Odd-Sunflowers

EUROCOMB’23

Abstract
Extending the notion of sunflowers, we call a family of at least two sets an odd-sunflower if every element of the underlying set is contained in an odd number of sets or in none of them. It follows from the Erdős-Szemerédi conjecture, recently proved by Naslund and Sawin, that there is a constant $\mu<2$ such that every family of subsets of an $n$-element set that contains no odd-sunflower consists of at most $\mu^n$ sets. We construct such families of size at least $1.5021^n$.

Pages:
441–449
References

H. L. Abbott, D. Hanson: On finite Δ-systems II, Discrete Math., 17 (1977), 121--126.
https://doi.org/10.1016/0012-365X(77)90139-X

H. L. Abbott, D. Hanson, and N. Sauer: Intersection theorems for systems of sets, J. Combin. Theory Ser. A, 12 (3) (1972), 381--389.
https://doi.org/10.1016/0097-3165(72)90103-3

N. Alon and R. Holzman: Near-sunflowers and focal families, preprint, https://arxiv.org/abs/2010.05992.

R. Alweiss, S. Lovett, K. Wu, and J. Zhang: Improved bounds for the sunflower lemma, Ann. of Math. (2) 194 (2021), no. 3, 795--815.
https://doi.org/10.4007/annals.2021.194.3.5

L. Babai and P. Frankl: Linear Algebra Methods in Combinatorics (Preliminary Version 2, Dept. of Computer Science, The University of Chicago, 1992.

E. Croot, V. Lev, and P. Pach: Progression-free sets in Z^n_4 are exponentially small, Ann. of Math. (2) 185 (2017), 331--337.
https://doi.org/10.4007/annals.2017.185.1.7

W. A. Deuber, P. Erdős, D. S. Gunderson, A. V. Kostochka, and A. G. Meyer, Intersection statements for systems of sets, J. Combin. Theory, Ser. A, 79 (1997), 118--132.
https://doi.org/10.1006/jcta.1997.2778

J. S. Ellenberg and D. Gijswijt: On large subsets of F^n_q with no three-term arithmetic progression, Ann. of Math. (2) 185 (2017), 339--343.
https://doi.org/10.4007/annals.2017.185.1.8

P. Erdős, E. C. Milner, and R. Rado: Intersection theorems for systems of sets (III), J. Austral. Math. Soc. 18 (1974), 22-40.
https://doi.org/10.1017/S1446788700019091

P. Erdős and R. Rado: Intersection theorems for systems of sets, J. London Math. Soc., Second Series, 35 (1) (1960), 85--90.
https://doi.org/10.1112/jlms/s1-35.1.85

P. Erdős and E. Szemerédi: Combinatorial properties of systems of sets, J. Combin. Theory, Ser. A 24 (1978), 308--313.
https://doi.org/10.1016/0097-3165(78)90060-2

P. Frankl: Extremalis halmazrendszerek (in Hungarian), kandidátusi értekezes, MTA, Budapest (1977).

P. Frankl: Pseudo sunflowers, European J. Combin. 104 (2022), Paper No. 103553, 6 pp.
https://doi.org/10.1016/j.ejc.2022.103553

P. Frankl and N. Tokushige: Extremal Problems for Finite Sets, Student Math. Library, vol. 86, Amer. Math. Soc., Providence, R.I., 2018.
https://doi.org/10.1090/stml/086

B. Huppert: Endliche Gruppen I, Grundlehren der mathematischen Wissenschaften (GL, volume 134), Springer, 1967.
https://doi.org/10.1007/978-3-642-64981-3

A. V. Kostochka: Extremal problems on Δ-systems, in: Numbers, Information and Complexity, Bielefeld, 1998, Kluwer Acad. Publ., Boston, MA (2000), 143-150 https://mathoverflow.net/questions/163689.
https://doi.org/10.1007/978-1-4757-6048-4_14

E. Naslund and W. Sawin: Upper bounds for sunflower-free sets, Forum Math. Sigma 5 (2017), Paper No. e15, 10 pp.
https://doi.org/10.1017/fms.2017.12

T. Tao: A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound, blog post, 2016, http://terrytao.wordpress.com/2016/05/18/a.

Metrics

0

Views

0

PDF views