Submission date: 26 October 2023

Abstract:

We show that for each integer d ≥ 2, the family ℱ_d= {G=(V,E):G and Ḡ have no d-tuple (a_1,...,a_d) satisfying that there exists {b_{ij}}_{1 ≤ i < j ≤ d} such that for all i,j ∈ {1,...,d}, E(b_{ij},a_i) ∧ E(b_{ij},a_j) ∧ ⋀_{k ≠ i,j} ¬ E(b_{ij},a_k)} has Erdős-Hajnal property. In particular, if T is a dp-minimal theory, ℳ ⊧ T and E a definable symmetric binary relation, then the family {G=(V,E): V ⊆ M a finite set and for every two vertices x,y ∈ V, E(x,y) iff ℳ ⊧ E(x,y)} has Erdős-Hajnal property. As a corollary, Erdős-Hajnal property holds for VC-density 1 graphs.

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 2310.17730: pdf, ps.