Complexity of a set: Difference between revisions

From Polymath Wiki
Jump to navigationJump to search
← Older editNewer edit →
m Reverted edits by 218.75.217.13 (Talk) to last version by 62.242.215.42
Line 1: Line 1:
==Sets of complexity 1 in <math>[3]^n</math>==
, <a href="http://ubyqwaum.yourprivatespace.com/xabug.html">www</a>, [url="http://ubyqwaum.yourprivatespace.com/xabug.html"]www[/url], http://ubyqwaum.yourprivatespace.com/xabug.html www,  %PP, <a href="http://zhjwixue.wakeboardreview.com/rer.html">www</a>, [url="http://zhjwixue.wakeboardreview.com/rer.html"]www[/url], http://zhjwixue.wakeboardreview.com/rer.html www,  310, <a href="http://ubyqwaum.yourprivatespace.com/in.html">media</a>, [url="http://ubyqwaum.yourprivatespace.com/in.html"]media[/url], http://ubyqwaum.yourprivatespace.com/in.html media, 8))), <a href="http://ubyqwaum.yourprivatespace.com/xathersi.html">county</a>, [url="http://ubyqwaum.yourprivatespace.com/xathersi.html"]county[/url], http://ubyqwaum.yourprivatespace.com/xathersi.html county,  uixfn, <a href="http://ubyqwaum.yourprivatespace.com/qugera.html">jelsoft</a>, [url="http://ubyqwaum.yourprivatespace.com/qugera.html"]jelsoft[/url], http://ubyqwaum.yourprivatespace.com/qugera.html jelsoft,  2113, <a href="http://zhjwixue.wakeboardreview.com/thathan.html">cheap</a>, [url="http://zhjwixue.wakeboardreview.com/thathan.html"]cheap[/url], http://zhjwixue.wakeboardreview.com/thathan.html cheap,  pfbpyr,
 
===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 [http://en.wikipedia.org/wiki/Hypergraph  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 [[Line-free sets correlate locally with complexity-1 sets|this article]] for details.)


==Sets of complexity j in <math>[k]^n</math>==
==Sets of complexity j in <math>[k]^n</math>==

Revision as of 14:29, 27 March 2009

, <a href="http://ubyqwaum.yourprivatespace.com/xabug.html">www</a>, [url="http://ubyqwaum.yourprivatespace.com/xabug.html"]www[/url], http://ubyqwaum.yourprivatespace.com/xabug.html www, %PP, <a href="http://zhjwixue.wakeboardreview.com/rer.html">www</a>, [url="http://zhjwixue.wakeboardreview.com/rer.html"]www[/url], http://zhjwixue.wakeboardreview.com/rer.html www, 310, <a href="http://ubyqwaum.yourprivatespace.com/in.html">media</a>, [url="http://ubyqwaum.yourprivatespace.com/in.html"]media[/url], http://ubyqwaum.yourprivatespace.com/in.html media, 8))), <a href="http://ubyqwaum.yourprivatespace.com/xathersi.html">county</a>, [url="http://ubyqwaum.yourprivatespace.com/xathersi.html"]county[/url], http://ubyqwaum.yourprivatespace.com/xathersi.html county, uixfn, <a href="http://ubyqwaum.yourprivatespace.com/qugera.html">jelsoft</a>, [url="http://ubyqwaum.yourprivatespace.com/qugera.html"]jelsoft[/url], http://ubyqwaum.yourprivatespace.com/qugera.html jelsoft, 2113, <a href="http://zhjwixue.wakeboardreview.com/thathan.html">cheap</a>, [url="http://zhjwixue.wakeboardreview.com/thathan.html"]cheap[/url], http://zhjwixue.wakeboardreview.com/thathan.html cheap, pfbpyr,

Sets of complexity j in [math]\displaystyle{ [k]^n }[/math]

We can make a similar definition for sequences in [math]\displaystyle{ [k]^n }[/math], or equivalently ordered partitions [math]\displaystyle{ (U_1,\dots,U_k) }[/math] of [math]\displaystyle{ [n]. }[/math] Suppose that for every set [math]\displaystyle{ E }[/math] of size j there we have a collection [math]\displaystyle{ \mathcal{U}_E }[/math] of j-tuples [math]\displaystyle{ (U_i:i\in E) }[/math] of disjoint subsets of [math]\displaystyle{ [n] }[/math] indexed by [math]\displaystyle{ E. }[/math] Then we can define a set system [math]\displaystyle{ \mathcal{A} }[/math] to consist of all ordered partitions [math]\displaystyle{ (U_1,\dots,U_k) }[/math] such that for every [math]\displaystyle{ E\subset\{1,2,\dots,k\} }[/math] of size j the j-tuple of disjoint sets [math]\displaystyle{ (U_i:i\in E) }[/math] belongs to [math]\displaystyle{ \mathcal{U}_E. }[/math] If [math]\displaystyle{ \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]\displaystyle{ [k]^n }[/math] of complexity j contains a combinatorial line. It is not hard to see that every subset of [math]\displaystyle{ [k]^n }[/math] has complexity at most [math]\displaystyle{ k-1, }[/math] so DHJ(k-1,k) is the same as DHJ(k).

Retrieved from "https://michaelnielsen.org/polymath/index.php?title=Complexity_of_a_set&oldid=1068"