Skip to main content
Cleaned up grammar, formatting, tags
Source Link
David Roberts
  • 35.5k
  • 11
  • 124
  • 349

I have observed some similar things between a reformulation of the Sunflower conjecture andSunflower conjecture (see also conjecture 1.3 in Improved bounds for the sunflower lemma) and Szemerédi's theorem such that for Szemerédi's theorem we have an often-used equivalent finitary version which states that:

Theorem: for every positive integer $k$ and real number $\delta\in (0,1]$ there exists a positive integer $N=N(\delta,k)$ such that every subset of $\{1,2,\cdots,N\}$ of size at least $δN$ contains an arithmetic progression of length $k$ say $k-\text{arithmitic progression}$

Theorem: for every positive integer $k$ and real number $\delta\in (0,1]$ there exists a positive integer $N=N(\delta,k)$ such that every subset of $\{1,2,\cdots,N\}$ of size at least $δN$ contains an arithmetic progression of length $k$ say $k\text{-arithmetic progression}$

For Sunflower conjecture (seeThe Sunflower conjecture 1.3 page 2) it states that :

Conjecture:Let $r ≥ 3$. There exists $c = c(r)$ such that any $w$-set system $F$ of size $|F| ≥ c^w$ contains an $r$-sunflower

Conjecture: Let $r ≥ 3$. There exists $c = c(r)$ such that any $w$-set system $F$ of size $|F| ≥ c^w$ contains an $r$-sunflower

We see that both of them investigate about existence of such constant with such bounds size forbounds for which we have $k-\text{arithmitic progression}$$k\text{-arithmetic progression}$ or $r$-sunflower,. Also other, another thing that attracted my attention is that for Erdős conjecture on arithmetic progressions In 1936, Erdős and Turán made in 1936 the weaker conjecture that any set of integers with positive natural density contains infinitely many 3 term-term arithmetic progressions. This was proven by Klaus Roth in 1952, and generalized to arbitrarily long arithmetic progressions by Szemerédi in 1975 in what is now known as Szemerédi's theorem. In the opposite direction, Kostochka proved that any $w$-set system of size $|F| ≥ cw! · {(\log \log \log w/ \log \log w)}^{w}$ $$ |F| \geq cw! \cdot {(\log \log \log w/ \log \log w)}^{w} $$ must contain a $3$-sunflower for some absolute constant $c$ ,. Now for Quantitativequantitative bounds of $r_k(N)$(the size of the largest subset of $\{1, 2, ..., N \}$$\{1, 2, \ldots, N \}$ without an arithmetic progression of length $k$) it is an open problem to determine its exact growth rate,. In the same time it is an open problem to determine the exact rate growth or exact bounds for The sunflower ( Thethe sunflower lemma via Shannon entropy) ,. My question here is is:

Question: According to similar things which I have cited above between Sunflower conjecture and Szemerédi's theorem is there any non trivial relationship between them ? And in which context we can consider Sunflower concide with arithmitic progression ?

Question: According to similar things which I have cited above between the Sunflower conjecture and Szemerédi's theorem, is there any non-trivial relationship between them? And in which context we can consider Sunflower coincide with arithmetic progression?

I have observed some similar things between reformulation of Sunflower conjecture and Szemerédi's theorem such that for Szemerédi's theorem we have an often-used equivalent finitary version which states that:

Theorem: for every positive integer $k$ and real number $\delta\in (0,1]$ there exists a positive integer $N=N(\delta,k)$ such that every subset of $\{1,2,\cdots,N\}$ of size at least $δN$ contains an arithmetic progression of length $k$ say $k-\text{arithmitic progression}$

For Sunflower conjecture (see conjecture 1.3 page 2) it states that :

Conjecture:Let $r ≥ 3$. There exists $c = c(r)$ such that any $w$-set system $F$ of size $|F| ≥ c^w$ contains an $r$-sunflower

We see that both of them investigate about existence of such constant with such bounds size for which we have $k-\text{arithmitic progression}$ or $r$-sunflower, Also other thing attracted my attention is that for Erdős conjecture on arithmetic progressions In 1936, Erdős and Turán made the weaker conjecture that any set of integers with positive natural density contains infinitely many 3 term arithmetic progressions. This was proven by Klaus Roth in 1952, and generalized to arbitrarily long arithmetic progressions by Szemerédi in 1975 in what is now known as Szemerédi's theorem. In the opposite Kostochka proved that any $w$-set system of size $|F| ≥ cw! · {(\log \log \log w/ \log \log w)}^{w}$ must contain a $3$-sunflower for some absolute constant $c$ , Now for Quantitative bounds of $r_k(N)$(the size of the largest subset of $\{1, 2, ..., N \}$ without an arithmetic progression of length $k$) it is an open problem to determine its exact growth rate, In the same time it is an open problem to determine the exact rate growth or exact bounds for The sunflower ( The sunflower lemma via Shannon entropy) , My question here is :

Question: According to similar things which I have cited above between Sunflower conjecture and Szemerédi's theorem is there any non trivial relationship between them ? And in which context we can consider Sunflower concide with arithmitic progression ?

