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

About 5 years old · traced to

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

∣F∣≤2r(n−r⌊d/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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.