Sunflower (arithmetic) – Wikipedia

Assortment of units wherein each two units have the identical intersection

Within the mathematical fields of set theory and extremal combinatorics, a sunflower or ${displaystyle Delta }$-system^[1] is a set of sets whose pairwise intersection is fixed. This fixed intersection is named the kernel of the sunflower.

The primary analysis query arising in relation to sunflowers is: beneath what situations does there exist a massive sunflower (a sunflower with many units) in a given assortment of units? The ${displaystyle Delta }$-lemma, sunflower lemma, and the Erdős-Rado sunflower conjecture give successively weaker situations which might suggest the existence of a giant sunflower in a given assortment, with the latter being one of the vital well-known open issues of extremal combinatorics.^[2]

Formal definition[edit]

Suppose ${displaystyle W}$ is a set system over ${displaystyle U}$, that’s, a set of subsets of a set ${displaystyle U}$. The gathering ${displaystyle W}$ is a sunflower (or ${displaystyle Delta }$-system) if there’s a subset ${displaystyle S}$ of ${displaystyle U}$ such that for every distinct ${displaystyle A}$ and ${displaystyle B}$ in ${displaystyle W}$, we’ve ${displaystyle Acap B=S}$. In different phrases, a set system or assortment of units ${displaystyle W}$ is a sunflower if the pairwise intersection of every set in ${displaystyle W}$ is similar.
Notice that this intersection, ${displaystyle S}$, could also be empty; a set of pairwise disjoint subsets can be a sunflower. Equally, a set of units every containing the identical components can be trivially a sunflower.

Sunflower lemma and conjecture[edit]

The research of sunflowers typically focuses on when set methods include sunflowers, specifically, when a set system is sufficiently massive to essentially include a sunflower.

Particularly, researchers analyze the perform ${displaystyle f(okay,r)}$ for nonnegative integers ${displaystyle okay,r}$, which is outlined to be the smallest nonnegative integer ${displaystyle n}$ such that, for any set system ${displaystyle W}$ such that each set ${displaystyle Sin W}$ has cardinality at most ${displaystyle okay}$, if ${displaystyle W}$ has greater than ${displaystyle n}$ units, then ${displaystyle W}$ comprises a sunflower of ${displaystyle r}$ units. Although it’s not clear that such an ${displaystyle n}$ should exist, a fundamental and easy results of Erdős and Rado, the Delta System Theorem, signifies that it does.

Erdos-Rado Delta System Theorem:^{[citation needed]}

For every ${displaystyle okay>0}$, ${displaystyle r>0}$ is an integer ${displaystyle f(okay,r)}$ such {that a} set system ${displaystyle F}$ of ${displaystyle okay}$-sets is of cardinality better than ${displaystyle f(okay,r)}$, then ${displaystyle F}$ comprises a sunflower of dimension ${displaystyle r}$.

Within the literature, ${displaystyle W}$ is usually assumed to be a set reasonably than a set, so any set can seem in ${displaystyle W}$ at most as soon as. By including dummy components, it suffices to solely contemplate set methods ${displaystyle W}$ such that each set in ${displaystyle W}$ has cardinality ${displaystyle okay}$, so typically the sunflower lemma is equivalently phrased as holding for “${displaystyle okay}$-uniform” set methods.

Sunflower lemma[edit]

Erdős & Rado (1960, p. 86) proved the sunflower lemma, which states that^[4]

${displaystyle f(okay,r)leq okay!(r-1)^{okay}.}$

That’s, if ${displaystyle okay}$ and ${displaystyle r}$ are optimistic integers, then a set system ${displaystyle W}$ of cardinality better than ${displaystyle okay!(r-1)^{okay}}$ of units of cardinality ${displaystyle okay}$ comprises a sunflower with not less than ${displaystyle r}$ units.

The Erdős-Rado sunflower lemma will be proved straight by means of induction. First, ${displaystyle f(1,r)leq r-1}$, because the set system ${displaystyle W}$ should be a set of distinct units of dimension one, and so ${displaystyle r}$ of those units make a sunflower. Within the normal case, suppose ${displaystyle W}$ has no sunflower with ${displaystyle r}$ units. Then contemplate ${displaystyle A_{1},A_{2},ldots ,A_{t}in W}$ to be a maximal assortment of pairwise disjoint units (that’s, ${displaystyle A_{i}cap A_{j}}$ is the empty set except ${displaystyle i=j}$, and each set in ${displaystyle W}$ intersects with some ${displaystyle A_{i}}$). As a result of we assumed that ${displaystyle W}$ had no sunflower of dimension ${displaystyle r}$, and a set of pairwise disjoint units is a sunflower, ${displaystyle t<r}$.

Let ${displaystyle A=A_{1}cup A_{2}cup cdots cup A_{t}}$. Since every ${displaystyle A_{i}}$ has cardinality ${displaystyle okay}$, the cardinality of ${displaystyle A}$ is bounded by ${displaystyle ktleq okay(r-1)}$. Outline ${displaystyle W_{a}}$ for some ${displaystyle ain A}$ to be

