65 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 $n$ and $d$ be positive integers, and let $\mathcal{F}\subseteq\binom{[n]}{d+1}$ be a $(d+1)$-uniform family with VC-dimension at most $d$. Erdős–Frankl–Pach conjecture. When…

Let $G=(S,E)$ be a subgraph of the Cartesian product … of graphs $G_1,\ldots,G_m$, and let $\operatorname{VC\text{-}dens}(S)$ denote the VC-density of $S$. VC-density conjecture. T…

Let $0\le s\le d$, and let $\mathcal{F}\subseteq\binom{[n]}{d+1}$ be an $s$-witness family, meaning that for every $F\in\mathcal{F}$ there exists $B_F\in\binom{F}{s}$ such that…

Let $[n]=\{1,\ldots,n\}$, and let $\mathcal{F}\subseteq\binom{[n]}{d+1}$ be a $(d+1)$-uniform set family. Its VC-dimension is the largest size of a set $S\subseteq[n]$ such that ev…

Doubly exponential upper-bound conjecture. A doubly exponential upper bound on $\textup{VC}(F)$ holds in the general setting.

Let $d\ge 0$ and $n\ge d+1$, and let $M_d(n)$ be the maximum size of a family $\mathcal{F}\subseteq\binom{[n]}{d+1}$ with $\operatorname{VC}(\mathcal{F})\le d$. A star is the famil…

In the proper positive-only learning model, let a concept class be intersection-closed if it is closed under arbitrary intersections of its concepts. Natarajan's characterization c…

Mubayi–Zhao conjecture. For all sufficiently large $n$, $M_d(n)=\operatorname{AK}_d(n)$. The paper proves that this conjecture is false for every $d\ge 3$ by constructing families…

Let $0C$ be a concept class of VC-dimension $d$. A concept class is maximum when, for every finite subset of its domain, it realizes all traces permitted by its VC-dimension.…

Let $H$ be a hypergraph of VC-dimension $d$. A sample compression scheme for $H$ consists of a compression map and reconstruction map that encode every finite sample from $H$ using…

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…

Let $Q_n=(\{0,1\}^n,E)$ be the $n$-dimensional discrete hypercube, and let $\mathcal{F}\subseteq V(Q_n)$ induce a subgraph with minimum degree $\delta$. Write…

Let $F4F1\mathcal{F}\subseteq\{0,1\}^n$ be a $d$-maximum class, and consider its one-inclusion graph. The Peeling algorithm repeatedly removes a vertex of minimum degree and record…

Bounded VCN-dimension conjecture. The resulting hypothesis class should have bounded $\operatorname{VCN}_{2,2}$-dimension.

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,

Let $S\subseteq \\{0,1\\}^n$ be a cube-ideal set-system with connectivity $\lambda$, where $\lambda\geq 3$. Its VC dimension is the largest integer $d$ such that the projection of…

Let $\mathcal{C}$ be a concept class of VC dimension $d$ defined on a finite domain $\mathcal{X}$. The Recursive Teaching Dimension is the parameter obtained by recursively removin…