# Complexity of a set

## Contents

## Sets of complexity 1 in [math][3]^n[/math]

### Definition

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

## Sets of complexity j in [math][k]^n[/math]

We can make a similar definition for sequences in [math][k]^n[/math], or equivalently ordered partitions [math](U_1,\dots,U_k)[/math] of [math][n].[/math]
Suppose that for every set [math]E[/math] of size j there we have a collection [math]\mathcal{U}_E[/math] of j-tuples [math](U_i:i\in E)[/math] of disjoint subsets of [math][n][/math] indexed by [math]E.[/math] Then we can define a set system [math]\mathcal{A}[/math] to consist of all ordered partitions [math](U_1,\dots,U_k)[/math] such that for every [math]E\subset\{1,2,\dots,k\}[/math] of size j the j-tuple of disjoint sets [math](U_i:i\in E)[/math] belongs to [math]\mathcal{U}_E.[/math] If [math]\mathcal{A}[/math] can be defined in that way then we say that it has *complexity j*.

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).