I have observed some similar things between a reformulation of the Sunflower conjecture (see also conjecture 1.3 in Improved bounds for the sunflower lemma) and Szemerédi's theorem such that for Szemerédi's theorem we have an often-used equivalent finitary version which states that:

Theorem: for every positive integer $k$ and real number $\delta\in (0,1]$ there exists a positive integer $N=N(\delta,k)$ such that every subset of $\{1,2,\cdots,N\}$ of size at least $δN$ contains an arithmetic progression of length $k$ say $k\text{-arithmetic progression}$

The Sunflower conjecture states that :

Conjecture: Let $r ≥ 3$. There exists $c = c(r)$ such that any $w$-set system $F$ of size $|F| ≥ c^w$ contains an $r$-sunflower

We see that both of them investigate about existence of such constant with such size bounds for which we have $k\text{-arithmetic progression}$ or $r$-sunflower. Also, another thing that attracted my attention is that for Erdős conjecture on arithmetic progressions, Erdős and Turán made in 1936 the weaker conjecture that any set of integers with positive natural density contains infinitely many 3-term arithmetic progressions. This was proven by Klaus Roth in 1952, and generalized to arbitrarily long arithmetic progressions by Szemerédi in 1975 in what is now known as Szemerédi's theorem. In the opposite direction, Kostochka proved that any $w$-set system of size $$ |F| \geq cw! \cdot {(\log \log \log w/ \log \log w)}^{w} $$ must contain a $3$-sunflower for some absolute constant $c$. Now for quantitative bounds of $r_k(N)$(the size of the largest subset of $\{1, 2, \ldots, N \}$ without an arithmetic progression of length $k$) it is an open problem to determine its exact growth rate. In the same time it is an open problem to determine the exact rate growth or exact bounds for The sunflower (the sunflower lemma via Shannon entropy). My question here is:

Question: According to similar things which I have cited above between the Sunflower conjecture and Szemerédi's theorem, is there any non-trivial relationship between them? And in which context we can consider Sunflower coincide with arithmetic progression?

deleted 1 character in body
Source Link

I have observed some similar things between reformulation of Sunflower conjecture and Szemerédi's theorem such that for Szemerédi's theorem we have an often-used equivalent finitary version which states that:

Theorem: for every positive integer $k$ and real number $\delta\in (0,1]$ there exists a positive integer $N=N(\delta,k)$ such that every subset of $\{1,2,\cdots,N\}$ of size at least $δN$ contains an arithmetic progression of length $k$ say $k-\text{arithmitic progression}$

For Sunflower conjecture (see conjecture 1.3 page 2) it states that :

Conjecture:Let $r ≥ 3$. There exists $c = c(r)$ such that any $w$-set system $F$ of size $|F| ≥ c^w$ contains an $r$-sunflower

We see that both of them investigate about existence of such constant with such bounds size for which we have $k-\text{arithmitic progression}$ or $r$-sunflower, Also other thing attracted my attention is that for Erdős conjecture on arithmetic progressions In 1936, Erdős and Turán made the weaker conjecture that any set of integers with positive natural density contains infinitely many 3 term arithmetic progressions. This was proven by Klaus Roth in 1952, and generalized to arbitrarily long arithmetic progressions by Szemerédi in 1975 in what is now known as Szemerédi's theorem. In the same timeopposite Kostochka proved that any $w$-set system of size $|F| ≥ cw! · {(\log \log \log w/ \log \log w)}^{w}$ must contain a $3$-sunflower for some absolute constant $c$ , Now for Quantitative bounds of $r_k(N)$(the size of the largest subset of $\{1, 2, ..., N \}$ without an arithmetic progression of length $k$) it is an open problem to determine its exact growth rate, In the same time it is an open problem to determine the exact rate growth or exact bounds for The sunflower ( The sunflower lemma via Shannon entropy) , My question here is :

Question: According to similar things which I have cited above between Sunflower conjecture and Szemerédi's theorem is there any non trivial relationship between them ? And in which context we can consider Sunflower concide with arithmitic progression ?

I have observed some similar things between reformulation of Sunflower conjecture and Szemerédi's theorem such that for Szemerédi's theorem we have an often-used equivalent finitary version which states that:

Theorem: for every positive integer $k$ and real number $\delta\in (0,1]$ there exists a positive integer $N=N(\delta,k)$ such that every subset of $\{1,2,\cdots,N\}$ of size at least $δN$ contains an arithmetic progression of length $k$ say $k-\text{arithmitic progression}$

For Sunflower conjecture (see conjecture 1.3 page 2) it states that :

Conjecture:Let $r ≥ 3$. There exists $c = c(r)$ such that any $w$-set system $F$ of size $|F| ≥ c^w$ contains an $r$-sunflower

