On the shatter function of semilinear set systems

2025/01/17 by Abdul Basit, Chieu-Minh Tran, Basit, Abdul +1
Mathematics · #03C45 #03C64 #05C65 #52C45 #Advanced Differential Equations and Dynamical Systems #Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO)

paper · pdf · doi:10.48550/arxiv.2501.10032

openalex publication_date 2025/01/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the shatter function of a semilinear set system on ℝ^m is asymptotic to a polynomial. This confirms, for the structure (ℝ; +, <), a conjecture of Chernikov and is a step towards characterizing model-theoretic linearity via shatter functions.

Related

• Shatter functions with polynomial growth rates
• Standard monomials and extremal point sets
• Shattering-Extremal Systems
• Shattering-extremal set systems of small VC-dimension
• Shattering-extremal set systems of VC dimension at most 2