${displaystyle W_{a}={Ssetminus {a}mid ain S,,Sin W}.}$

Then ${displaystyle W_{a}}$ is a set system, like ${displaystyle W}$, besides that each ingredient of ${displaystyle W_{a}}$ has ${displaystyle k-1}$ components. Moreover, each sunflower of ${displaystyle W_{a}}$ corresponds to a sunflower of ${displaystyle W}$, just by including again ${displaystyle a}$ to each set. Which means, by our assumption that ${displaystyle W}$ has no sunflower of dimension ${displaystyle r}$, the dimensions of ${displaystyle W_{a}}$ should be bounded by ${displaystyle f(k-1,r)-1}$.

Since each set ${displaystyle Sin W}$ intersects with one of many ${displaystyle A_{i}}$‘s, it intersects with ${displaystyle A}$, and so it corresponds to not less than one of many units in a ${displaystyle W_{a}}$:

${displaystyle |W|leq sum _{ain A}|W_{a}|leq |A|(f(k-1,r)-1)leq okay(r-1)f(k-1,r)-|A|leq okay(r-1)f(k-1,r)-1.}$

Therefore, if $W$, then ${displaystyle W}$ comprises an ${displaystyle r}$ set sunflower of dimension ${displaystyle okay}$ units. Therefore, ${displaystyle f(okay,r)leq okay(r-1)f(k-1,r)}$ and the theory follows.^[2]

Erdős-Rado sunflower conjecture[edit]

The sunflower conjecture is one in every of a number of variations of the conjecture of Erdős & Rado (1960, p. 86) that for every ${displaystyle r>2}$, ${displaystyle f(okay,r)leq C^{okay}}$ for some fixed ${displaystyle C>0}$ relying solely on ${displaystyle r}$. The conjecture stays huge open even for fastened low values of ${displaystyle r}$; for instance ${displaystyle r=3}$; it’s not identified whether or not ${displaystyle f(okay,3)leq C^{okay}}$ for some ${displaystyle C>0}$. ^[5] A 2021 paper by Alweiss, Lovett, Wu, and Zhang offers the most effective progress in the direction of the conjecture, proving that ${displaystyle f(okay,r)leq C^{okay}}$ for ${displaystyle C=O(r^{3}log(okay)log log(okay))}$.^[7] A month after the discharge of the primary model of their paper, Rao sharpened the certain to ${displaystyle C=O(rlog(rk))}$; the present best-known certain is ${displaystyle C=O(rlog okay)}$.

Sunflower decrease bounds[edit]

Erdős and Rado proved the next decrease certain on ${displaystyle f(okay,r)}$. It is the same as the assertion that the unique sunflower lemma is perfect in ${displaystyle r}$.

Theorem. ${displaystyle (r-1)^{okay}leq f(okay,r).}$

Proof.
For ${displaystyle okay=1}$ a set of ${displaystyle r-1}$ sequence of distinct components will not be a sunflower.
Let ${displaystyle h(k-1,r)}$ denote the dimensions of the most important set of ${displaystyle k-1}$-sets with no ${displaystyle r}$ sunflower. Let ${displaystyle H}$ be such a set. Take a further set of ${displaystyle r-1}$ components and add one ingredient to every set in one in every of ${displaystyle r-1}$ disjoint copies of ${displaystyle H}$. Take the union of the ${displaystyle r-1}$ disjoint copies with the weather added and denote this set ${displaystyle H^{*}}$. The copies of ${displaystyle H}$ with a component added type an ${displaystyle r-1}$ partition of ${displaystyle H^{*}}$. We’ve that,${displaystyle (r-1)|H|leq |H^{*}|}$. ${displaystyle H^{*}}$ is sunflower free since any choice of ${displaystyle r}$ units if in one of many disjoint partitions is sunflower free by assumption of H being sunflower free. In any other case, if ${displaystyle r}$ units are chosen from throughout a number of units of the partition, then two should be chosen from one partition since there are solely ${displaystyle r-1}$ partitions. This suggests that not less than two units and never all of the units could have a component in frequent. Therefore this isn’t a sunflower of ${displaystyle r}$ units.

See Also

clickr, or a younger man’s Flickr clonejure

A stronger result’s the next theorem:

Theorem. ${displaystyle f(a+b,r)geq (f(a,r)-1)(f(b,r)-1)}$

Proof. Let ${displaystyle F}$ and ${displaystyle F^{*}}$ be two sunflower free households. For every set ${displaystyle A}$ in F, append each set in ${displaystyle F^{*}}$ to ${displaystyle A}$ to supply ${displaystyle |F^{*}|}$ many units. Denote this household of units ${displaystyle F_{A}}$. Take the union of ${displaystyle F_{A}}$ over all ${displaystyle A}$ in ${displaystyle F}$. This produces a household of ${displaystyle |F^{*}||F|}$ units which is sunflower free.

Additionally it is identified that ${displaystyle 10^{.5k}leq f(okay,3)}$.

Functions of the sunflower lemma[edit]

