The Frankl-Pach upper bound is not tight for any uniformity

Gennian Ge, Zixiang Xu, Chi Hoi Yip, Shengtong Zhang, Xiaochen Zhao · 2024

Read The Frankl-Pach upper bound is not tight for any uniformity by Gennian Ge, Zixiang Xu, Chi Hoi Yip, Shengtong Zhang, Xiaochen Zhao (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-11901.txt.

Introduction

Gennian Ge, Zixiang Xu, Chi Hoi Yip, Shengtong Zhang, and Xiaochen Zhao close a forty-year gap in extremal combinatorics. The question, posed by Frankl and Pach in 1984, asks how large a uniform set system on n elements can be if its VC-dimension stays below the uniformity. Frankl and Pach proved an upper bound, and in 2007 Mubayi and Zhao showed the bound was loose, but only when the dimension parameter was a prime power.

The new proof removes every extra assumption: for all dimensions at least two and all sufficiently large ground sets, the Frankl-Pach bound is not tight for any uniformity. The argument blends a polynomial method with structural analysis of the set system. The authors answer the standing question of whether new ideas could free the improvement from number-theoretic side conditions.

Catalog record

CREATORGennian Ge, Zixiang Xu, Chi Hoi Yip, Shengtong Zhang, Xiaochen Zhao
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE16 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-11901

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Frankl-Pach upper bound is not tight for any uniformity Gennian Ge, Zixiang Xu, Chi Hoi Yip, Shengtong Zhang, Xiaochen Zhao Abstract For any positive integers n ≥ d + 1 ≥ 3 n\geq d+1\geq 3 , what is the maximum size of a ( d + 1 ) (d+1) -uniform set system in [ n ] [n] with VC-dimension at most d d ? In 1984, Frankl and Pach initiated the study of this fundamental problem and provided an upper bound ( n d ) \binom{n}{d} via an elegant algebraic proof. Surprisingly, in 2007, Mubayi and Zhao showed that when n n is sufficiently large and d d is a prime power, the Frankl-Pach upper bound is not tight. They also remarked that their method requires d d to be a prime power, and asked for new ideas to improve the Frankl-Pach upper bound without extra assumptions on n n and d d . In this paper, we provide an improvement for any d ≥ 2 d\geq 2 and n ≥ 2 ​ d + 2 n\geq 2d+2 , which demonstrates that the long-standing Frankl-Pach upper bound ( n d ) \binom{n}{d} is not tight for any uniformity. Our proof combines a simple yet powerful polynomial method and structural analysis. 1 Introduction The Vapnik-Chervonenkis dimension ( VC-dimension ) is a cornerstone concept in statistical learning and machine learning. It quantifies the capacity of a set of functions and assesses a model’s potential to generalize beyond its training data. Widely applied in computational learning theory, artificial intelligence, and statistical inference, the VC-dimension plays a pivotal role in analyzing classification algorithms and evaluating the performance of machine learning models. Its formal definition is as follows. Definition 1.1 . Let \mathcal{F}\subseteq 2^{V} be a set system on the ground set V . The VC-dimension of \mathcal{F} is the largest size of subset S\subseteq V such that for every subset S^{\prime}\subseteq S , there exists a member F_{S^{\prime}}\in\mathcal{F} such that F_{S^{\prime}}\cap S=S^{\prime} . A natural question that arises is: What is the maximum size of a set system with a given VC-dimension? This fundamental question in the theory of VC-dimension was independently resolved in the 1970s by three different groups [ 17 , 18 , 20 ] . Lemma 1.2 . Let \mathcal{F}\subseteq 2^{V} be a set system with VC-dimension at most d , then |\mathcal{F}|\leq\sum\limits_{i=0}^{d}\binom{|V|}{i} . Furthermore, the upper bound in Lemma 1.2 is sharp, as shown by considering a Hamming ball with radius d . Lemma 1.2 also stands as an important result in extremal combinatorics. In particular, the connection between VC-dimension and extremal combinatorics has sparked significant excitement in recent years; see for example [ 3 , 6 , 7 , 8 , 13 , 16 , 19 ] . While Lemma 1.2 provides a tight upper bound for non-uniform set systems with a given VC-dimension, it is natural to investigate the maximum size of a uniform set system with small VC-dimension. Indeed, in the 1980s, Frankl and Pach [ 9 ] initiated the study of this fundamental problem and provided a clean upper bound with an elegant proof. Theorem 1.3 ( [ 9 ] ) . Let n,d be positive integers with n\geq d+1 . If \mathcal{F}\subseteq\binom{[n]}{d+1} is a set system with VC-dimension at most d , then |\mathcal{F}|\leq\binom{n}{d} . Frankl and Pach [ 9 ] as well Erdős [ 5 ] further conjectured that for sufficiently large n , the maximum value is \binom{n-1}{d} achieved when \mathcal{F} forms a star. However, two unexpected results emerged over the past four decades: (1) In 1997, Ahlswede and Khachatrian [ 1 ] disproved the above conjecture by constructing such a set system of size \binom{n-1}{d}+\binom{n-4}{d-2} when n\geq 2(d+1) . (2) In 2007, Mubayi and Zhao [ 15 ] cleverly combined the high-order inclusion matrix and the sunflower lemma to show that, when d=p^{t} for some prime p and positive integer t and n is sufficiently large relative to d , the size of such a set system is at most \binom{n}{d}-\log_{p}{n}+C_{d} , where C_{d} is related to the sunflower lemma [ 2 , 4 ] . They also remarked [ 15 , Proposition 10] that their method requires d to be a prime power, and claimed that improving the Frankl-Pach upper bound for other values of d will most likely require some new ideas. In this paper, we show that the upper bound in Theorem 1.3 can be improved for all positive integers n,d with d\geq 2 and n\geq 2d+2 . Theorem 1.4 . Let n,d be positive integers with d\geq 2 and n\geq 2d+2 . If \mathcal{F}\subseteq\binom{[n]}{d+1} is a set system with VC-dimension at most d , then |\mathcal{F}|<\binom{n}{d} . In particular the condition n\geq 2d+2 is optimal since when n=2d+1 , the upper bound \binom{n}{d} is achieved by \mathcal{F}=\binom{[n]}{d+1} , which was remarked by Frankl and Pach [ 9 ] . Our proof combines a simple yet powerful polynomial method with clean structural analysis. We begin with a concise proof of Theorem 1.3 in Section 2 as an introductory step, which we then refine to establish Theorem 1.4 in Section 3 . Notations. We usually regard [n]=\{1,2,\ldots,n\} as the ground set. For a subset A\subseteq[n] , we use \binom{A}{k} to denote the family of all subsets of A with size k and \binom{A}{\leq k} to denote the family of all subsets of A with size at most k ; we also use \bm{v}_{A}\in\{0,1\}^{n} to denote the characteristic vector of A . For a set system \mathcal{F} , we denote the k -shadow of \mathcal{F} as \partial_{k}{\mathcal{F}}:=\{T\in\binom{[n]}{k}:T\subseteq F\ \text{for\ some\ }F\in\mathcal{F}\} . We write \bm{x}=(x_{1},x_{2},\ldots,x_{n}) and use V_{n,d} to denote the vector space spanned by monomials in \mathbb{R}[\bm{x}] with degree at most d . 2 Warm-up: Frankl-Pach upper bound via polynomial method In this section, we provide an alternative proof of Theorem 1.3 using the multi-linear polynomial method. The following triangular criterion is useful for proving that a sequence of polynomials is linearly independent. Lemma 2.1 . Let f_{1},f_{2},\ldots,f_{m}\in\mathbb{R}[\bm{x}] . If \bm{v}^{(1)},\bm{v}^{(2)},\ldots,\bm{v}^{(m)} are vectors in \mathbb{R}^{n} such that f_{i}(\bm{v}^{(i)})\neq 0 for 1\leq i\leq m and f_{i}(\bm{v}^{(j)})=0 for i>j , then f_{1},f_{2},\ldots,f_{m} are linearly independent. We then build the following relationship between the size of \mathcal{F} and its d -shadow, which also implies the result in Theorem 1.3 . Theorem 2.2 . Let \mathcal{F}\subseteq\binom{[n]}{d+1} be a set system with VC-dimension at most d , then |\mathcal{F}|\leq|\partial_{d}\mathcal{F}| . We remark that Theorem 2.2 is of independent interest. For instance, it extends the celebrated Katona’s shadow theorem [ 10 ] , which asserts that any (d+1) -uniform intersecting family \mathcal{F} satisfies |\mathcal{F}|\leq|\partial_{d}\mathcal{F}| ; this follows from the fact that any such intersecting family has VC-dimension at most d . Proof of Theorem 2.2 . Let \mathcal{F}=\{F_{1},F_{2},\ldots,F_{m}\}\subseteq\binom{[n]}{d+1} be a set system with VC-dimension at most d . We now consider the following set systems and their corresponding polynomials. 1. Since the VC-dimension of \mathcal{F} is at most d , for each set F_{i}\in\mathcal{F} , there exists some B_{i} such that F_{i}\cap F\neq B_{i} for all F\in\mathcal{F} . For each F_{i}\in\mathcal{F} , let f_{F_{i}}(\bm{x})=\prod\limits_{j\in B_{i}}x_{j}\cdot\prod\limits_{j\in F_{i}\setminus B_{i}}(x_{j}-1)-\prod\limits_{j\in F_{i}}x_{j} . 2. Let \mathcal{H}=\binom{[n]}{\leq d-1} . For each set H\in\mathcal{H} , define h_{H}(\bm{x})=(\sum\limits_{j=1}^{n}x_{j}-d-1)\cdot\prod\limits_{j\in H}x_{j} . 3. Let

Read the complete text