The improved uniform bound for families with bounded symmetric-difference VC-dimension

From papers

Let d<nd<n be positive integers with dot\bequivr(mod2)d ot\bequiv r \pmod 2 for some r{0,1}r\in\{0,1\}. Let F\mathcal F be a uniform family of subsets of [n][n] such that the VC-dimension of its symmetric-difference family satisfies

Vdim(FΔF)d.\operatorname{Vdim}(\mathcal F\mathbin{\Delta}\mathcal F)\leq d.

Uniform Dvir–Moran conjecture. One should have

F2r(nrd/2).|\mathcal F|\leq 2^r\binom{n-r}{\lfloor d/2\rfloor}.

The paper presents this as the best form of its preceding theorem, refining the general bound for uniform families with bounded symmetric-difference VC-dimension. The statement is given as a conjecture in the concluding remarks, and no resolution is supplied in the source.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Gábor Hegedüs, “An uniform version of Dvir and Moran's theorem”, arXiv:2105.04159 (2021).

Solutions 0

No solutions have been posted yet.