Complexity of a set

From Polymath1Wiki

(Difference between revisions)
Jump to: navigation, search
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).
-
 
-
[http://www.resumesplanet.com resume writing service]
 
-
 
-
[http://perfectessay.net/blog/perfect-essay-for-successful-education/ perfect essays]
 

Current revision

Contents

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

Personal tools