The sunflower lemma has quite a few functions in theoretical computer science. For instance, in 1986, Razborov used the sunflower lemma to show that the Clique language required ${displaystyle n^{log(n)}}$ (superpolynomial) dimension monotone circuits, a breakthrough lead to circuit complexity concept on the time. Håstad, Jukna, and Pudlák used it to show decrease bounds on depth-${displaystyle 3}$ ${displaystyle AC_{0}}$ circuits. It has additionally been utilized within the parameterized complexity of the hitting set problem, to design fixed-parameter tractable algorithms for locating small units of components that include not less than one ingredient from a given household of units.

Analogue for infinite collections of units[edit]

A model of the ${displaystyle Delta }$-lemma which is actually equal to the Erdős-Rado ${displaystyle Delta }$-system theorem states {that a} countable assortment of k-sets comprises a countably infinite sunflower or ${displaystyle Delta }$-system.

The ${displaystyle Delta }$-lemma states that each uncountable assortment of finite sets comprises an uncountable ${displaystyle Delta }$-system.

The ${displaystyle Delta }$-lemma is a combinatorial set-theoretic software utilized in proofs to impose an upper bound on the dimensions of a set of pairwise incompatible components in a forcing poset. It might for instance be used as one of many elements in a proof exhibiting that it’s in step with Zermelo–Fraenkel set theory that the continuum hypothesis doesn’t maintain. It was launched by Shanin (1946).

If ${displaystyle W}$ is an ${displaystyle omega _{2}}$-sized assortment of countable subsets of ${displaystyle omega _{2}}$, and if the continuum speculation holds, then there’s an ${displaystyle omega _{2}}$-sized ${displaystyle Delta }$-subsystem. Let ${displaystyle langle A_{alpha }:alpha <omega _{2}rangle }$ enumerate ${displaystyle W}$. For ${displaystyle operatorname {cf} (alpha )=omega _{1}}$, let
${displaystyle f(alpha )=sup(A_{alpha }cap alpha )}$. By Fodor’s lemma, repair ${displaystyle S}$ stationary in ${displaystyle omega _{2}}$ such that ${displaystyle f}$ is continually equal to ${displaystyle beta }$ on ${displaystyle S}$.
Construct ${displaystyle S’subseteq S}$ of cardinality ${displaystyle omega _{2}}$ such that each time ${displaystyle i<j}$ are in ${displaystyle S’}$ then ${displaystyle A_{i}subseteq j}$. Utilizing the continuum speculation, there are solely ${displaystyle omega _{1}}$-many countable subsets of ${displaystyle beta }$, so by additional thinning we could stabilize the kernel.

See additionally[edit]

References[edit]

• Alweiss, Ryan; Lovett, Shachar; Wu, Kewen; Zhang, Jiapeng (June 2020), “Improved bounds for the sunflower lemma”, Proceedings of the 52nd Annual ACM SIGACT Symposium on Principle of Computing, Affiliation for Computing Equipment, pp. 624–630, arXiv:1908.08483, doi:10.1145/3357713.3384234, ISBN 978-1-4503-6979-4, S2CID 201314765
• Bell, Tolson; Chueluecha, Suchakree; Warnke, Lutz (2021), “Notice on Sunflowers”, Discrete Arithmetic, 344 (7): 112367, arXiv:2009.09327, doi:10.1016/j.disc.2021.112367, MR 4240687, S2CID 221818818
• Deza, M.; Frankl, P. (1981), “Each massive set of equidistant (0,+1,–1)-vectors types a sunflower”, Combinatorica, 1 (3): 225–231, doi:10.1007/BF02579328, ISSN 0209-9683, MR 0637827, S2CID 14043028
• Erdős, Paul; Rado, R. (1960), “Intersection theorems for methods of units”, Journal of the London Mathematical Society, Second Collection, 35 (1): 85–90, doi:10.1112/jlms/s1-35.1.85, ISSN 0024-6107, MR 0111692
• Flum, Jörg; Grohe, Martin (2006), “A Kernelization of Hitting Set”, Parameterized Complexity Principle, EATCS Ser. Texts in Theoretical Laptop Science, Springer, pp. 210–212, doi:10.1007/3-540-29953-X, ISBN 978-3-540-29952-3, MR 2238686
• Jech, Thomas (2003), Set Principle, Springer
• Kunen, Kenneth (1980), Set Theory: An Introduction to Independence Proofs, North-Holland, ISBN 978-0-444-85401-8
• Rao, Anup (2020-02-25), “Coding for Sunflowers”, Discrete Evaluation, 2020 (2): 11887, doi:10.19086/da.11887, S2CID 202558957
• Rao, Anup (2023), “Sunflowers: from soil to oil” (PDF), Bull. Amer. Math. Soc., 60 (1): 29–38, doi:10.1090/bull/1777
• Shanin, N. A. (1946), “A theorem from the final concept of units”, C. R. (Doklady) Acad. Sci. URSS, New Collection, 53: 399–400
• Tao, Terence (2020), The sunflower lemma via Shannon entropy, What’s new (private weblog)

Exterior hyperlinks[edit]