This content will become publicly available on December 1, 2026

Title: Sunflowers in Set Systems with Small VC-Dimension
Abstract A family ofrdistinct sets$$\{A_1,\ldots , A_r\}$$ { A 1 , , A r } is anr-sunflower if for all$$1 \leqslant i < j\leqslant r$$ 1 i < j r and$$1 \leqslant i' < j'\leqslant r$$ 1 i < j r , we have$$A_i\cap A_j = A_{i'}\cap A_{j'}$$ A i A j = A i A j . Erdős and Rado conjectured in 1960 that every family$$\mathcal {H}$$ H of$$\ell $$ -element sets of size at least$$K(r)^\ell $$ K ( r ) contains anr-sunflower, whereK(r) is some function that depends only onr. We prove that if$$\mathcal {H}$$ H is a family of$$\ell $$ -element sets of VC-dimension at mostdand$$|\mathcal H| > (C r(\log d+\log ^*\ell ))^\ell $$ | H | > ( C r ( log d + log ) ) for some absolute constant$$C > 0$$ C > 0 , then$$\mathcal {H}$$ H contains anr-sunflower. This improves a recent result of Fox, Pach, and Suk. When$$d=1$$ d = 1 , we obtain a sharp bound, namely that$$|\mathcal H| > (r-1)^\ell $$ | H | > ( r - 1 ) is sufficient. Along the way, we establish a strengthening of the Kahn–Kalai conjecture for set families of bounded VC-dimension, which is of independent interest.  more » « less
Award ID(s):
2528522 2152488 1937241
PAR ID:
10688180
Author(s) / Creator(s):
; ; ; ;
Publisher / Repository:
Springer
Date Published:
Journal Name:
Combinatorica
Volume:
45
Issue:
6
ISSN:
0209-9683
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract We study holomorphic mapsFfrom a smooth Levi non-degenerate real hypersurface$$ M_{\ell }\subset {\mathbb {C}}^n $$ M C n into a hyperquadric$$ {\mathbb {H}}_{\ell '}^N $$ H N with signatures$$ \ell \le (n-1)/2 $$ ( n - 1 ) / 2 and$$ \ell '\le (N-1)/2,$$ ( N - 1 ) / 2 , respectively. Assuming that$$ N - n < n - 1,$$ N - n < n - 1 , we prove that if$$ \ell = \ell ',$$ = , thenFis either CR transversal to$$ {\mathbb {H}}_{\ell }^N $$ H N at every point of$$ M_{\ell },$$ M , or it maps a neighborhood of$$ M_{\ell } $$ M in$$ {\mathbb {C}}^n $$ C n into$$ {\mathbb {H}}_{\ell }^N.$$ H N . Furthermore, in the case where$$ \ell ' > \ell ,$$ > , we show that ifFis not CR transversal at$$0\in M_\ell ,$$ 0 M , then it must be transversally flat. The latter is best possible. 
    more » « less
  2. Abstract For the partition functionp(n), Ramanujan proved the striking identities$$\begin{aligned} \begin{aligned} \mathcal {P}_5(q):=\sum _{n\ge 0} p(5n+4)q^n&=5\prod _{n\ge 1} \frac{\left( q^5;q^5\right) _{\infty }^5}{(q;q)_{\infty }^6},\\ \mathcal {P}_{7}(q):=\sum _{n\ge 0} p(7n+5)q^n&=7\prod _{n\ge 1}\frac{\left( q^7;q^7\right) _{\infty }^3}{(q;q)_{\infty }^4}+49q \prod _{n\ge 1}\frac{\left( q^7;q^7\right) _{\infty }^7}{(q;q)_{\infty }^8}, \end{aligned} \end{aligned}$$ P 5 ( q ) : = n 0 p ( 5 n + 4 ) q n = 5 n 1 q 5 ; q 5 5 ( q ; q ) 6 , P 7 ( q ) : = n 0 p ( 7 n + 5 ) q n = 7 n 1 q 7 ; q 7 3 ( q ; q ) 4 + 49 q n 1 q 7 ; q 7 7 ( q ; q ) 8 , where$$(q;q)_{\infty }:=\prod _{n\ge 1}(1-q^n).$$ ( q ; q ) : = n 1 ( 1 - q n ) . As these identities imply his celebrated congruences modulo 5 and 7, it is natural to seek, for primes$$\ell \ge 5,$$ 5 , closed form expressions of the power series$$ \mathcal {P}_{\ell }(q):=\sum _{n\ge 0} p(\ell n-\delta _{\ell })q^n\pmod {\ell }, $$ P ( q ) : = n 0 p ( n - δ ) q n ( mod ) , where$$\delta _{\ell }:=\frac{\ell ^2-1}{24}.$$ δ : = 2 - 1 24 . In this paper, we prove that$$ \mathcal {P}_{\ell }(q)\equiv c_{\ell } \dfrac{\mathcal {T}_{\ell }(q)}{\left( q^\ell ; q^\ell \right) _\infty } \pmod {\ell }, $$ P ( q ) c T ( q ) q ; q ( mod ) , where$$c_{\ell }\in \mathbb Z$$ c Z is explicit and$${\mathcal {T}}_{\ell }(q)$$ T ( q ) is the generating function for the Hecke traces of$$\ell $$ -ramified values of special Dirichlet series for weight$$\ell -1$$ - 1 cusp forms on$$\textrm{SL}_2(\mathbb Z)$$ SL 2 ( Z ) . This is a new proof of Ramanujan’s congruences modulo 5, 7, and 11, as there are no nontrivial cusp forms of weight 4, 6, and 10. 
    more » « less
  3. Abstract LetXbe a compact normal complex space of dimensionnandLbe a holomorphic line bundle onX. Suppose that$$\Sigma =(\Sigma _1,\ldots ,\Sigma _\ell )$$ Σ = ( Σ 1 , , Σ ) is an$$\ell $$ -tuple of distinct irreducible proper analytic subsets ofX,$$\tau =(\tau _1,\ldots ,\tau _\ell )$$ τ = ( τ 1 , , τ ) is an$$\ell $$ -tuple of positive real numbers, and let$$H^0_0(X,L^p)$$ H 0 0 ( X , L p ) be the space of holomorphic sections of$$L^p:=L^{\otimes p}$$ L p : = L p that vanish to order at least$$\tau _jp$$ τ j p along$$\Sigma _j$$ Σ j ,$$1\le j\le \ell $$ 1 j . If$$Y\subset X$$ Y X is an irreducible analytic subset of dimensionm, we consider the space$$H^0_0 (X|Y, L^p)$$ H 0 0 ( X | Y , L p ) of holomorphic sections of$$L^p|_Y$$ L p | Y that extend to global holomorphic sections in$$H^0_0(X,L^p)$$ H 0 0 ( X , L p ) . Assuming that the triplet$$(L,\Sigma ,\tau )$$ ( L , Σ , τ ) is big in the sense that$$\dim H^0_0(X,L^p)\sim p^n$$ dim H 0 0 ( X , L p ) p n , we give a general condition onYto ensure that$$\dim H^0_0(X|Y,L^p)\sim p^m$$ dim H 0 0 ( X | Y , L p ) p m . WhenLis endowed with a continuous Hermitian metric, we show that the Fubini-Study currents of the spaces$$H^0_0(X|Y,L^p)$$ H 0 0 ( X | Y , L p ) converge to a certain equilibrium current onY. We apply this to the study of the equidistribution of zeros inYof random holomorphic sections in$$H^0_0(X|Y,L^p)$$ H 0 0 ( X | Y , L p ) as$$p\rightarrow \infty $$ p
    more » « less
  4. Abstract Let$$p_{1},\ldots ,p_{n}$$ p 1 , , p n be a set of points in the unit square and let$$T_{1},\ldots ,T_{n}$$ T 1 , , T n be a set of$$\delta $$ δ -tubes such that$$T_{j}$$ T j passes through$$p_{j}$$ p j . We prove a lower bound for the number of incidences between the points and tubes under a natural regularity condition (similar to Frostman regularity). As a consequence, we show that in any configuration of points$$p_{1},\ldots , p_{n} \in [0,1]^{2}$$ p 1 , , p n [ 0 , 1 ] 2 along with a line$$\ell _{j}$$ j through each point$$p_{j}$$ p j , there exist$$j\neq k$$ j k for which$$d(p_{j}, \ell _{k}) \lesssim n^{-2/3+o(1)}$$ d ( p j , k ) n 2 / 3 + o ( 1 ) . It follows from the latter result that any set of$$n$$ n points in the unit square contains three points forming a triangle of area at most$$n^{-7/6+o(1)}$$ n 7 / 6 + o ( 1 ) . This new upper bound for Heilbronn’s triangle problem attains the high-low limit established in our previous work arXiv:2305.18253. 
    more » « less
  5. Abstract Let$$\mathbb {F}_q^d$$ F q d be thed-dimensional vector space over the finite field withqelements. For a subset$$E\subseteq \mathbb {F}_q^d$$ E F q d and a fixed nonzero$$t\in \mathbb {F}_q$$ t F q , let$$\mathcal {H}_t(E)=\{h_y: y\in E\}$$ H t ( E ) = { h y : y E } , where$$h_y:E\rightarrow \{0,1\}$$ h y : E { 0 , 1 } is the indicator function of the set$$\{x\in E: x\cdot y=t\}$$ { x E : x · y = t } . Two of the authors, with Maxwell Sun, showed in the case$$d=3$$ d = 3 that if$$|E|\ge Cq^{\frac{11}{4}}$$ | E | C q 11 4 andqis sufficiently large, then the VC-dimension of$$\mathcal {H}_t(E)$$ H t ( E ) is 3. In this paper, we generalize the result to arbitrary dimension by showing that the VC-dimension of$$\mathcal {H}_t(E)$$ H t ( E ) isdwhenever$$E\subseteq \mathbb {F}_q^d$$ E F q d with$$|E|\ge C_d q^{d-\frac{1}{d-1}}$$ | E | C d q d - 1 d - 1
    more » « less