Complexity of a set
Sets of complexity 1 in [math]\displaystyle{ [3]^n }[/math]
Definition
Let [math]\displaystyle{ \mathcal{U}, \mathcal{V} }[/math] and [math]\displaystyle{ \mathcal{W} }[/math] be collections of subsets of [math]\displaystyle{ [n]. }[/math] Then we can define a subset [math]\displaystyle{ \mathcal{A} }[/math] of [math]\displaystyle{ [3]^n }[/math] by taking the set of all sequences x such that the 1-set of x (meaning the set of coordinates i where [math]\displaystyle{ x_i=1 }[/math] belongs to [math]\displaystyle{ \mathcal{U}, }[/math] the 2-set of x belongs to [math]\displaystyle{ \mathcal{V} }[/math] and the 3-set of x belongs to [math]\displaystyle{ \mathcal{W}. }[/math] If [math]\displaystyle{ \mathcal{A} }[/math] 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 [math]\displaystyle{ \mathcal{W} }[/math] consists of all subsets of [math]\displaystyle{ [n]. }[/math] We say that [math]\displaystyle{ \mathcal{A} }[/math] is a special set of complexity 1 if there exist [math]\displaystyle{ \mathcal{U} }[/math] and [math]\displaystyle{ \mathcal{V} }[/math] such that [math]\displaystyle{ \mathcal{A} }[/math] is the set of all [math]\displaystyle{ x\in[3]^n }[/math] such that the 1-set of x belongs to [math]\displaystyle{ \mathcal{U} }[/math] and the 2-set of x belongs to [math]\displaystyle{ \mathcal{V}. }[/math] Special sets of complexity 1 appear as local obstructions to uniformity in DHJ(3). (See [[Line_free_sets_correlate_locally_with_complexity-1_sets|this article] for details.)
