# Complexity of a set

### From Polymath1Wiki

Current revision (20:06, 30 October 2013) (view source) (→Sets of complexity j in [k]^n) |
|||

Line 19: | Line 19: | ||

DHJ(j,k) is the assertion that every subset of <math>[k]^n</math> of complexity j contains a combinatorial line. It is not hard to see that every subset of <math>[k]^n</math> has complexity at most <math>k-1,</math> so DHJ(k-1,k) is the same as DHJ(k). | DHJ(j,k) is the assertion that every subset of <math>[k]^n</math> of complexity j contains a combinatorial line. It is not hard to see that every subset of <math>[k]^n</math> has complexity at most <math>k-1,</math> so DHJ(k-1,k) is the same as DHJ(k). | ||

- | |||

- | |||

- | |||

- |

## Current revision

## Contents |

## Sets of complexity 1 in [3]^{n}

### Definition

Let and be collections of subsets of [*n*]. Then we can define a subset of [3]^{n} by taking the set of all sequences x such that the 1-set of x (meaning the set of coordinates i where *x*_{i} = 1) belongs to the 2-set of x belongs to and the 3-set of x belongs to If can be defined in this way, then we say that it has *complexity 1*. DHJ(1,3) is the special case of DHJ(3) that asserts that a dense set of complexity 1 contains a combinatorial line.

### Motivation

Sets of complexity 1 are closely analogous to sets that arise in the theory of 3-uniform hypergraphs. One way of constructing a 3-uniform hypergraph H is to start with a graph G and let H be the set of all triangles in G (or more formally the set of all triples xyz such that xy, yz and xz are edges of G). These sets form a complete set of obstructions to uniformity for 3-uniform hypergraphs, so there is reason to expect that sets of complexity 1 will be of importance for DHJ(3).

### Special sets of complexity 1

A more restricted notion of a set of complexity 1 is obtained if one assumes that consists of all subsets of [*n*]. We say that is a *special set of complexity 1* if there exist and such that is the set of all such that the 1-set of x belongs to and the 2-set of x belongs to Special sets of complexity 1 appear as local obstructions to uniformity in DHJ(3). (See this article for details.)

## Sets of complexity j in [*k*]^{n}

We can make a similar definition for sequences in [*k*]^{n}, or equivalently ordered partitions of [*n*].
Suppose that for every set *E* of size j there we have a collection of j-tuples of disjoint subsets of [*n*] indexed by *E*. Then we can define a set system to consist of all ordered partitions such that for every of size j the j-tuple of disjoint sets belongs to If can be defined in that way then we say that it has *complexity j*.

DHJ(j,k) is the assertion that every subset of [*k*]^{n} of complexity j contains a combinatorial line. It is not hard to see that every subset of [*k*]^{n} has complexity at most *k* − 1, so DHJ(k-1,k) is the same as DHJ(k).