29 problems

Let $M_3(n)$ denote the maximum size of a family $\mathcal{F}\subseteq\binom{[n]}{4}$ with $\operatorname{VC}(\mathcal{F})\le 3$. The paper establishes the lower bound … for every…

Let $\operatorname{GHD}_k^n$ be the partial sign matrix for the gap Hamming distance problem, and let $A$ be any total sign matrix obtained by replacing every $*$ entry of…

Let $[n]=\{1,\ldots,n\}$, let $0\leqslant s\leqslant d$, and let $\mathcal{F}\subseteq\binom{[n]}{d+1}$. An $s$-witness family is a family such that for every $F\in\mathcal{F}$ the…

Frankl's chain-free conjecture.

Chao–Xu–Yip–Zhang's conjecture.

Polynomial graph-partition conjecture. If $\mathcal{H}$ has bounded VC$_2$ dimension, then it has an $\varepsilon$-graph partition with $M=\operatorname{poly}(1/\varepsilon)$ many…

Let $\mathcal{H}$ be a $3$-graph with bounded VC$_2$ dimension, and let $\mathcal{Q}_V$ denote the vertex partition in the upper-bound theorem. Double-tower upper-bound conjecture.…

Mészáros–Rónyai conjecture. For every nonempty s-extremal family $\mathcal{F}\subseteq 2^{[n]}$, there exists $F_0\in\mathcal{F}$ such that $\mathcal{F}\setminus\{F_0\}$ is still s…

For every $D\geq 1$ and $\varepsilon>0$, there exists $\delta>0$ such that every $3$-partite $3$-graph $H$ of slicewise VC-dimension at most $D$ that is weakly $\delta$-regular sat…

Higher-residue conjecture. As $N\to\infty$ through the primes congruent to $1$ modulo $r$,

McDonald–Sahay–Wyman's conjecture. As $N\to\infty$ through the primes,

VC-dimension–blowup threshold conjecture. For any graph $H$,

Chernikov's VC-density conjecture. The following assertions hold:

Let $\mathcal{I}=(U,\mathcal{C'})$ be an ideal of a convex geometry, with Euclidean dimension $\operatorname{\dim_{\mathbb{E}}}(\mathcal{I})$ and VC-dimension…

Let $\mathcal{H}$ be a hereditary property of $3$-uniform hypergraphs with infinite $\operatorname{VC}_2$-dimension. Let $L_{\mathcal{H}}(\epsilon_1,\epsilon_2)$ denote the associa…

Maximum VC-dimension conjecture for power subgroups. One has

Maximum VC-dimension conjecture. One has

Let $q\geq 2$ be an integer, $M$ be an $L$-structure, and let $\varphi(x,y)$ be an $L(M)$-formula with dual shatter function $\pi_{\varphi}^*(n)\in o(n^q)$. A family of instances…

Uniform Dvir–Moran conjecture. One should have

Let $f^d_r(k)$ be the least positive integer $m$ such that every family $\mathcal F$ of $k$-sets with $|\mathcal F|\geq m$ and $\text{VC-dim}(\mathcal F)\leq d$ contains an $r$-sun…

Let $\mathcal H \subseteq \mathcal X\to\mathcal Y$ be a VC class of dimension $d$, and let $\mathcal A$ be a proper learning algorithm. For a distribution $\mathcal D$, write…

Let $\mathcal{X}$ be a domain, let $\mathcal{W}$ be a class of functions $f:\mathcal{X}\to\{0,1\}$ with VC dimension $d\geq 1$, and let $n\geq 1$. For a dataset…

Let $\mathcal{X}$ be a domain, let $\mathcal{W}$ be a class of functions $f:\mathcal{X}\to\{0,1\}$ with VC dimension $d\geq 1$, and let $n\geq 1$. For a dataset…

Let $\mathcal{X}$ be a domain, let $\mathcal{W}$ be a class of functions $f:\mathcal{X}\to\{0,1\}$ with VC dimension $d\geq 1$, and let $n\geq 1$. For a dataset…

Let $d\geq 2$. A graph has VC-dimension at most $d$ when its VC-dimension is bounded by $d$. Bounded-VC-dimension Erdős–Hajnal conjecture. There exists a constant $\varepsilon(d)$…