Nothing Special   »   [go: up one dir, main page]
Document Open Access Logo

Sunflowers in Set Systems of Bounded Dimension

Authors Jacob Fox, János Pach, Andrew Suk

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.37.pdf
  • Filesize: 0.59 MB
  • 13 pages

Document Identifiers

Author Details

Jacob Fox
  • Department of Mathematics, Stanford University, CA, USA
János Pach
  • Alfréd Rényi Institute of Mathematics, Budapest, Hungary
  • Moscow Institute of Physics and Technology, Moscow, Russia
Andrew Suk
  • Department of Mathematics, University of California San Diego, La Jolla, CA, USA

Funding

  • Fox, Jacob: Supported by a Packard Fellowship and by NSF award DMS-1855635.
  • Pach, János: Rényi Institute, Budapest and MIPT, Moscow. Supported by NKFIH grants K-176529, KKP-133864, Austrian Science Fund Z 342-N31, Ministry of Education and Science of the Russian Federation MegaGrant No. 075-15-2019-1926, ERC Advanced Grant "GeoScape."
  • Suk, Andrew: Supported by NSF CAREER award DMS-1800746, NSF award DMS-1952786, and an Alfred Sloan Fellowship.

Acknowledgements

We would like to thank Amir Yehudayoff for suggesting working with the Littlestone dimension, and the SoCG 2021 referees for helpful comments.

Cite As Get BibTex

Jacob Fox, János Pach, and Andrew Suk. Sunflowers in Set Systems of Bounded Dimension. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 37:1-37:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.SoCG.2021.37

Abstract

Given a family F of k-element sets, S₁,…,S_r ∈ F form an r-sunflower if S_i ∩ S_j = S_{i'} ∩ S_{j'} for all i ≠ j and i' ≠ j'. According to a famous conjecture of Erdős and Rado (1960), there is a constant c = c(r) such that if |F| ≥ c^k, then F contains an r-sunflower.
We come close to proving this conjecture for families of bounded Vapnik-Chervonenkis dimension, VC-dim(F) ≤ d. In this case, we show that r-sunflowers exist under the slightly stronger assumption |F| ≥ 2^{10k(dr)^{2log^{*} k}}. Here, log^* denotes the iterated logarithm function.
We also verify the Erdős-Rado conjecture for families F of bounded Littlestone dimension and for some geometrically defined set systems.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatoric problems
Keywords
  • Sunflower
  • VC-dimension
  • Littlestone dimension
  • pseudodisks

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. H. L. Abbott, D. Hanson, and N. Sauer. Intersection theorems for systems of sets. J. Combin. Theory Ser. A, 12:381-389, 1972. Google Scholar
  2. M. Ajtai, V. Chvátal, M.M. Newborn, and E. Szemerédi. Crossing-free subgraphs. In Peter L. Hammer, Alexander Rosa, Gert Sabidussi, and Jean Turgeon, editors, Theory and Practice of Combinatorics, volume 60 of North-Holland Mathematics Studies, pages 9-12. North-Holland, 1982. URL: https://doi.org/10.1016/S0304-0208(08)73484-4.
  3. N. Alon and R. Holzman. Near-sunflowers and focal families. arXiv, 2020. URL: http://arxiv.org/abs/2010.05992.
  4. N. Alon, R. Livni, M. Malliaris, and S. Moran. Private pac learning implies finite littlestone dimension. STOC, pages 852-860, 2019. Google Scholar
  5. R. Alweiss, S. Lovet, K. Wu, and J. Zhang. Improved bounds for the sunflower lemma. arXiv, 2020. URL: http://arxiv.org/abs/1908.08483.
  6. S. Ben-David, D. Pál, and S. Shalev-Shwartz. Agnostic online learning. COLT, 2009. Google Scholar
  7. S. Buzaglo, R. Holzman, and R. Pinchasi. On s-intersecting curves and related problems. Symposium on Computational Geometry, pages 79-84, 2008. Google Scholar
  8. H. Chase and J. Freitag. Model theory and machine learning. Bull. Symb. Log., 25:319-332, 2019. Google Scholar
  9. K. L. Clarkson. Applications of random sampling in computational geometry, ii. Symposium on Computational Geometry, pages 1-11, 1988. Google Scholar
  10. G. Ding, P. Seymour, and P. Winkler. Bounding the vertex cover number of a hypergraph. Combinatorica, 14:23-34, 1994. Google Scholar
  11. P. Erdős and R. Rado. Intersection theorems for systems of sets. J. London Math. Soc., 35:85-90, 1960. Google Scholar
  12. J. Fox, J. Pach, and A. Suk. Erdős-Hajnal conjecture for graphs with bounded VC-dimension. Discrete Comput. Geom., 61:809-829, 2019. Google Scholar
  13. J. Fox, J. Pach, and A. Suk. Bounded VC-dimension implies the Schur-Erdős conjecture. Symposium on Computational Geometry, pages 46:1-46:8, 2020. Google Scholar
  14. A. V. Kostochka. An intersection theorem for systems of sets. Random Structures Algorithms, 9:213-221, 1996. Google Scholar
  15. N. Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Mach. Learn., 2:285-318, 1987. Google Scholar
  16. E. Naslund and W. Sawin. Upper bounds for sunflower-free sets. Forum Math. Sigma, e15:10 pp., 2017. Google Scholar
  17. P. Erdős and E. Szemerédi. Combinatorial properties of systems of sets. J. Combin. Theory Ser. A, 24:308-313, 1978. Google Scholar
  18. J. Pach and P. Agarwal. Combinatorial Geometry. Wiley-Interscience, New York, 1995. Google Scholar
  19. A. Rao. Coding for sunflowers. Discrete Anal., 2:8 pp., 2020. Google Scholar
  20. N. Sauer. On the density of families of sets. J. Combinat. Theory Ser. A, 13:145-147, 1972. Google Scholar
  21. M. Sharir. On k-sets in arrangements of curves and surfaces. Discrete Comput. Geom., 6:593-617, 1991. Google Scholar
  22. S. Shelah. A combinatorial problem, stability and order for models and theories in infinitary languages. Pacific J. Math., 41:247-261, 1972. Google Scholar
  23. S. Smorodinsky and M. Sharir. Selecting points that are heavily covered by pseudo-circles, spheres or rectangles. Combin. Probab. Comput., 13:389-411, 2004. Google Scholar
  24. V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl., 16:264-280, 1971. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact