Definable (p,q)(p,q)-conjecture for formulas of VC-codensity less than qq

At least 3 years old · documented by

Let q≥2q\geq 2 be an integer, MM be an LL-structure, and let φ(x,y)\varphi(x,y) be an L(M)L(M)-formula with dual shatter function πφ∗(n)∈o(nq)\pi_{\varphi}^*(n)\in o(n^q). A family of instances {φ(x,a):a∈A}\{\varphi(x,a):a\in A\} has the (p,q)(p,q)-property if, among any pp instances, some qq have nonempty intersection. Definable (p,q)(p,q)-conjecture. If there exists an integer p≥qp\geq q such that φ(x,y)\varphi(x,y) has the (p,q)(p,q)-property, then there exists some m<ωm<\omega and L(M)L(M)-formulas ψ1(y),…,ψm(y)\psi_1(y),\ldots,\psi_m(y) such that, for every i≤mi\leq m, the family

{φ(x,a):a∈ψi(M)}\{\varphi(x,a):a\in\psi_i(M)\}

is consistent. This is the definable model-theoretic analogue of the Alon–Kleitman–Matoušek (p,q)(p,q)-theorem and strengthens the base case of the definable (p,q)(p,q)-conjecture; the source notes that the version commonly found in the literature assumes the stronger hypothesis that the whole structure is NIP.

References

Primary source

Pablo Andújar Guerrero, “Definable (ω, 2)-theorem for families with VC-codensity less than 2”, arXiv:2205.13665 (2023).

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.