Fox, Jacob and Pach, János and Suk, Andrew (2021) Sunflowers in set systems of bounded dimension. In: 37th International Symposium on Computational Geometry, SoCG 2021. Leibniz-Zentrum für Informatik, Wadern, pp. 571-583. ISBN 9783959771849
|
Text
lipics-vol189-socg2021-complete_-571-583.pdf Available under License Creative Commons Attribution. Download (318kB) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.37
Abstract
Given a family F of k-element sets, S1,..., Sr ∈ F form an r-sunflower if Si ∩ Sj = Si′ ∩ Sj′ 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| ≥ ck, 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| ≥ 210k(dr)2 log∗ 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. © Jacob Fox, János Pach, and Andrew Suk; licensed under Creative Commons License CC-BY 4.0 37th International Symposium on Computational Geometry (SoCG 2021).
| Item Type: | Book Section |
|---|---|
| Additional Information: | Department of Mathematics, Stanford UniversityCA, United States Alfréd Rényi Institute of Mathematics, Budapest, Hungary Moscow Institute of Physics and Technology, Moscow, Russian Federation Department of Mathematics, University of California San Diego, San Diego, CA, United States Conference code: 169534 Export Date: 20 September 2021 Correspondence Address: Fox, J.; Department of Mathematics, United States Correspondence Address: Pach, J.; Alfréd Rényi Institute of MathematicsHungary Correspondence Address: Suk, A.; Department of Mathematics, United States Funding details: National Science Foundation, NSF, 1800746, 1952786, DMS-1855635 Funding details: European Research Council, ERC, DMS-1800746, DMS-1952786 Funding details: Austrian Science Fund, FWF, Z 342-N31 Funding details: Ministry of Education and Science of the Russian Federation, Minobrnauka, 075-15-2019-1926 Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH, K-176529, KKP-133864 Funding details: Moscow Institute of Physics and Technology, MIPT Funding text 1: Jacob Fox: Supported by a Packard Fellowship and by NSF award DMS-1855635. J?nos Pach: 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.? Andrew Suk: Supported by NSF CAREER award DMS-1800746, NSF award DMS-1952786, and an Alfred Sloan Fellowship. Funding text 2: Funding Jacob Fox: Supported by a Packard Fellowship and by NSF award DMS-1855635. János Pach: 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.” Andrew Suk: Supported by NSF CAREER award DMS-1800746, NSF award DMS-1952786, and an Alfred Sloan Fellowship. Department of Mathematics, Stanford UniversityCA, United States Alfréd Rényi Institute of Mathematics, Budapest, Hungary Moscow Institute of Physics and Technology, Moscow, Russian Federation Department of Mathematics, University of California San Diego, San Diego, CA, United States Conference code: 169534 Export Date: 22 September 2021 Correspondence Address: Fox, J.; Department of Mathematics, United States Correspondence Address: Pach, J.; Alfréd Rényi Institute of MathematicsHungary Correspondence Address: Suk, A.; Department of Mathematics, United States Funding details: National Science Foundation, NSF, 1800746, 1952786, DMS-1855635 Funding details: European Research Council, ERC, DMS-1800746, DMS-1952786 Funding details: Austrian Science Fund, FWF, Z 342-N31 Funding details: Ministry of Education and Science of the Russian Federation, Minobrnauka, 075-15-2019-1926 Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH, K-176529, KKP-133864 Funding details: Moscow Institute of Physics and Technology, MIPT Funding text 1: Jacob Fox: Supported by a Packard Fellowship and by NSF award DMS-1855635. J?nos Pach: 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.? Andrew Suk: Supported by NSF CAREER award DMS-1800746, NSF award DMS-1952786, and an Alfred Sloan Fellowship. Funding text 2: Funding Jacob Fox: Supported by a Packard Fellowship and by NSF award DMS-1855635. János Pach: 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.” Andrew Suk: Supported by NSF CAREER award DMS-1800746, NSF award DMS-1952786, and an Alfred Sloan Fellowship. Department of Mathematics, Stanford UniversityCA, United States Alfréd Rényi Institute of Mathematics, Budapest, Hungary Moscow Institute of Physics and Technology, Moscow, Russian Federation Department of Mathematics, University of California San Diego, San Diego, CA, United States Conference code: 169534 Export Date: 23 September 2021 Correspondence Address: Fox, J.; Department of Mathematics, United States Correspondence Address: Pach, J.; Alfréd Rényi Institute of MathematicsHungary Correspondence Address: Suk, A.; Department of Mathematics, United States Funding details: National Science Foundation, NSF, 1800746, 1952786, DMS-1855635 Funding details: European Research Council, ERC, DMS-1800746, DMS-1952786 Funding details: Austrian Science Fund, FWF, Z 342-N31 Funding details: Ministry of Education and Science of the Russian Federation, Minobrnauka, 075-15-2019-1926 Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH, K-176529, KKP-133864 Funding details: Moscow Institute of Physics and Technology, MIPT Funding text 1: Jacob Fox: Supported by a Packard Fellowship and by NSF award DMS-1855635. J?nos Pach: 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.? Andrew Suk: Supported by NSF CAREER award DMS-1800746, NSF award DMS-1952786, and an Alfred Sloan Fellowship. Funding text 2: Funding Jacob Fox: Supported by a Packard Fellowship and by NSF award DMS-1855635. János Pach: 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.” Andrew Suk: Supported by NSF CAREER award DMS-1800746, NSF award DMS-1952786, and an Alfred Sloan Fellowship. |
| Uncontrolled Keywords: | SILICON; sunflower; VC-dimension; Computational geometry; Set theory; K elements; Set system; Vapnik-Chervonenkis dimensions; Littlestone dimension; Pseudodisks; Logarithm function; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 22 Nov 2023 17:03 |
| Last Modified: | 22 Nov 2023 17:03 |
| URI: | http://real.mtak.hu/id/eprint/180684 |
Actions (login required)
 |
Edit Item |