We see that both of them investigate about existence of such constant with such bounds size for which we have $k-\text{arithmitic progression}$ or $r$-sunflower, Also other thing attracted my attention is that for Erdős conjecture on arithmetic progressions In 1936, Erdős and Turán made the weaker conjecture that any set of integers with positive natural density contains infinitely many 3 term arithmetic progressions. This was proven by Klaus Roth in 1952, and generalized to arbitrarily long arithmetic progressions by Szemerédi in 1975 in what is now known as Szemerédi's theorem. In the same time Kostochka proved that any $w$-set system of size $|F| ≥ cw! · {(\log \log \log w/ \log \log w)}^{w}$ must contain a $3$-sunflower for some absolute constant $c$ , Now for Quantitative bounds of $r_k(N)$(the size of the largest subset of $\{1, 2, ..., N \}$ without an arithmetic progression of length $k$) it is an open problem to determine its exact growth rate, In the same time it is an open problem to determine the exact rate growth or exact bounds for The sunflower ( The sunflower lemma via Shannon entropy) , My question here is :

Question: According to similar things which I have cited above between Sunflower conjecture and Szemerédi's theorem is there any non trivial relationship between them ? And in which context we can consider Sunflower concide with arithmitic progression ?

I have observed some similar things between reformulation of Sunflower conjecture and Szemerédi's theorem such that for Szemerédi's theorem we have an often-used equivalent finitary version which states that:

Theorem: for every positive integer $k$ and real number $\delta\in (0,1]$ there exists a positive integer $N=N(\delta,k)$ such that every subset of $\{1,2,\cdots,N\}$ of size at least $δN$ contains an arithmetic progression of length $k$ say $k-\text{arithmitic progression}$

For Sunflower conjecture (see conjecture 1.3 page 2) it states that :

Conjecture:Let $r ≥ 3$. There exists $c = c(r)$ such that any $w$-set system $F$ of size $|F| ≥ c^w$ contains an $r$-sunflower

We see that both of them investigate about existence of such constant with such bounds size for which we have $k-\text{arithmitic progression}$ or $r$-sunflower, Also other thing attracted my attention is that for Erdős conjecture on arithmetic progressions In 1936, Erdős and Turán made the weaker conjecture that any set of integers with positive natural density contains infinitely many 3 term arithmetic progressions. This was proven by Klaus Roth in 1952, and generalized to arbitrarily long arithmetic progressions by Szemerédi in 1975 in what is now known as Szemerédi's theorem. In the opposite Kostochka proved that any $w$-set system of size $|F| ≥ cw! · {(\log \log \log w/ \log \log w)}^{w}$ must contain a $3$-sunflower for some absolute constant $c$ , Now for Quantitative bounds of $r_k(N)$(the size of the largest subset of $\{1, 2, ..., N \}$ without an arithmetic progression of length $k$) it is an open problem to determine its exact growth rate, In the same time it is an open problem to determine the exact rate growth or exact bounds for The sunflower ( The sunflower lemma via Shannon entropy) , My question here is :

Question: According to similar things which I have cited above between Sunflower conjecture and Szemerédi's theorem is there any non trivial relationship between them ? And in which context we can consider Sunflower concide with arithmitic progression ?

Source Link

Is there any relationship between Szemerédi's theorem and Sunflower conjecture?

I have observed some similar things between reformulation of Sunflower conjecture and Szemerédi's theorem such that for Szemerédi's theorem we have an often-used equivalent finitary version which states that:

Theorem: for every positive integer $k$ and real number $\delta\in (0,1]$ there exists a positive integer $N=N(\delta,k)$ such that every subset of $\{1,2,\cdots,N\}$ of size at least $δN$ contains an arithmetic progression of length $k$ say $k-\text{arithmitic progression}$

For Sunflower conjecture (see conjecture 1.3 page 2) it states that :

Conjecture:Let $r ≥ 3$. There exists $c = c(r)$ such that any $w$-set system $F$ of size $|F| ≥ c^w$ contains an $r$-sunflower

We see that both of them investigate about existence of such constant with such bounds size for which we have $k-\text{arithmitic progression}$ or $r$-sunflower, Also other thing attracted my attention is that for Erdős conjecture on arithmetic progressions In 1936, Erdős and Turán made the weaker conjecture that any set of integers with positive natural density contains infinitely many 3 term arithmetic progressions. This was proven by Klaus Roth in 1952, and generalized to arbitrarily long arithmetic progressions by Szemerédi in 1975 in what is now known as Szemerédi's theorem. In the same time Kostochka proved that any $w$-set system of size $|F| ≥ cw! · {(\log \log \log w/ \log \log w)}^{w}$ must contain a $3$-sunflower for some absolute constant $c$ , Now for Quantitative bounds of $r_k(N)$(the size of the largest subset of $\{1, 2, ..., N \}$ without an arithmetic progression of length $k$) it is an open problem to determine its exact growth rate, In the same time it is an open problem to determine the exact rate growth or exact bounds for The sunflower ( The sunflower lemma via Shannon entropy) , My question here is :

Question: According to similar things which I have cited above between Sunflower conjecture and Szemerédi's theorem is there any non trivial relationship between them ? And in which context we can consider Sunflower concide with arithmitic progression ?