

























Using techniques in \cite{chudnovsky2023erdHos} and substitution in \cite{alon2001ramsey}, we show that there is $ε>0$ such that for any graph $G$ with VC-dimension $\leq 2$, $G$ has a clique or an anti-clique of size $\geq |G|^ε$. We also show that Erdős-Hajnal property of VC-dimension $1$ graphs can be proved using $δ$-dimension technique in \cite{chernikov2018note}, and we show that when $E$ is a definable symmetric binary relation, \cite[Theorem 1.3]{chernikov2018note} can be proved without using Shelah's 2-rank..
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。