Submission date: 25 October 2023

Abstract:

Using techniques in [chudnovsky2023erdHos] and substitution in [alon2001ramsey], we show that there is ε > 0 such that for any graph G with VC-dimension ≤ 2, G has a clique or an anti-clique of size ≥ |G|^ε. We also show that Erdős-Hajnal property of VC-dimension 1 graphs can be proved using δ-dimension technique in [chernikov2018note], and we show that when E is a definable symmetric binary relation, Theorem 1.3 of [chernikov2018note] can be proved without using Shelah's 2-rank..

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 2310.16970: pdf, ps.