Complexity of a set
From Polymath1Wiki
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 xi = 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 ![x\in[3]^n](/polymath1/images/math/7/e/b/7eb9856b9e08d30476708ffe0dcdc9a7.png)
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).
