# Difference between revisions of "Complexity of a set"

## Sets of complexity 1 in $[3]^n$

### Definition

Let $\mathcal{U}, \mathcal{V}$ and $\mathcal{W}$ be collections of subsets of $[n].$ Then we can define a subset $\mathcal{A}$ 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 $\mathcal{U},$ the 2-set of x belongs to $\mathcal{V}$ and the 3-set of x belongs to $\mathcal{W}.$ If $\mathcal{A}$ 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 $\mathcal{W}$ consists of all subsets of $[n].$ We say that $\mathcal{A}$ is a special set of complexity 1 if there exist $\mathcal{U}$ and $\mathcal{V}$ such that $\mathcal{A}$ is the set of all $x\in[3]^n$ such that the 1-set of x belongs to $\mathcal{U}$ and the 2-set of x belongs to $\mathcal{V}.$ 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 $(U_1,\dots,U_k)$ of $[n].$ Suppose that for every set $E$ of size j there we have a collection $\mathcal{U}_E$ of j-tuples $(U_i:i\in E)$ of disjoint subsets of $[n]$ indexed by $E.$ Then we can define a set system $\mathcal{A}$ to consist of all ordered partitions $(U_1,\dots,U_k)$ such that for every $E\subset\{1,2,\dots,k\}$ of size j the j-tuple of disjoint sets $(U_i:i\in E)$ belongs to $\mathcal{U}_E.$ If $\mathcal{A}$ 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).