# Beyond chromatic threshold via $(p,q)$-theorem, and sharp blow-up phenomenon

Hong Liu Extremal Combinatorics and Probability Group (ECOPRO), Institute for
Basic Science (IBS), Daejeon, South Korea. Emails: {hongliu,
<EMAIL_ADDRESS>Supported by IBS-R029-C4. Chong Shangguan Research
Center for Mathematics and Interdisciplinary Sciences, Shandong University,
Qingdao 266237, China, and the Frontiers Science Center for Nonlinear
Expectations, Ministry of Education, Qingdao 266237, China. Email:
<EMAIL_ADDRESS>Supported by the National Natural Science Foundation of
China under Grant Nos. 12101364 and 12231014, and the Natural Science
Foundation of Shandong Province under Grant No. ZR2021QA005. Jozef Skokan
Department of Mathematics, London School of Economics, Houghton Street, London
WC2A 2AE, UK. Email<EMAIL_ADDRESS>Zixiang Xu11footnotemark: 1

###### Abstract

We establish a novel connection between the well-known chromatic threshold
problem in extremal combinatorics and the celebrated $(p,q)$-theorem in
discrete geometry. In particular, for a graph $G$ with bounded clique number
and a natural density condition, we prove a $(p,q)$-theorem for an abstract
convexity space associated with $G$. Our result strengthens those of Thomassen
and Nikiforov on the chromatic threshold of cliques. Our $(p,q)$-theorem can
also be viewed as a $\chi$-boundedness result for (what we call) ultra maximal
$K_{r}$-free graphs.

We further show that the graphs under study are blow-ups of constant size
graphs, improving a result of Oberkampf and Schacht on homomorphism threshold
of cliques. Our result unravels the cause underpinning such a blow-up
phenomenon, differentiating the chromatic and homomorphism threshold problems
for cliques. Our result implies that for the homomorphism threshold problem,
rather than the minimum degree condition usually considered in the literature,
the decisive factor is a clique density condition on co-neighborhoods of
vertices. More precisely, we show that if an $n$-vertex $K_{r}$-free graph $G$
satisfies that the common neighborhood of every pair of non-adjacent vertices
induces a subgraph with $K_{r-2}$-density at least $\varepsilon>0$, then $G$
must be a blow-up of some $K_{r}$-free graph $F$ on at most
$2^{O(\frac{r}{\varepsilon}\log\frac{1}{\varepsilon})}$ vertices. Furthermore,
this single exponential bound is optimal. We construct examples with no
$K_{r}$-free homomorphic image of size smaller than
$2^{\Omega_{r}(\frac{1}{\varepsilon})}$.

##  1 Introduction

###  1.1 Overview

Finding sufficient conditions guaranteeing a graph to have bounded complexity
has long been a popular topic in combinatorics and theoretical computer
science. There are many natural ways to measure complexity. In this paper, the
invariant we are interested in is the chromatic number, and we focus on graphs
with bounded clique number. Note that graphs with bounded clique number could
have arbitrarily large chromatic number: as one of the famous early
applications of probabilistic method in combinatorics, Erdős [19] in 1959
constructed a graph with arbitrarily large girth (hence triangle-free) and
chromatic number.

The density condition is a natural one to impose to guarantee constant
chromatic number. Turán’s theorem [55], a fundamental result in extremal graph
theory, states that every $n$-vertex $K_{r}$-free graph contains at most
$\frac{r-2}{r-1}\cdot\frac{n^{2}}{2}$ edges, and, moreover, the balanced
complete $(r-1)$-partite graph, also known as the Turán graph $T_{n,r-1}$, is
the unique extremal graph. Rephrasing Turán’s theorem, we see that every
$n$-vertex $K_{r}$-free graph $G$ with $e(G)\geq e(T_{n,r-1})$ must be
$T_{n,r-1}$ and hence $(r-1)$-colorable. However, the number of edges $e(G)$
is not an ideal density condition. Indeed, if $e(G)$ drops slightly below
$e(T_{n,r-1})$, although by a stability theorem of Erdős and Simonovits [22,
51], we know that $G$ is close to $T_{n,r-1}$ (in edit-distance), but $G$
could still have large chromatic number due to small noise, e.g. $G$ could be
a disjoint union of $T_{n-o(n),r-1}$ and an Erdős’ graph mentioned above on
$o(n)$ vertices. Notice that in both this example and the graph from random
construction of Erdős, there are vertices with small degree. Motivated by this
observation, Andrásfai, Erdős, and Sós [5] initiated the study of the
relationship between the chromatic number and the minimum degree of a
$K_{r}$-free graph. They showed that every $n$-vertex $K_{r}$-free graph with
minimum degree larger than $\frac{3r-7}{3r-4}\cdot n$ has chromatic number at
most $r-1$. It remained an interesting question to determine the optimal min-
degree condition guaranteeing bounded chromatic number. This is the by-now
well-known _chromatic threshold_ problem first formulated in the early 1970s
by Erdős and Simonovits [21], and since then there has been a large amount of
work on this topic. Formally, for a graph $H$, its chromatic threshold is
defined as

$\delta_{\chi}(H):=\inf\big{\\{}\alpha\geq 0:\exists\leavevmode\nobreak\
C=C(\alpha,H)\ \textup{s.t.\leavevmode\nobreak\ }\forall\leavevmode\nobreak\
n\textup{-vertex\ }H\textup{-free}\leavevmode\nobreak\ G,\leavevmode\nobreak\
\delta(G)\geq\alpha n\Rightarrow\chi(G)\leq C\big{\\}}.$

In other words, for $\alpha<\delta_{\chi}(H)$, there exist $H$-free graphs
with minimum degree $\alpha n$ and arbitrarily large chromatic number, but if
$\alpha>\delta_{\chi}(H)$, then $\chi(G)$ must be bounded.

For the first non-trivial case when $H$ is a triangle, a beautiful
construction of Hajnal using the Kneser graph shows that
$\delta_{\chi}(K_{3})\geq\frac{1}{3}$ (see [21]); this example can be easily
extended to obtain $\delta_{\chi}(K_{r})\geq\frac{2r-5}{2r-3}$. It was not
until 2002 that Thomassen [53] proved that Hajnal’s construction is optimal:
$\delta_{\chi}(K_{3})=\frac{1}{3}$, as conjectured by Erdős and Simonovits
[21]. Later, the chromatic thresholds for all cliques
$\delta_{\chi}(K_{r})=\frac{2r-5}{2r-3}$ were determined by Goddard and Lyle
[24] and independently by Nikiforov [45]. After a series of results (see,
e.g., [10, 12, 13, 26, 32, 38]), the culmination is the remarkable work of
Allen, Böttcher, Griffiths, Kohayakawa, and Morris [1], which determined the
chromatic thresholds for all graphs $H$.

One of our main contributions is to study the chromatic threshold problem
through a geometric perspective, establishing a surprising connection between
this classical problem in extremal combinatorics and the celebrated
$(p,q)$-theorem in discrete geometry. We will elaborate more on this in the
next subsection. Below is our first result.

######  Theorem 1.1.

Let $r\geq 3$, $\varepsilon>0$ and $G$ be an $n$-vertex $K_{r}$-free graph. If
for every non-adjacent pair of vertices $u,v\in V(G)$, the induced subgraph
$G[N(u)\cap N(v)]$ contains at least $\varepsilon n^{r-2}$ copies of
$K_{r-2}$, then $\chi(G)=O_{r,\varepsilon}(1)$.

Our theorem implies and extends the results of Thomassen [53], Goddard and
Lyle [24], and Nikiforov [45] as the above clique density condition in the co-
neighborhoods is a strictly weaker condition than the minimum degree condition
in $\delta_{\chi}(K_{r})$; see the discussion in Section 1.4.

Throughout the rest of this paper, we will refer the graphs in Theorem 1.1 as
_$\varepsilon$ -ultra maximal $K_{r}$-free graphs_.

###  1.2 Chromatic threshold meets $(p,q)$-theorem

In 1921, Radon [49] proved his fundamental lemma in combinatorial convexity
which states that any set of $d+2$ points in ${\mathbbm{R}}^{d}$ can be
partitioned into two parts whose convex hulls intersect. Radon’s lemma was
introduced to prove Helly’s theorem [29], yet another fundamental result in
convexity. Helly’s theorem is a local-global type result, stating that for any
finite family of convex sets in ${\mathbbm{R}}^{d}$, if every $d+1$ of them
intersect, then all of them intersect. Since then, many generalizations have
been developed. We refer the readers to [8, 9, 14, 18]. One of the important
extensions, due to Katchalski and Liu [33], is the fractional Helly theorem.
It states that if in a finite family of convex sets in ${\mathbbm{R}}^{d}$, a
positive fraction of $(d+1)$-tuples intersect, then a positive fraction of all
sets intersect. For $p\geq q$, a family of sets has _$(p,q)$ -property_ if
every of its $p$-tuple contains an intersecting $q$-tuple. In the early 90s,
settling an old conjecture of Hadwiger and Debrunner [25], Alon and Kleitman
[3] proved the following famous $(p,q)$-theorem, a far-reaching generalization
of Helly’s theorem. For a set system $\mathcal{G}$ defined on a ground set
$X$, a set $T\subseteq X$ is a _transversal_ for $\mathcal{G}$ if for every
$A\in{\mathcal{G}}$, $T\cap A\neq\varnothing$. The _transversal number_ of
$\mathcal{G}$, denoted by $\tau(\mathcal{G})$, is the minimum size of a
transversal for $\mathcal{G}$.

######  Theorem 1.2 ($(p,q)$-theorem).

Let $d,p,q$ be positive integers with $p\geq q\geq d+1$. If $\mathcal{F}$ is a
finite family of convex sets in ${\mathbbm{R}}^{d}$ with $(p,q)$-property,
then $\tau(\mathcal{F})\leq O_{d,p,q}(1)$.

An interesting direction of research in discrete geometry is to prove
classical results in Euclidean convexity in an abstract way. We will also work
in an axiomatic setting through abstract convexity spaces. By now, abstract
versions of Helly’s theorem and many of its variants, including the fractional
Helly theorem, and $(p,q)$-theorem have been studied in abstract convexity
spaces, see e.g. [4].

We will cast the problem in Theorem 1.1 in the language of convexity spaces,
which turns out to be equivalent to the following.

######  Theorem 1.3.

Let $r\geq 3$, $\varepsilon>0$ and ${\mathcal{B}}$ be a set system with
$(r,2)$-property. If for every intersecting pair $A,B\in{\mathcal{B}}$, at
least $\varepsilon$ fraction of the $(r-2)$-tuples ${\mathcal{T}}$ in
${\mathcal{B}}$ satisfies that both ${\mathcal{T}}\cup\\{A\\}$ and
${\mathcal{T}}\cup\\{B\\}$ are matchings of size $(r-1)$, then
$\tau({\mathcal{B}})=O_{r,\varepsilon}(1)$.

We further strengthen Theorems 1.1 and 1.3 to the following, which is a
$(p,q)$-theorem for certain convexity spaces we construct from graphs. We
defer the definition of the convexity space ${\mathcal{C}}(G)$ below and other
necessary notions to Section 2. We refer readers familiar with convexity
spaces to Section 2.3 and Fig. 2.1 which contain an overview of the proof for
Theorem 1.4.

######  Theorem 1.4 ($(r,2)$-theorem for ${\mathcal{C}}(G)$).

Let $r\geq 3$ and $G$ be a graph with bipartite induced matching number $t$.
For any ${\mathcal{G}}\subseteq{\mathcal{C}}(G)$, if ${\mathcal{G}}$ has
$(r,2)$-property, then $\tau({\mathcal{G}})=O_{r,t}(1)$. In particular, if $G$
is $\alpha$-ultra maximal $K_{r}$-free, then
$\tau({\mathcal{G}})=O_{r,\alpha}(1)$.

We remark that Theorem 1.4 is also related to the well-studied
$\chi$-boundedness problem. Indeed, it can be viewed also as a strengthening
of a $\chi$-boundedness result for ultra maximal $K_{r}$-free graphs, see
2.12.

###  1.3 Blow-up phenomenon

Given two graphs $G$ and $F$, $G$ is _homomorphic_ to $F$, denoted by
$G\xrightarrow{\textup{hom}}F$, if there exists a homomorphism
$\varphi:V(G)\rightarrow V(F)$ preserving adjacencies, i.e. if $uv\in E(G)$,
then $\varphi(u)\varphi(v)\in E(F)$. Note that $\chi(G)=t$ is equivalent to
$G$ being homomorphic to $K_{t}$. A natural extension of the chromatic
threshold problem raised in [53] asks for minimum degree condition for an
$H$-free graph guaranteeing a bounded size homomorphic image which is also
$H$-free. Formally, the _homomorphism threshold_ of a graph $H$ is defined as

$\delta_{\textup{hom}}(H):=\inf\big{\\{}\alpha\geq
0:\exists\leavevmode\nobreak\ H\textup{-free}\leavevmode\nobreak\
F=F(\alpha,H)\ \textup{s.t.\leavevmode\nobreak\ }\forall\leavevmode\nobreak\
n\textup{-vertex\ }H\textup{-free}\leavevmode\nobreak\ G,\leavevmode\nobreak\
\delta(G)\geq\alpha n\Rightarrow G\xrightarrow{\textup{hom}}F\big{\\}}.$

As having a bounded homomorphic image implies bounded chromatic number,
$\delta_{\textup{hom}}(H)\geq\delta_{\chi}(H)$. The first such result was
proved by Łuczak [37], showing that
$\delta_{\textup{hom}}(K_{3})=\frac{1}{3}$. Later, Goddard and Lyle [24]
resolved the clique case, proving that
$\delta_{\textup{hom}}(K_{r})=\delta_{\chi}(K_{r})=\frac{2r-5}{2r-3}$ for all
positive integers $r\geq 3$. The proofs of Łuczak [37], and Goddard and Lyle
[24] utilized Szemerédi regularity lemma [52], and therefore gave a tower-type
upper bound on the size of the $K_{r}$-free homomorphic image $F$. Recently,
Oberkampf and Schacht [46] gave a new proof using a clever probabilistic
argument. Their proof yields a double exponential bound
$2^{2^{O(1/\varepsilon^{2})}}$ on the size of the homomorphic image for
$K_{r}$-free graphs with minimum degree at least
$(\frac{2r-5}{2r-3}+\varepsilon)n$, which was the best-known bound for all
$r\geq 4$. As for $r=3$, a beautiful (unpublished) result of Brandt and
Thomassé [12] proved an optimal bound that any triangle-free graph $G$ with
$\delta(G)\geq(\frac{1}{3}+\varepsilon)n$ is homomorphic to a triangle-free
graph (Vega graphs) of size $O\big{(}\frac{1}{\varepsilon}\big{)}$.

Except for cliques, determining the homomorphism thresholds for any other
graph is still widely open. Letzter and Snyder [16] showed that
$\delta_{\textup{hom}}(C_{5})\leq\frac{1}{5}$. Later, Ebsen and Schacht [34]
proved that $\delta_{\textup{hom}}(C_{2r+1})\leq\frac{1}{2r+1}$ for every
$r\geq 2$. A recent significant advancement, due to Sankar [50], shows that
$\delta_{\textup{hom}}(C_{2r+1})>0$. It was known that
$\delta_{\chi}(C_{2r+1})=0$ [54], so her result provides the first example $H$
with $\delta_{\textup{hom}}(H)>\delta_{\chi}(H)$.

An important variation was studied by Łuczak and Thomassé [38] in their
ingenious new proof of $\delta_{\chi}(K_{3})=\frac{1}{3}$. They realized that
the $n/3$ minimum degree condition can be relaxed to a linear one if we have
bounded VC-dimension (see Section 2.1 for definition). That is, any $n$-vertex
triangle-free graph $G$ with bounded VC-dimension and $\delta(G)=\Omega(n)$
has bounded chromatic number (see Theorem 5.1).

Our next result shows that VC-dimension, while significant in the chromatic
threshold problem, is not so influential in the homomorphism threshold
problem.

######  Theorem 1.5.

There exists an $n$-vertex triangle-free graph $G$ with VC-dimension $3$ and
$\delta(G)\geq\frac{n}{4}$ such that $G$ has no triangle-free homomorphic
image of size smaller than $\frac{n}{4}$.

What is more relevant then? This is the content of our next main result, which
strengthens Theorem 1.1. Our theorem shows that the graph under study is in
fact a blow-up of a constant size graph, which then necessarily also has to be
$K_{r}$-free. For a graph $H$, we write $H[t]$ for the _$t$ -blow-up_ of $H$
obtained by replacing every vertex of $H$ by $t$ independent copies (i.e.
every vertex becomes an independent set of size $t$ and every edge becomes a
copy of $K_{t,t}$). We simply write $H[\cdot]$ when mentioning a blow-up of
$H$ without specifying its size (and the sizes of these independent sets could
be different). Obviously, if $G=F[\cdot]$, then
$G\xrightarrow{\textup{hom}}F$.

######  Theorem 1.6.

Given $r\geq 3,\varepsilon>0$ and $G$ be an $n$-vertex $K_{r}$-free graph. If
for every non-adjacent pair of vertices $u,v\in V(G)$, the induced subgraph
$G[N(u)\cap N(v)]$ contains $\varepsilon n^{r-2}$ copies of $K_{r-2}$, then
$G=F[\cdot]$ for some maximal $K_{r}$-free graph $F$ on at most
$2^{O((\frac{1}{\varepsilon}+r)\log\frac{1}{\varepsilon})}$ vertices.

The merit of Theorem 1.6 is that it reveals the cause of the blow-up
phenomenon $G=F[\cdot]$. Indeed, since the chromatic and homomorphism
thresholds mysteriously coincide for cliques:
$\delta_{\textup{hom}}(K_{r})=\delta_{\chi}(K_{r})$, it was not clear what
separates these two problems for cliques. Theorem 1.6 shows that for the blow-
up phenomenon, rather than VC-dimension, the main driving factor is the clique
density condition in the co-neighborhoods considered above.

Interestingly, in contrast to the $O(\frac{1}{\varepsilon})$ bound on the size
of triangle-free homomorphic image in Brandt-Thomassé’s work [12] under the
stronger minimum degree condition, much to our own surprise, the single
exponential bound in $\frac{1}{\varepsilon}$ in Theorem 1.6 is optimal as
shown by the following construction.

######  Theorem 1.7.

For every $r\geq 3$, there exists an $n$-vertex $K_{r}$-free graph $G$ such
that for every pair of non-adjacent vertices $u,v$, $G[N(u)\cap N(v)]$
contains at least $\varepsilon n^{r-2}$ copies of $K_{r-2}$, but $G$ has no
$K_{r}$-free homomorphic image of size smaller than
$2^{\frac{1}{8r^{r}\varepsilon}}$.

###  1.4 Applications

As a first application, the chromatic and homomorphism thresholds for cliques,
$\delta_{\textup{hom}}(K_{r})=\delta_{\chi}(K_{r})=\frac{2r-5}{2r-3}$, are
corollaries of Theorems 1.1 and 1.6, and Theorem 1.6 quantitatively improves
the double exponential bound in [46] to a single exponential one. Indeed, the
minimum degree condition $\delta(G)\geq(\frac{2r-5}{2r-3}+\varepsilon)n$
implies the clique density condition in co-neighborhoods considered in
Theorems 1.1 and 1.6, see 4.9.

In addition, one can consider the following natural variations on
$\delta_{\chi}$ and $\delta_{\textup{hom}}$ with increasingly stronger
hypotheses. First define a ‘higher moment minimum degree’: for
$a\in{\mathbbm{N}}$, let $\delta^{(a)}(G)$ be the minimum co-degree over all
independent sets of size $a$. So $\delta^{(1)}(G)=\delta(G)$ and
$\delta^{(2)}(G)=\min\\{|N(u)\cap N(v)|:uv\notin E(G)\\}$. Then, we can define
a higher moment homomorphism threshold as follows.

$\delta_{\textup{hom}}^{(a)}(H):=\inf\big{\\{}\alpha\geq
0:\exists\leavevmode\nobreak\ H\textup{-free}\leavevmode\nobreak\
F=F(\alpha,H)\ \textup{s.t.\leavevmode\nobreak\ }\forall\leavevmode\nobreak\
n\textup{-vertex\ }H\textup{-free}\leavevmode\nobreak\ G,\leavevmode\nobreak\
\delta^{(a)}(G)\geq\alpha n\Rightarrow G\xrightarrow{\textup{hom}}F\big{\\}}.$

More generally, for $a,b\in{\mathbbm{N}}$ with $b\geq 2$, let
$\hat{\delta}^{(a,b)}(G)$ be the minimum relative $K_{b}$-density in the
subgraph induced by co-neighborhood of $I$ over all independent sets $I$ of
size $a$. In other words,
$\hat{\delta}^{(a,b)}(G)=\min\limits_{I:|I|=a}\frac{k_{b}(G[N(I)])}{\binom{|N(I)|}{b}}$,
where $k_{b}(\cdot)$ counts the number of copies of $K_{b}$. Define

$\displaystyle\delta_{\textup{hom}}^{(a,b)}(H):=\inf\big{\\{}\alpha\geq 0:$
$\displaystyle\exists\leavevmode\nobreak\ H\textup{-free}\leavevmode\nobreak\
\textup{graph}\leavevmode\nobreak\ F=F(\alpha,H)\
\textup{s.t.\leavevmode\nobreak\ }\forall\leavevmode\nobreak\
n\textup{-vertex\ }H\textup{-free}\leavevmode\nobreak\ G,$
$\displaystyle\leavevmode\nobreak\
\delta^{(a)}(G)=\Omega(n),\leavevmode\nobreak\
\hat{\delta}^{(a,b)}(G)\geq\alpha\Rightarrow
G\xrightarrow{\textup{hom}}F\big{\\}}.$

Thus, $\delta_{\textup{hom}}=\delta_{\textup{hom}}^{(1)}$ and Theorem 1.6 can
be stated as $\delta_{\textup{hom}}^{(2,r-2)}(K_{r})=0$.

We shall see that Theorem 1.6 determines all other variations
$\delta_{\textup{hom}}^{(2,b)}(K_{r})$, which take values from generalized
Turán densities:
$\pi_{s}(K_{t}):=\lim\limits_{n\rightarrow\infty}\frac{\textup{ex}(n,K_{s},K_{t})}{\binom{n}{s}}$,
where $s\leq t$. Here $\textup{ex}(n,K_{s},K_{t})$ is the maximum number of
$K_{s}$ in an $n$-vertex $K_{t}$-free graph. Erdős [20] determined back in
1962 all such densities $\pi_{s}(K_{t})=\prod_{i=1}^{s-1}\frac{t-1-i}{t-1}$,
which are realized by $T_{n,t-1}$.

######  Corollary 1.8.

Let $r,a,b\in{\mathbbm{N}}$ with $r\geq 3$, $a\geq 2$, and $2\leq b\leq r-2$.
Then we have

$\delta_{\textup{hom}}^{(a)}(K_{r})=\frac{r-3}{r-2}\quad\mbox{and}\quad\delta_{\textup{hom}}^{(a,b)}(K_{r})=\pi_{b}(K_{r-2})=\prod_{i=1}^{b-1}\frac{r-3-i}{r-3}.$

Notations. For a family $\mathcal{H}$ of graphs, we say $G$ is
$\mathcal{H}$-free if $G$ does not contain any graph $H\in\mathcal{H}$ as a
subgraph. For a vertex $u\in V(G)$, we will use $N_{G}(u)$ (or $N(u)$ if the
subscript is clear) to denote the set of neighbors of $u$. For a pair of
vertices $u,v\in V(G)$, we use $N_{G}(u,v)$ (or $N(u,v)$ if the subscript is
clear) to denote the set of common neighbors of $u$ and $v$, that is,
$N_{G}(u,v)=N_{G}(u)\cap N_{G}(v)$. For a subset $T\subseteq V(G)$, we will
use $G[T]$ to denote the subgraph induced by $T$. For the sake of clarity of
presentation, we omit floors and ceilings and treat large numbers as integers
whenever this does not affect the argument. All logarithms are natural
logarithms with base $e$.

Structure of this paper. In Section 2, we will build the connection between
graph theory and abstract convexity spaces and prove Theorem 1.4, which
implies Theorem 1.1. In Section 3, we will discuss the difference between the
chromatic and homomorphism threshold problems for cliques and prove Theorem
1.5. We then prove Theorems 1.6 and 1.7 and 1.8 in Section 4. Concluding
remarks are in Section 5.

##  2 A geometric framework

In this section, first in Section 2.1, we introduce abstract convexity spaces
and some useful parameters. Then in Section 2.2, we define a convexity space
from a graph, prove some properties of this space, and establish some
correspondence between the graph and this space. With this preparation, we are
then in a position to lay out our geometric approach in Section 2.3 and list
the main lemmas for proving Theorem 1.1. The main lemmas are proved in Section
2.4 and Section 2.5. Finally, Theorem 1.4 is proved in Section 2.6.

###  2.1 Abstract convexity space

A convexity space is a pair $(X,{\mathcal{C}})$ where ${\mathcal{C}}\subseteq
2^{X}$ is a family of subsets satisfying

  * •

$\varnothing,X\in{\mathcal{C}}$;

  * •

${\mathcal{C}}$ is closed under intersection, i.e. for every
${\mathcal{F}}\subseteq{\mathcal{C}}$,
$\bigcap{\mathcal{F}}:=\bigcap_{F\in{\mathcal{F}}}F\in{\mathcal{C}}$.

We call sets in ${\mathcal{C}}$ _convex sets_. The _convex hull_ of a set of
points $Y\subseteq X$ is the intersection of all convex sets in
${\mathcal{C}}$ containing $Y$, which is also the minimal convex set
containing $Y$. That is, $\mathrm{conv}Y=\bigcap_{Y\subseteq
F\in{\mathcal{C}}}F$. When the set $X$ is clear from the content, we simply
refer ${\mathcal{C}}$ as a convexity space. For more on the theory of
convexity space and combinatorial convexity, we refer the interested readers
to the books of van de Vel [56] and of Bárány [6]. Two trivial convexity
spaces are ${\mathcal{C}}=\\{\varnothing,X\\}$ and ${\mathcal{C}}=2^{X}$. Let
$\mathcal{C}^{d}$ be the family of all convex sets in ${\mathbbm{R}}^{d}$.
Then $({\mathbbm{R}}^{d},\mathcal{C}^{d})$ is the usual Euclidean convexity
space. Here are some non-trivial examples.

  * •

_Convex lattice sets_ : A set of the form $C\cap{\mathbbm{Z}}^{d}$ for some
convex set $C$ in ${\mathcal{C}}^{d}$ is called a _convex lattice set_. Then
$({\mathbbm{Z}}^{d},{\mathcal{C}}^{d}\cap{\mathbbm{Z}}^{d})$ is a convexity
space.

  * •

_Subgroups_ : Given a group $G$ with identity $e$, then
$(G\setminus\\{e\\},\\{H\setminus\\{e\\}:H\leq G\\})$ is a convexity space.
For a set $S\subseteq G\setminus\\{e\\},{\rm conv}S=\left\langle
S\right\rangle\setminus\\{e\\}$ is a subgroup generated by $S$ (with identity
removed).

  * •

_Subcubes_. A subset ${\mathcal{C}}\subseteq\\{0,1\\}^{n}$ is a _subcube_ if
there exists a set of coordinates $I\subseteq[n]$ and a binary vector
$\bm{v}\in\\{0,1\\}^{I}$ such that ${\mathcal{C}}$ consists of all vectors in
$\\{0,1\\}^{n}$ whose projection on $I$ is $\bm{v}$. Then $\\{0,1\\}^{n}$
together with the family of all subcubes forms a convexity space.

  * •

_Subtrees_. Given a finite tree $T$ on vertex set $V$, then $V$ together with
all its subtrees forms a convexity space.

Let us now introduce some invariants which are abstractions of properties of
Euclidean convexity space.

######  Definition 2.1.

The _Radon number_ of a convexity space $(X,{\mathcal{C}})$, denoted by
$r({\mathcal{C}})$, is the minimum integer $r$ such that for any set of points
$Y\subseteq X$ with $|Y|\geq r$, there is a partition $Y=Y_{1}\cup Y_{2}$ with
$\mathrm{conv}Y_{1}\cap\mathrm{conv}Y_{2}\neq\varnothing$.

Radon’s Lemma [49] states, in this notation, that the Radon number of the
Euclidean convexity space $({\mathbbm{R}}^{d},{\mathcal{C}}^{d})$ is at most
$d+2$.

######  Definition 2.2.

The _Helly number_ of a set system ${\mathcal{F}}$, denoted by
$h({\mathcal{F}})$, is the minimum integer $h$ such that in any finite
subfamily ${\mathcal{G}}\subseteq{\mathcal{F}}$, if every $h$-tuple of
${\mathcal{G}}$ is intersecting, then ${\mathcal{G}}$ is intersecting.

Thus, Helly’s theorem [29] implies that $h(\mathcal{C}^{d})\leq d+1$, which is
less than its Radon number. This relation between Radon and Helly numbers
holds for all convexity space $(X,{\mathcal{C}})$:
$h({\mathcal{C}})<r({\mathcal{C}})$, as shown by Levi [35]. The gap between
Radon number and Helly number, however, could be arbitrarily large. One such
example is the space of subcubes in $\\{0,1\\}^{n}$, which has Helly number 2,
but Radon number $\lfloor{\log_{2}(n+1)}\rfloor+1$.

We also need the fractional extension of Helly number defined as follows.

######  Definition 2.3.

The _fractional Helly number_ of a set system ${\mathcal{F}}$, denoted by
$h^{*}({\mathcal{F}})$, is the smallest natural number $k$ such that for every
$\alpha>0$, there exists $\beta=\beta(\alpha)>0$ such that the following
holds. For every $\\{F_{1},F_{2},\ldots,F_{m}\\}\subseteq{\mathcal{F}}$, if
the number of intersecting $k$-tuples $I\in\binom{[m]}{k}$ with
$\bigcap\limits_{i\in I}F_{i}\neq\varnothing$ is at least
$\alpha\binom{m}{k}$, then $\\{F_{1},F_{2},\ldots,F_{m}\\}$ contains an
intersecting subfamily of size at least $\beta m$.

We remark that there is no direct relation between the Helly number and its
fractional counterpart. For example, for the Euclidean convexity space,
$h(\mathcal{C}^{d})=h^{*}(\mathcal{C}^{d})=d+1$; for the convex lattice set,
$h({\mathcal{C}}^{d}\cap{\mathbbm{Z}}^{d})=2^{d}$ and
$h^{*}({\mathcal{C}}^{d}\cap{\mathbbm{Z}}^{d})=d+1$ [7, 15]; for the family
${\mathcal{B}}^{d}$ of all axis-aligned boxes in ${\mathbbm{R}}^{d}$,
$h({\mathcal{B}}^{d})=2$ and $h^{*}({\mathcal{B}}^{d})=d+1$ [17].

The concept of (weak) $\varepsilon$-net is well-studied in computational
geometry, combinatorics, and machine learning; it is particularly useful in
many algorithmic applications, including range searching and geometric
optimization.

######  Definition 2.4.

Let $X$ be a set and ${\mathcal{C}}\subseteq 2^{X}$ be a family of subsets of
$X$. Given a finitely supported probability measure $\mu$ on $X$, a set
$N\subseteq X$ is a _weak $\varepsilon$-net for ${\mathcal{C}}$ with respect
to $\mu$_, if $N\cap C\neq\varnothing$ for every $C\in\mathcal{C}$ with
$\mu(C)\geq\varepsilon$. We say that ${\mathcal{C}}$ has weak
$\varepsilon$-nets of size $m=m({\mathcal{C}},\varepsilon)$ if there is a weak
$\varepsilon$-net for ${\mathcal{C}}$ with respect to $\mu$ of size at most
$m$ for every finitely supported probability measure $\mu$ on $X$.

Note that $m({\mathcal{C}},\varepsilon)$, the size of weak $\varepsilon$-nets
for ${\mathcal{C}}$, does not depend on the choice of the probability measure
$\mu$.

We need the following fractional version of transversal number.

######  Definition 2.5.

A _fractional transversal_ for a set system $\mathcal{G}$ on ground set $V$ is
a function $f$ from $V$ to $[0,1]$ such that for every set $A\in\mathcal{G}$,
$\sum_{v\in A}f(v)\geq 1$. The size of $f$ is $\sum_{v\in V}f(v)$ and the
_fractional transversal number_ of $\mathcal{G}$ is the minimum size of a
fractional transversal for $\mathcal{G}$, denoted by $\tau^{*}(\mathcal{G})$.

In particular, the characteristic function of a transversal is a fractional
transversal and so for any $\mathcal{G}$, we have
$\tau^{*}(\mathcal{G})\leq\tau(\mathcal{G})$.

######  Definition 2.6.

A _matching_ in a set system $\mathcal{H}$ is a collection pairwise disjoint
sets in $\mathcal{H}$. The _matching number_ of $\mathcal{H}$ is size of a
largest matching in $\mathcal{H}$, denoted by $\nu(\mathcal{H})$.

######  Definition 2.7.

A _fractional matching_ in a set system $\mathcal{H}$ on ground set $V$ is a
function $g$ from ${\mathcal{H}}$ to $[0,1]$ such that for every $v\in V$,
$\sum_{v\in A}g(A)\leq 1$. The size of $g$ is $\sum_{A\in{\mathcal{H}}}g(A)$
and the _fractional matching number_ of $\mathcal{H}$ is the maximum size of a
fractional matching in $\mathcal{H}$, denoted by $\nu^{*}(\mathcal{H})$.

Similarly, $\nu(\mathcal{H})\leq\nu^{*}(\mathcal{H})$ holds for every set
system $\mathcal{H}$. Moreover, LP duality infers that
$\nu^{*}(\mathcal{H})=\tau^{*}(\mathcal{H})$. Therefore, for any
$\mathcal{H}$, we have
$\nu(\mathcal{H})\leq\nu^{*}(\mathcal{H})=\tau^{*}(\mathcal{H})\leq\tau(\mathcal{H})$.

The _Vapnik-Chervonenkis dimension_ (_VC-dimension_ for short) is a parameter
that measures the complexity of various combinatorial objects, and plays an
important role in statistics, algebraic geometry, learning theory, and model
theory. For a set system $\mathcal{F}\subseteq 2^{X}$, the _Vapnik-
Chervonenkis dimension_ of $\mathcal{F}$, denoted by
$\mathrm{dim}_{\mathsf{VC}}(\mathcal{F})$, is the largest integer $d$ for
which there exists a subset $S\subseteq X$ with $|S|=d$ such that for every
subset $B\subseteq S$, one can find a member $A\in\mathcal{F}$ with $A\cap
S=B$. In such case, we say that $S$ is _shattered_ by ${\mathcal{F}}$.

The well-known $\varepsilon$-net theorem of Haussler and Welzl [28] (also see
the book of Matoušek [41]) provides an inverse inequality for transversal
number and its fractional version in set systems with bounded VC-dimension.

######  Theorem 2.8 ($\varepsilon$-net theorem).

There exists an absolute constant $C$ such that the following holds. Let
${\mathcal{F}}$ be a set system with VC-dimension $d$. Then
$\tau({\mathcal{F}})\leq
Cd\tau^{*}({\mathcal{F}})\log\tau^{*}({\mathcal{F}})$.

###  2.2 The unusual suspect

In this subsection, we construct an abstract convexity space from a graph.
Given a set system ${\mathcal{F}}$, the _intersection closure_ of
${\mathcal{F}}$, denoted by ${\mathcal{F}}^{\cap}$, is the set system obtained
from ${\mathcal{F}}$ by taking all possible intersections of subfamilies of
${\mathcal{F}}$. Given a graph $G$, let $\mathrm{MIS}(G)$ be the family of all
maximal independent sets of $G$.

We can now define our convexity space ${\mathcal{C}}(G)$ from a given graph
$G$ as follows:

  * •

Let $\mathcal{B}(G):=\\{K_{v}:v\in V(G)\\}$ be the set system on the ground
set $\mathrm{MIS}(G)$ indexed by $V(G)$, where
$K_{v}=\\{I\in\mathrm{MIS}(G):v\in I\\}$ consists of all maximal independent
sets of $G$ containing $v$.

  * •

Let ${\mathcal{C}}(G)={\mathcal{B}}(G)^{\cap}$ be the intersection closure of
${\mathcal{B}}(G)$. Then $(X,{\mathcal{C}}(G))$ is a convexity space, where
$X=\mathrm{MIS}(G)$.

Note that ${\mathcal{B}}(G)$ and ${\mathcal{C}}(G)$ could be a family of
multi-sets. For example, if two vertices $u,v$ have the same neighborhood in
$G$, then $K_{u}=K_{v}$. Equivalently, ${\mathcal{C}}(G)$ can be defined as
${\mathcal{C}}(G)=\\{K_{S}:S\subseteq V(G)\\}$, where for each subset
$S\subseteq V(G)$, $K_{S}=\\{I\in X:S\subseteq I\\}$ is the set of all maximal
independent sets containing $S$. The _dual_ of a set system ${\mathcal{H}}$ is
a set system obtained from ${\mathcal{H}}$ by swapping the roles of ground
elements and sets in ${\mathcal{H}}$. Note that the dual of $\mathcal{B}(G)$
is the set system induced by $\mathrm{MIS}(G)$, which we denote by
${\mathcal{M}}(G)=\\{I:I\in\mathrm{MIS}(G)\\}$.

The convex hull operator of this convexity space $(X,{\mathcal{C}}(G))$ can be
described as follows. Given a subset $Y=\\{I_{1},\ldots,I_{m}\\}\subseteq X$,
$\mathrm{conv}Y$ is the intersection of all convex sets in ${\mathcal{C}}(G)$
containing $Y$, so $\mathrm{conv}Y=K_{I_{1}\cap\cdots\cap I_{m}}$.

In the rest of this subsection, we establish some correspondence between a
graph $G$ and the set system ${\mathcal{B}}(G)$, which is summarized in Table
1.

The graph $G$ | Set syetem $\mathcal{B}=\mathcal{B}(G)$
---|---
$uv\in E(G)$ | $K_{u}\cap K_{v}=\emptyset$
(maximal) independent set $I$ | (maximal) intersecting subfamily $\\{K_{v}:v\in I\\}$
Chromatic number $\chi(G)$ | Transversal number $\tau(\mathcal{B})$
Clique number $w(G)$ | Matching number $\nu(\mathcal{B})$
$K_{r}$-freeness |  $(r,2)$-property
Table 1: Graph terminology vs. geometric terminology

We first observe that $G$ is isomorphic to the disjointness graph of
${\mathcal{B}}(G)$. Here, the _disjointness graph_ of a set system
$\mathcal{F}$, denoted by $D(\mathcal{F})$, is the graph with vertex set
$\mathcal{F}$ and a pair of sets in ${\mathcal{F}}$ are adjacent in
$D(\mathcal{F})$ if and only if they are disjoint. On the other hand, if we
start with any set system ${\mathcal{F}}$ and consider
${\mathcal{B}}(D({\mathcal{F}}))$, we will get a set system whose nerves have
the same 1-skeleton. The nerve of a set system is an abstract simplicial
complex that records all intersecting subfamilies. In other words,
${\mathcal{F}}$ and ${\mathcal{B}}(D({\mathcal{F}}))$ have the same pairwise
intersections. One can think the two operations $D(\cdot)$ and
${\mathcal{B}}(\cdot)$ as dual of each other.

######  Proposition 2.9.

Given any graph $G$, we have $G\cong D(\mathcal{B}(G))$. On the other hand,
given any set system $\mathcal{F}$, ${\mathcal{F}}$ and
${\mathcal{B}}(D({\mathcal{F}}))$ have the same pairwise intersections.

###### Proof.

By the definition of ${\mathcal{B}}(G)$, $K_{u}\cap K_{v}=\varnothing$ if and
only if there is no maximal independent set containing both $u$ and $v$, in
other words $uv\in E(G)$. Thus, mapping $K_{v}$ to $v$ for each $v\in V(G)$ is
a graph isomorphism between $D(\mathcal{B}(G))$ and $G$.

For the second part, we need to show that ${\mathcal{F}}$ and
${\mathcal{B}}(D({\mathcal{F}}))$ have the same pairwise intersections. This
amounts to proving that $D({\mathcal{F}})\cong
D({\mathcal{B}}(D({\mathcal{F}})))$, which follows from the first part. ∎

A simple but useful fact is that the operation: $G\rightarrow{\mathcal{C}}(G)$
always produces a convexity space with Helly number 2.

######  Proposition 2.10.

For any graph $G$ with at least one edge, ${\mathcal{C}}(G)$ has Helly number
$2$.

###### Proof.

We need to show that for any subfamily
${\mathcal{S}}=\\{K_{S_{i}}:S_{i}\subseteq V(G)\\}\subseteq{\mathcal{C}}(G)$,
if ${\mathcal{S}}$ is pairwise intersecting, then it is in fact intersecting.
Similarly to 2.9, it is easy to see that if $K_{S}$ and $K_{T}$ intersect,
then $S\cup T$ is an independent set. Thus, ${\mathcal{S}}$ being pairwise
intersecting infers that $S=\bigcup\limits_{S_{i}\in{\mathcal{S}}}S_{i}$ is an
independent set in $G$. Let $I$ be an arbitrary maximal independent set
containing $S$, then $I\in\bigcap{\mathcal{S}}$ as desired. ∎

2.9 in particular implies that there is a one-to-one correspondence between
(maximal) independent sets $I$ in $G$ and subfamilies of ${\mathcal{B}}(G)$
that are (maximally) pairwise intersecting; and as ${\mathcal{B}}(G)$ has
Helly number 2, all these subfamilies are intersecting.

A key correspondence is as follows.

######  Proposition 2.11.

For any graph $G$, we have $\chi(G)=\tau(\mathcal{B}(G))$.

###### Proof.

Observe that a collection of maximal independent sets pierces
${\mathcal{B}}(G)=\\{K_{u}:u\in V(G)\\}$ if and only if their union covers
$V(G)$. We first show that $\chi(G)\leq\tau({\mathcal{B}}(G))$. Let
$k=\tau({\mathcal{B}}(G))$, then there are
$I_{1},I_{2},\ldots,I_{k}\in\mathrm{MIS}(G)$ such that they pierce
${\mathcal{B}}(G)$. As $\bigcup_{j\in[k]}I_{j}=V(G)$, for every vertex $v\in
V(G)$, we can color it with the smallest index $j\in[k]$ such that $v\in
I_{j}$. This provides a proper $k$-coloring of $G$, and so $\chi(G)\leq k$.

To show $\tau(\mathcal{B}(G))\leq\chi(G)$, suppose that $\chi(G)=r$. Then we
can partition $V(G)$ into $r$ independent sets $V_{1}\cup V_{2}\cup\cdots\cup
V_{r}$. For each $V_{j}$, $j\in[r]$, let $I_{j}\supseteq V_{j}$ be an
arbitrary maximal independent set containing it. Then we have
$\bigcup_{j\in[r]}I_{j}=V(G)$ and therefore $I_{j}$, $j\in[r]$, pierce
${\mathcal{B}}(G)$, which implies that $\tau({\mathcal{B}}(G))\leq r$. ∎

######  Remark 2.12.

Using the correspondence in Table 1, it is not hard to see that Theorem 1.1 is
equivalent to Theorem 1.3, which is an $(r,2)$-theorem for ${\mathcal{B}}(G)$.
A class of graphs are $\chi$-bounded if its chromatic number can be bounded by
a function of its clique number. The correspondence in Table 1 shows that
Theorem 1.1, the $(r,2)$-theorem for ${\mathcal{B}}(G)$, can be rephrased as
the statement that ultra maximal $K_{r}$-free graphs are $\chi$-bounded.
Finally note that Theorem 1.4 is a strengthening as it is an $(r,2)$-theorem
for the convexity space ${\mathcal{C}}(G)$, because the $(r,2)$-theorem holds
for any family of convex sets in the convexity space, not just the ones of the
family ${\mathcal{B}}(G)$.

###  2.3 Main lemmas and proof of Theorem 1.1

In this subsection, we present our geometric framework, depicted in Fig. 2.1.
By 2.11, our goal is to bound the transversal number of ${\mathcal{B}}(G)$.
Our approach consists of two sides.

On the side of convexity space, to bound $\tau({\mathcal{B}}(G))$, by the
$\varepsilon$-net theorem, Theorem 2.8, it suffices to bound the VC-dimension
of ${\mathcal{B}}(G)$ and the fractional transversal number
$\tau^{*}({\mathcal{B}}(G))$. The latter can in turn be bounded by the
fractional Helly number of ${\mathcal{B}}(G)$. To this end, we prove in Lemma
2.13 and Lemma 2.14 that both the VC-dimension and the fractional Helly number
of ${\mathcal{B}}(G)$ can be controlled by certain induced matching defined as
follows.

Bipartite induced matchingHalf graph$\varepsilon$-ultra $K_{r}$-freeVC-
dimension ${\mathcal{B}}$$\varepsilon$-net ${\mathcal{B}}$Radon number
${\mathcal{C}}$Weak $\varepsilon$-net ${\mathcal{C}}$$(r,2)$-theorem
${\mathcal{C}}$Fractional transversalFractional Helly ${\mathcal{C}}$Helly
${\mathcal{C}}$The graph $G$Convexity space $(X,{\mathcal{C}})$ Figure 2.1:
The relationship between graphs and convexity spaces

A matching $\\{u_{i}v_{i}\\}_{i\in[t]}$ in a graph $G$ is a _bipartite induced
matching_ of size $t$ if $u_{i}v_{j}\in E(G)$ if and only if $i=j$. We call
the size of a largest such matching in $G$ its _bipartite induced matching
number_ , denoted by $\nu_{\mathrm{bi}}(G)$. If we further require that both
$\\{u_{i}\\}_{i\in[t]}$ and $\\{v_{i}\\}_{i\in[t]}$ are independent sets, then
we call it an _induced matching_.

######  Lemma 2.13.

For any graph $G$, if $\mathrm{dim}_{\mathsf{VC}}({\mathcal{B}}(G))\geq 3$,
then $\mathrm{dim}_{\mathsf{VC}}({\mathcal{B}}(G))\leq\nu_{\mathrm{bi}}(G)$.

We remark that the bound on the VC-dimension above is optimal. Indeed,
consider the graph $G$ with four vertices $x,y,z,w$, where $x,y,z$ form a copy
of triangle, and $w$ is an isolated vertex. Then it is easy to check that
${\mathcal{B}}(G)$ has VC-dimension 2, however $\nu_{\mathrm{bi}}(G)=1$.

######  Lemma 2.14.

For any graph $G$, $h^{*}(\mathcal{B}(G))\leq\nu_{\mathrm{bi}}(G)+1$.

We have then to control the bipartite induced matching number on the graph
side. Recall that an $n$-vertex $K_{r}$-free graph $G$ is $\varepsilon$-ultra
maximal $K_{r}$-free if for every non-adjacent pair of vertices $u,v\in V(G)$,
the induced subgraph $G[N(u)\cap N(v)]$ contains $\varepsilon n^{r-2}$ copies
of $K_{r-2}$.

We show that all $\varepsilon$-ultra maximal $K_{r}$-free graphs have bounded
bipartite induced matching number.

######  Theorem 2.15.

For $\varepsilon>0$ and $r\geq 3$, every $\varepsilon$-ultra maximal
$K_{r}$-free graph $G$ satisfies

$\nu_{\mathrm{bi}}(G)\leq(2/\varepsilon)^{2/\varepsilon}.$

We will prove Theorem 2.15 in two steps. First, we show that in an
$\varepsilon$-ultra $K_{r}$-free graph $G$, there does not exist a large copy
of certain half graph, see Lemma 2.22. From not containing a large half graph,
we can then derive that $G$ cannot have a large bipartite induced matching,
see Lemma 2.23.

Combining Lemmas 2.13 and 2.14 and Theorem 2.15, we get the following.

######  Corollary 2.16.

Let $\varepsilon>0$, $r\geq 3$ and $G$ be an $\varepsilon$-ultra maximal
$K_{r}$-free graph. Then both the VC-dimension and fractional Helly number of
${\mathcal{B}}(G)$ are at most $(2/\varepsilon)^{2/\varepsilon}+1$.

######  Remark 2.17.

We would like to mention a related $(p,q)$-theorem for set systems with
bounded VC-dimension due to Matoušek [42]. It states that if the VC-dimension
of the dual of a set system ${\mathcal{F}}$ is at most $k-1$, then any finite
${\mathcal{G}}\subseteq{\mathcal{F}}$ with $(r,k)$-property, $r\geq k$,
satisfies $\tau({\mathcal{G}})=O_{r,k}(1)$. Notice that even though we do have
a bound on the VC-dimension of dual of ${\mathcal{B}}(G)$, that is,
$\mathrm{dim}_{\mathsf{VC}}({\mathcal{M}}(G))$ (from 2.16 or Lemma 2.20).
However, we cannot apply Matoušek’s result to bound $\tau({\mathcal{B}}(G))$
directly. Indeed, by Table 1, the $K_{r}$-freeness of $G$ corresponds to
$(r,2)$-property of ${\mathcal{B}}(G)$. To utilize Matoušek’s result, we would
need to (i) either show the $(r,k)$-property for ${\mathcal{B}}(G)$, (ii) or
prove that ${\mathcal{M}}(G)$ has VC-dimension $1$. Having (i) for any $k>2$
would require a stronger hypothesis that in $G$, there is an independent set
of size $k$ in a subgraph induced by any set of $r$ vertices. We cannot hope
to have (ii) either: for $\varepsilon$-ultra maximal $K_{r}$-free graph $G$,
${\mathcal{M}}(G)$ could have VC-dimension $2^{\Omega(1/\varepsilon)}$, see
e.g. the construction in Theorem 1.6 and Section 4.2.

To prove Theorem 1.1, we are left to bound the fractional transversal number
of ${\mathcal{B}}(G)$.

######  Lemma 2.18.

Let $\varepsilon>0$, $r\geq 3$ and $G$ be an $\varepsilon$-ultra maximal
$K_{r}$-free graph. Then $\tau^{*}(\mathcal{B}(G))=O_{\varepsilon,r}(1)$.

Before we prove this result, we need the following.

######  Theorem 2.19 ([2]).

Let $r,\ell\geq k\geq 2$ and ${\mathcal{F}}$ be a set system with
$(r,k)$-property. If the Helly number of $\mathcal{F}$ is $k$ and the
fractional Helly number of $\mathcal{F}$ is $\ell$, then
$\tau^{*}(\mathcal{F})=O_{r,\ell,k}(1)$.

###### Proof of Lemma 2.18.

By the correspondence in Table 1, ${\mathcal{B}}(G)$ has $(r,2)$-property as
$G$ is $K_{r}$-free. The Helly number of $\mathcal{B}(G)$ is $2$ by 2.10 and
the fractional Helly number of ${\mathcal{B}}(G)$ is also bounded by 2.16. The
conclusion then follows from Theorem 2.19 with $k=2$. ∎

Finally, combining Theorem 2.8, 2.16 and Lemma 2.18, we obtain Theorem 1.1.

###  2.4 VC-dimension and fractional Helly number

In this subsection, we prove Lemmas 2.13 and 2.14.

###### Proof of Lemma 2.13.

Suppose the VC-dimension of $\mathcal{B}(G)$ is $d\geq 3$, then there is a set
$A:=\\{I_{1},\ldots,I_{d}\\}$ of $d$ maximal independent sets shattered by
$\mathcal{B}(G)$. We shall find a bipartite induced matching of size $d$ in
$G$. Note that for each $i\in[d]$, there exists some
$K_{v_{i}}\in\mathcal{B}(G)$ such that $K_{v_{i}}\cap
A=A\setminus\\{I_{i}\\}$. Then $v_{i}\notin I_{i}$, which together with the
maximality of $I_{i}$ implies that there is a vertex $u_{i}\in I_{i}$ such
that $v_{i}u_{i}\in E(G)$. Moreover, for all distinct $i,j\in[d]$, $v_{i}\in
I_{j}$, implying that $v_{i}u_{j}\notin E(G)$. That is, $v_{i}$ is adjacent to
$u_{j}$ if and only if $i=j$. In particular, all $v_{i}$ are distinct vertices
and all $u_{i}$ are distinct vertices.

We now show that for any $i,j\in[d]$, $v_{i}\neq u_{j}$. Suppose
$v_{i}=u_{j}$. Then $i\neq j$, for otherwise $v_{j}=v_{i}=u_{j}$ contradicting
$u_{j}v_{j}\in E(G)$. Note also that for any distinct $i,j\in[d]$,
$K_{v_{i}}\cap K_{v_{j}}\cap A=A\setminus\\{I_{i},I_{j}\\}\neq\varnothing$ as
$d\geq 3$, implying that $u_{j}v_{j}=v_{i}v_{j}\notin E(G)$, a contradiction.
Thus, $\\{u_{i}v_{i}\\}_{i\in[d]}$ is a bipartite induced matching of size $d$
as desired. ∎

We can also bound the VC-dimension of the dual of ${\mathcal{B}}(G)$ by its
bipartite induced matching number.

######  Lemma 2.20.

For any graph $G$, if the VC-dimension of the dual of $\mathcal{B}(G)$ is
$d\geq 1$, then $d\leq\nu_{bi}(G)$.

###### Proof.

Recall that the dual of ${\mathcal{B}}(G)$ is the maximal independent set
hypergraph ${\mathcal{M}}={\mathcal{M}}(G)$. By assumption, there is a set $D$
of $d$ vertices $v_{1},\ldots,v_{d}$ such that for any subset
$D^{\prime}\subseteq D$, there is a maximal independent set $I_{D^{\prime}}$
such that $I_{D^{\prime}}\cap D=D^{\prime}$. In particular, $D$ is an
independent set by considering $I_{D}$. For each $i\in[d]$, as $v_{i}\notin
I_{D\setminus\\{v_{i}\\}}$, the maximality of $I_{D\setminus\\{v_{i}\\}}$
implies that there exists some vertex $u_{i}\in I_{D\setminus\\{v_{i}\\}}$
such that $v_{i}u_{i}\in E(G)$ and $v_{j}u_{i}\notin E(G)$ for any $j\neq i$.
Since $D$ is an independent set, we must have $u_{i}\notin D$. Moreover,
$u_{1},u_{2},\ldots,u_{d}$ are all distinct. Indeed, if $u_{j}=u_{i}$ for
$j\neq i$, then $v_{j}u_{j}=v_{j}u_{i}\notin E(G)$, a contradiction. Thus,
$\\{v_{i}u_{i}\\}_{i\in[d]}$ is a bipartite induced matching of size $d$. ∎

We now bound the fractional Helly number of ${\mathcal{B}}(G)$. Matoušek [42]
proved that if the VC-dimension of the dual of a set system ${\mathcal{F}}$ is
at most $k-1$, then the fractional Helly number of ${\mathcal{F}}$ is at most
$k$. This, together with Lemma 2.20, implies that
$h^{*}({\mathcal{B}}(G))\leq\mathrm{dim}_{\mathsf{VC}}({\mathcal{M}}(G))+1\leq\nu_{\mathrm{bi}}(G)+1$.
Here, we give a different proof using the following result of Holmsen [30].

######  Theorem 2.21 ([30]).

For any $k\geq 2$ and $\alpha>0$, there exists $\beta>0$ such that the
following holds. Let $G$ be an $n$-vertex graph with at least
$\alpha\binom{n}{k}$ independent sets of size $k$. If $G$ does not contain an
induced matching of size $k$, then $\alpha(G)\geq\beta n$.

###### Proof of Lemma 2.14.

Let $\nu_{\mathrm{bi}}(G)=k-1$. By the definition of fractional Helly number,
we need to show that for every $\alpha>0$, there exists $\beta>0$ such that
every family
$\mathcal{F}=\\{K_{u_{1}},\ldots,K_{u_{m}}\\}\subseteq{\mathcal{B}}(G)$ with
at least $\alpha\binom{m}{k}$ intersecting $k$-subsets must contain an
intersecting subfamily of size $\beta m$. By the correspondence in Table 1,
this amounts to proving that for every $U=\\{u_{1},\ldots,u_{m}\\}\subseteq
V(G)$, if $G[U]$ has at least $\alpha\binom{m}{k}$ independent sets of size
$k$, then $\alpha(G[U])\geq\beta m$. This follows immediately from Theorem
2.21 as $G$ does not contain an induced matching of size
$\nu_{\mathrm{bi}}(G)+1=k$. ∎

###  2.5 Bipartite induced matching in $\varepsilon$-ultra maximal
$K_{r}$-free

In this subsection, we prove Theorem 2.15. We need a notion of half graphs.
Let $\mathcal{H}_{k}$ be the family of graphs which consists of all of the
graphs $H$ with vertices $\\{x_{i},y_{i}:\leavevmode\nobreak\ i\in[k]\\}$ such
that

  * •

$x_{i}y_{i}\notin E(H)$ for all $i\in[k]$; and

  * •

$x_{i}y_{j}\in E(H)$ for all $1\leq j<i\leq k$.

Note that we put no restriction on pairs $\\{x_{j},y_{i}\\}$ for all $1\leq
j<i\leq k$ and no restriction on $H[\\{x_{1},\ldots,x_{k}\\}]$ and
$H[\\{y_{1},\ldots,y_{k}\\}]$. We call graphs in ${\mathcal{H}}_{k}$ _half
graphs_.

$x_{4}$$x_{3}$$x_{2}$$x_{1}$$y_{4}$$y_{3}$$y_{2}$$y_{1}$ Figure 2.2: Half
graph

$b_{1}$$a_{1}$$c_{1}$$a_{2}$$a_{\frac{\varepsilon q}{2}+1}$$a_{q}$ Figure 2.3:
2.24

######  Lemma 2.22.

Let $\varepsilon>0$, $r\geq 3$ and $G$ be an $\varepsilon$-ultra maximal
$K_{r}$-free graph. Then $G$ does not contain any half graph in
$\mathcal{H}_{k}$ as a subgraph, where $k=\frac{1}{\varepsilon}+1$.

###### Proof.

Suppose to the contrary that $G$ contains a copy of some half graph
$H\in\mathcal{H}_{k}$ with vertex set $\\{x_{i},y_{i}:\leavevmode\nobreak\
i\in[k]\\}$. As $G$ is $\varepsilon$-ultra maximal $K_{r}$-free and
$x_{i}y_{i}\notin E(G)$ for all $i\in[k]$, the induced subgraph
$G[N(x_{i},y_{i})]$ contains at least $\varepsilon n^{r-2}$ many
$(r-2)$-cliques. By the pigeonhole principle, there must exist a copy of
$K_{r-2}$ lying in at least $\lceil\frac{k\varepsilon
n^{r-2}}{\binom{n}{r-2}}\rceil\geq\lceil k\varepsilon\rceil\geq 2$ common
neighborhood of distinct pairs, say $G[N(x_{i},y_{i})]$ and
$G[N(x_{j},y_{j})]$ with $1\leq j<i\leq k$. Then, as $x_{i}y_{j}\in E(G)$,
this copy of $K_{r-2}$ together with $x_{i}$ and $y_{j}$ forms a copy of
$K_{r}$, a contradiction. ∎

######  Lemma 2.23.

Let $\varepsilon>0$, $r\geq 3$ and $G$ be an $\varepsilon$-ultra maximal
$K_{r}$-free graph. If $G$ contains a bipartite induced matching of size $t$,
then $G$ contains a copy of some graph $H\in\mathcal{H}_{k}$ as a subgraph,
where $k=\log t/\log\frac{2}{\varepsilon}$.

###### Proof.

We first establish the following claim, which will be used iteratively to
build a large half graph from a large bipartite induced matching.

######  Claim 2.24.

Let $a_{1},\ldots,a_{q}$ and $b_{1}$ be vertices with $q\geq 2/\varepsilon$,
$a_{1}b_{1}\in E(G)$ and $a_{i}b_{1}\notin E(G)$ for all $2\leq i\leq q$. Then
there exists a vertex $c_{1}$ such that $a_{1}c_{1}\notin E(G)$ and
$a_{i}c_{1}\in E(G)$ for $2\leq i\leq\varepsilon q/2+1$.

###### Proof of claim.

Consider the set of non-adjacent pairs $\\{a_{i},b_{1}\\}$, $2\leq i\leq q$.
By assumption, for each such non-adjacent pair there are at least $\varepsilon
n^{r-2}$ many $(r-2)$-cliques in $G[N(a_{i},b_{1})]$. Then, by the pigeonhole
principle, there exists a copy $K$ of $(r-2)$-clique lying in at least
$\frac{(q-1)\varepsilon n^{r-2}}{\binom{n}{r-2}}\geq\varepsilon q/2$ many
common neighborhood of distinct pairs $\\{a_{i},b_{1}\\}$. By relabelling if
necessary, we may assume that $K$ lies in $G[N(a_{i},b_{1})]$ for $2\leq
i\leq\varepsilon q/2+1$. Note that, the vertex $a_{1}$ cannot be adjacent to
all vertices in $K$ for otherwise $K$ together with $a_{1}$ and $b_{1}$ would
form a copy of $K_{r}$. Therefore, we can pick a vertex $c_{1}$ in $K$ such
that $a_{1}c_{1}\notin E(G)$ and $a_{i}c_{1}\in E(G)$ for $2\leq
i\leq\varepsilon q/2+1$ as desired. ∎

We now build a large half graph. Let $\\{x_{i}z_{i}\\}_{i\in[t]}$ be a
bipartite induced matching in $G$. In the first round, applying 2.24 with
$(a_{i},q,b_{1})=(x_{i},t,z_{1})$, we obtain a vertex $y_{1}$ such that
$x_{1}y_{1}\notin E(G)$ and $x_{i}y_{1}\in E(G)$ for $2\leq i\leq\varepsilon
t/2+1$. In general, for $2\leq j\leq k$, in the $j$-th round, we apply 2.24
with $(a_{i},q,b_{1})=(x_{i+j-1},(\frac{\varepsilon}{2})^{j-1}t,z_{j})$, we
obtain a vertex $y_{j}$ such that $x_{j}y_{j}\notin E(G)$ and $x_{i}y_{j}\in
E(G)$ for $j+1\leq i\leq(\frac{\varepsilon}{2})^{j}t+j$. Since
$t\geq(\frac{2}{\varepsilon})^{k}$, we can indeed invoke 2.24 for $k$ rounds
to obtain vertices $y_{1},\ldots,y_{k}$. Note that all $y_{i}$ vertices are
distinct as for any $1\leq j<i\leq k$, $x_{i}y_{j}\in E(G)$ but
$x_{i}y_{i}\notin E(G)$. Then, $\\{x_{i},y_{i}:\leavevmode\nobreak\
i\in[k]\\}$ induces a half graph in ${\mathcal{H}}_{k}$ with $k=\log
t/\log\frac{2}{\varepsilon}$ as desired. ∎

Theorem 2.15 now follows immediately from Lemmas 2.22 and 2.23.

###  2.6 Beyond $\chi$-boundedness, an $(r,2)$-theorem for ${\mathcal{C}}(G)$

In this subsection, we prove Theorem 1.4, which strengthens Theorems 1.1 and
1.3. The idea is to utilize weak $\varepsilon$-nets for the convexity space
${\mathcal{C}}(G)$ instead of $\varepsilon$-nets for ${\mathcal{B}}(G)$. Then
we use the equivalence of weak $\varepsilon$-nets theorem (Theorem 2.29),
Radon’s lemma (Theorem 2.30) and fractionally Helly theorem (Theorem 2.32) for
a convexity space to derive the desired $(r,2)$-theorem for
${\mathcal{C}}(G)$.

We shall need the following results for convexity spaces.

######  Lemma 2.25 (Weak $\varepsilon$-net $\Rightarrow$ Radon [43]).

Let $(X,{\mathcal{C}})$ be a convexity space. If the Radon number of
${\mathcal{C}}$ is greater than $r>0$, then there is a probability measure
$\mu$ on $X$ such that every weak $\varepsilon$-net for ${\mathcal{C}}$ with
respect to $\mu$ has size at least $(1-2\varepsilon)r$.

######  Theorem 2.26 (Radon $\Rightarrow$ fractional Helly [31]).

Every convexity space with Radon number $r$ has fractional Helly number at
most $r^{r^{\lceil\log_{2}r\rceil}}$.

######  Theorem 2.27 ([43]).

Let $X$ be a set and $\mathcal{F}\subseteq 2^{X}$ be a compact family with VC-
dimension $d$ and Helly number $h$. Then for every $\varepsilon>0$, the
intersection closure ${\mathcal{F}}^{\cap}$ has weak $\varepsilon$-nets of
size at most $(120h^{2}/\varepsilon)^{4hd\log(1/\varepsilon)}$.

We will use the following consequence of Theorem 2.27.

######  Corollary 2.28.

Let $X$ be a set and $\mathcal{F}\subseteq 2^{X}$ be a compact family with VC-
dimension $d$ and Helly number $h$. Then for any finite set system
${\mathcal{G}}\subseteq{\mathcal{F}}^{\cap}$, we have
$\tau(\mathcal{G})\leq(120h^{2}\tau^{*}({\mathcal{G}}))^{4hd\log\tau^{*}({\mathcal{G}})}$.

###### Proof.

Let $t^{*}=\tau^{*}({\mathcal{G}})$ and $f(\cdot)$ be an optimal fractional
transversal of ${\mathcal{G}}$ assigning each point $p\in X$ with weight
$m_{p}/D$, where $m_{p},D\in{\mathbbm{N}}$. So, $\sum\limits_{p\in
X}\frac{m_{p}}{D}=t^{*}$ and $\sum\limits_{p\in A}\frac{m_{p}}{D}\geq 1$ for
each $A\in\mathcal{G}$. Now define a finitely supported probability measure
$\mu$ on $X$ by setting $\mu(p)=\frac{m_{p}/D}{t^{*}}$. Then, for each
$A\in\mathcal{G}$, $\mu(A)=\sum\limits_{p\in
A}\frac{m_{p}/D}{t^{*}}\geq\frac{1}{t^{*}}$. Thus, any weak
$\frac{1}{t^{*}}$-net for ${\mathcal{F}}^{\cap}$ with respect to $\mu$ is a
transversal of $\mathcal{G}$. The desired bound on $\tau({\mathcal{G}})$ then
follows from Theorem 2.27 with $\varepsilon_{\ref{thm:WeakEpsRadon}}=1/t^{*}$.
∎

Combining Theorem 2.27, 2.28 with 2.10 and Lemma 2.13, we obtain the following
weak $\varepsilon$-net theorem for the convexity space ${\mathcal{C}}(G)$
derived from a graph $G$.

######  Theorem 2.29 (Weak $\varepsilon$-net for ${\mathcal{C}}(G)$).

For any graph $G$ and $\varepsilon>0$, the convexity space ${\mathcal{C}}(G)$
has weak $\varepsilon$-nets of size at most
$(480/\varepsilon)^{8\nu_{\mathrm{bi}}(G)\log(1/\varepsilon)}$. In other
words, for any set system ${\mathcal{G}}\subseteq{\mathcal{C}}(G)$, we have

$\tau({\mathcal{G}})\leq(480\tau^{*}({\mathcal{G}}))^{8\nu_{\mathrm{bi}}(G)\log\tau^{*}({\mathcal{G}})}.$

Applying Theorem 2.29 and Lemma 2.25 with $\varepsilon_{\ref{thm:weak-eps-
net-C}}=\varepsilon_{\ref{lem:weak-eps-Radon}}=1/4$, we infer that the Radon
number of the convexity space ${\mathcal{C}}(G)$ is bounded by the bipartite
induced matching number of $G$.

######  Theorem 2.30 (Radon for ${\mathcal{C}}(G)$).

For any graph $G$, the Radon number of the convexity space ${\mathcal{C}}(G)$
is at most $2^{300\nu_{\mathrm{bi}}(G)}$.

######  Remark 2.31.

Let us see the effect of bounded Radon number on the graph $G$ using the
correspondence in Table 1. If $r({\mathcal{C}}(G))=r=O(1)$, then for any
maximal independent sets $I_{1},\ldots,I_{r}$, there is a partition $[r]=A\cup
B$ s.t. $K_{\cap_{a\in A}I_{a}}\cap K_{\cap_{b\in B}I_{b}}\neq\varnothing$,
that is, $e(\cap_{a\in A}I_{a},\cap_{b\in B}I_{b})=0$. Note that between any
two $I_{j}$ there is at least one edge by maximality. So the convexity space
${\mathcal{C}}(G)$ having bounded Radon number reflects in a sense that
$\mathrm{MIS}(G)$ has bounded structure.

A fractional Helly theorem for ${\mathcal{C}}(G)$ now follows from Theorems
2.30 and 2.26.

######  Theorem 2.32 (Fractional Helly for ${\mathcal{C}}(G)$).

For any graph $G$, the fractional Helly number of the convexity space
${\mathcal{C}}(G)$ is at most $2^{2^{10^{5}\nu_{\mathrm{bi}}(G)^{2}}}$.

Finally, putting everything together, we can prove Theorem 1.4.

###### Proof of Theorem 1.4.

As any upper bound on Helly number or fractional Helly number on
${\mathcal{C}}(G)$ is inherited by all its subfamilies, by 2.10 and Theorem
2.32, we see that ${\mathcal{G}}$ satisfies $h({\mathcal{G}})=2$ and
$h^{*}({\mathcal{G}})=O_{t}(1)$. Thus, from Theorem 2.19, we get that
$\tau^{*}({\mathcal{G}})=O_{r,t}(1)$. Then Theorem 2.29 infers that
$\tau({\mathcal{G}})=O_{r,t}(1)$. Finally, the ‘In particular’ part follows
from Theorem 2.15. ∎

##  3 Distinguishing chromatic and homomorphism thresholds

Coincidentally, the chromatic and homomorphism thresholds for cliques have the
same value. In this section, we prove Theorem 1.5 via a construction to see
the difference between these two problems.

Let us first see the role of VC-dimension. A graph $G$ has VC-dimension $d$ if
the set system $\mathcal{F}:=\\{N_{G}(v)\subseteq V(G):v\in V(G)\\}$ induced
by the neighborhood of vertices in $G$ has VC-dimension $d$. In this case of
triangle, we know that
$\delta_{\chi}(K_{3})=\delta_{\textup{hom}}(K_{3})=\frac{1}{3}$. Łuczak and
Thomassé [38] later proved that if a triangle-free graph has bounded VC-
dimension, then any linear minimum degree $\delta(G)=\Omega(n)$ suffices to
force bounded chromatic number (see Theorem 5.1 for a short new proof).

In contrast, Theorem 1.5 shows that VC-dimension is not sufficient to force a
bounded triangle-free homomorphic image.

We start with the following construction.

######  Construction 3.1.

Let $t\geq 3$ and $\Gamma$ be a $t$-vertex maximal triangle-free graph on
vertex set $\\{z_{i}\\}_{i\in[t]}$.

  * •

Let $M_{t,t}$ be the bipartite graph obtained from removing a perfect matching
from the complete bipartite graph $K_{t,t}$. That is,
$V(M_{t,t})=\\{x_{i},y_{i}\\}_{i\in[t]}$ and $x_{i}y_{j}\in E(M_{t,t})$ if and
only if $i\neq j$.

  * •

Let $M_{t,t}\vee\Gamma$ be the graph obtained from taking disjoint union of
$M_{t,t}$ and $\Gamma$, and adding edges $x_{i}z_{i}$, $y_{i}z_{i}$ for all
$i\in[t]$.

  * •

Let $\Gamma[a,b]$ be the graph obtained from $M_{t,t}\vee\Gamma$ by blowing up
each vertex in $M_{t,t}$ into $a$ copies and each vertex in $\Gamma$ into $b$
copies.

$x_{4}$$x_{3}$$x_{2}$$x_{1}$$y_{4}$$y_{3}$$y_{2}$$y_{1}$$\Gamma$$z_{2}$ Figure
3.1: $t=4$ in 3.1

$a_{4}$$a_{3}$$a_{2}$$a_{1}$$b_{4}$$b_{3}$$b_{2}$$b_{1}$$c_{1}^{(1)}$$c_{1}^{(2)}$$c_{2}^{(1)}$$c_{2}^{(2)}$$d_{1}^{(1)}$$d_{1}^{(2)}$$d_{2}^{(1)}$$d_{2}^{(2)}$
Figure 3.2: $K_{2,2}[1,2]$

It is easy to check that the graph $\Gamma[a,b]$ is maximal triangle-free with
$(2a+b)t$ vertices and minimum degree $\min\\{(t-1)a+b,\leavevmode\nobreak\
2a+\delta(\Gamma)b\\}$. Furthermore, the VC-dimension of $\Gamma[a,b]$ depends
only on $\Gamma$. Thus, for any $\Gamma$ with sufficiently large order $t$,
bounded VC-dimension and minimum degree $\delta(\Gamma)=\Omega(t)$ and
$a,b=O(1)$, $G=\Gamma[a,b]$ is a maximal triangle-free graph with minimum
degree $\Omega(|G|)$ and bounded VC-dimension.

Next, we identify the obstruction for a graph to have a small triangle-free
homomorphic image.

######  Lemma 3.2.

If a graph $G$ contains $t$ vertices $x_{1},\ldots,x_{t}$ such that between
any two distinct $x_{i},x_{j}$ there is an induced 4-vertex path $P_{4}$, then
$G$ has no triangle-free homomorphic image of size smaller than $t$.

###### Proof.

Let $F$ be a triangle-free homomorphic image of $G$ with
$\varphi:G\xrightarrow{\textup{hom}}F$. It suffices to show that every vertex
$x_{i}$, $i\in[t]$, must be mapped to a distinct vertex in $F$. Suppose there
are two distinct $x_{i}$, $x_{j}$ such that $\varphi(x_{i})=\varphi(x_{j})$.
By assumption, there exist vertices $y,z$ such that $x_{i}yzx_{j}$ is an
induced $P_{4}$. Then $\varphi(x_{i})$, $\varphi(y)$ and $\varphi(z)$ form a
triangle in $F$, a contradiction. ∎

######  Proposition 3.3.

The graph $\Gamma[a,b]$ in 3.1 does not have any triangle-free homomorphic
image of size smaller than $t$.

###### Proof.

By construction, between any two distinct $x_{i},x_{j}$ in $\Gamma[a,b]$,
$x_{i}z_{i}y_{i}x_{j}$ is an induced $P_{4}$. The conclusion then follows from
Lemma 3.2. ∎

###  3.1 Proof of Theorem 1.5

We shall prove that $G=K_{\frac{n}{8},\frac{n}{8}}[1,2]$ has the desired
properties. Let $V(G)=A\cup B\cup C\cup D$, where $A=\\{a_{i}\\}_{i\in[n/4]}$,
$B=\\{b_{i}\\}_{i\in[n/4]}$, $C=\\{c_{i}^{(1)},c_{i}^{(2)}\\}_{i\in[n/8]}$ and
$D:=\\{d_{i}^{(1)},d_{i}^{(2)}\\}_{i\in[n/8]}$ are independent sets, and
$A\cup B$ induces $M_{n/4,n/4}$ with $a_{i}b_{i}\notin E(G)$, $C\cup D$
induces $K_{n/4,n/4}$ and
$a_{i}c_{i}^{(k)},b_{i}c_{i}^{(k)},a_{i+n/8}d_{i}^{(k)},b_{i+n/8}d_{i}^{(k)}\in
E(G)$ for all $i\in[n/8]$ and $k\in\\{1,2\\}$.

By construction, the minimum degree of $G$ is at least $\frac{n}{4}$. Theorem
1.5 follows from 3.3 (with $t=\frac{n}{4}$) and the following result.

######  Proposition 3.4.

The VC-dimension of $G=K_{\frac{n}{8},\frac{n}{8}}[1,2]$ is at most $3$.

###### Proof.

Let $S\subseteq V(G)$ be a nonempty subset shattered by
$\mathcal{F}:=\\{N_{G}(v)\subseteq V(G):v\in V(G)\\}$. Then, for every subset
$S^{\prime}\subseteq S$, there is a vertex $v_{S^{\prime}}$ such that
$N_{G}(v_{S^{\prime}})\cap S=S^{\prime}$. As $G$ is triangle-free, for every
vertex $v\in V(G)$, $N_{G}(v)$ is an independent set; in particular,
$S\subseteq N_{G}(v_{S})$ is an independent set. Then, $S\cap(A\cup B)$ is
either $\\{a_{i},b_{i}\\}$ for some $i\in[\frac{n}{4}]$, or a subset of $A$ or
$B$. Similarly, $S\cap(C\cup D)$ is a subset of $C$ or $D$.

Suppose that $S\cap(A\cup B)=\\{a_{i},b_{i}\\}$ for some $i\in[\frac{n}{4}]$.
Since $S\cap C$ and $S\cap D$ cannot both be nonempty, we can assume without
loss of generality that $S\cap C\neq\emptyset$. If $|S\cap C|=1$, then we are
done. Otherwise, if $S\cap C$ contains at least two vertices, say
$c,c^{\prime}\in C$, then, by our construction of $G$,
$v_{\\{a_{i},b_{i},c\\}}$ can only be in $D$. But then we would also have
$c^{\prime}\in N_{G}(v_{\\{a_{i},b_{i},c\\}})\cap S$, a contradiction. So, $S$
has size at most $3$ in this case.

Next, by symmetry, suppose that $S\cap(A\cup B)\subseteq A$ and $S\cap(C\cup
D)\subseteq C$. Suppose that $S\cap(C\cup D)$ contains at least three
vertices, say $c_{1},c_{2},c_{3}\in C$, then $N_{G}(c_{i})\neq N_{G}(c_{j})$
for any distinct $i,j\in[3]$, as otherwise there is no choice for
$v_{\\{c_{i}\\}}$. Consequently, there is no $k\in[\frac{n}{8}]$ so that
$\\{c_{1},c_{2}\\}=\\{c_{k}^{(1)},c_{k}^{(2)}\\}$, which implies that
$v_{\\{c_{1},c_{2}\\}}$ can only be in $D$. However, we would also have
$c_{3}\in N_{G}(v_{\\{c_{1},c_{2}\\}})\cap S$, again a contradiction.
Therefore, $|S\cap(C\cup D)|\leq 2$. If $|S\cap(C\cup D)|=2$, similarly
$v_{S}$ must be in $D$. As by assumption $S\cap(A\cup B)\subseteq A$ and every
vertex in $D$ has degree 1 in $A$, we have $|S|\leq 3$.

We may then assume $|S\cap(C\cup D)|\leq 1$. Suppose that $|S\cap(C\cup
D)|=1$. If $S\cap(A\cup B)\subseteq A$ contains three vertices, say
$a_{1},a_{2},a_{3}\in A$, then as every vertex in $D$ has degree $1$ to $A$,
for each $i\in[3]$, $v_{S\setminus\\{a_{i}\\}}$ must lie in $B$. But
$S\setminus\\{a_{i}\\}$ contains a vertex in $C$ that has degree $1$ in $B$,
implying that there is at most one vertex in $B$ that could be
$v_{S\setminus\\{a_{i}\\}}$ for some $i\in[3]$, a contradiction. Thus, in this
case $|S\cap(A\cup B)|\leq 2$ and $|S|\leq 3$.

Lastly, we assume $S\cap(C\cup D)=\varnothing$. If $|S\cap(A\cup B)|\geq 4$,
then there is no vertex adjacent to exactly two vertices in $S\cap(A\cup
B)\subseteq A$, a contradiction. Hence $|S|=|S\cap(A\cup B)|\leq 3$, finishing
the proof. ∎

We remark that $G=K_{\frac{n}{8},\frac{n}{8}}[1,2]$ is triangle-free and has
large minimum degree, but $G$ is not $\varepsilon$-ultra maximal $K_{3}$-free
as $|N_{G}(a_{i},b_{i})|=2$. This also shows that the ultra $K_{r}$-freeness
is more important to determine the structure of homomorphic images of dense
$K_{r}$-free graphs.

##  4 Sharp blow-up phenomenon

###  4.1 Proof of Theorem 1.6

The main tool used in the proof of Theorem 1.6 is the packing lemma of
Haussler [27]. To state it, we need some notations. In a set system
${\mathcal{F}}\subseteq 2^{V}$, we say that $v$ _splits_
$F_{1},F_{2}\in{\mathcal{F}}$ if $v$ belongs to exactly one of $F_{1}$ and
$F_{2}$, i.e. $v\in F_{1}\triangle F_{2}$. A subfamily
$\mathcal{X}\subseteq\mathcal{F}$ is _$s$ -separated_ if for every pair in
${\mathcal{X}}$ is splitted by at least $s$ elements in $V$. Haussler [27]
proved that the size of an $s$-separated subfamily in a set system can be
bounded using its VC-dimension.

######  Lemma 4.1 ([27]).

Let $\mathcal{F}\subseteq 2^{V}$ be a set system with VC-dimension $d$. If
$\mathcal{X}\subseteq\mathcal{F}$ is $s$-separated, then $|\mathcal{X}|\leq
e(d+1)\big{(}\frac{2e|\mathcal{F}|}{s}\big{)}^{d}$.

###### Proof of Theorem 1.6.

Let $M_{t,t}$ be the graph obtained by removing a perfect matching from
$K_{t,t}$. Let $\mathcal{M}_{t,t}$ be the family of graphs obtained by adding
every possible set of edges to the two vertex parts of $M_{t,t}$; that is,
$\mathcal{M}_{t,t}$ consists of all graphs $F$ with vertices
$\\{a_{i},b_{i}\\}_{i\in[t]}$ such that $a_{i}b_{j}\in E(F)$ if and only if
$i\neq j$ for all $i,j\in[t]$, where we put no restriction on
$F[\\{a_{1},\ldots,a_{t}\\}]$ and $F[\\{b_{1},\ldots,b_{t}\\}]$. It is clear
that $\mathcal{M}_{t,t}$ is a subfamily of $\mathcal{H}_{t}$ defined in
Section 2.5. Setting $t:=\frac{1}{\varepsilon}+1$, we infer from Lemma 2.22
that $G$ is $\mathcal{M}_{t,t}$-free. Combining $K_{r}$-freeness and
$\mathcal{M}_{t,t}$-freeness, we can bound the VC-dimension of $G$.

######  Claim 4.2.

The VC-dimension of $G$ is at most $t+r-4$.

###### Proof of claim.

Suppose for contradiction that the VC-dimension of $G$ is at least $t+r-3$.
Then, there is a $(t+r-3)$-set $A=\\{a_{1},\ldots,a_{t+r-3}\\}$ such that for
each subset $S\subseteq A$, there exists a vertex $v_{S}\in V(G)$ with
$N(v_{S})\cap A=S$. In particular, letting $b_{i}=v_{A\setminus\\{a_{i}\\}}$
for each $i\in[t+r-3]$, we have $N(b_{i})\cap A=A\setminus\\{a_{i}\\}$. Let
$B=\\{b_{1},\ldots,b_{t+r-3}\\}$.

As $G$ is $K_{r}$-free, it is not hard to see that $|A\cap B|\leq r-3$.
Indeed, suppose otherwise that $|A\cap B|\geq r-2$. As for each $i\in[t+r-3]$,
$b_{i}$ is adjacent to all vertices in $A$ except for $a_{i}$, we have that
$a_{i}\neq b_{j}$ for every distinct $i,j$. Therefore, for any vertex $c\in
A\cap B$, we must have $c=a_{i}=b_{i}$ for some $i\in[t+r-3]$. Assume without
loss of generality that $a_{i}=b_{i}$ for $i\in[r-2]$. Then
$v_{A},a_{1},\ldots,a_{r-2}$ together with any vertex in
$A\setminus\\{a_{1},\ldots,a_{r-2}\\}$ form a copy of $K_{r}$, a
contradiction.

As $|A|=|B|=t+r-3$ and $|A\cap B|\leq r-3$, by the construction of $A$ and
$B$, we can find $2t$ distinct vertices
$\\{a^{\prime}_{i}\\}_{i\in[t]}\subseteq A\setminus B$ and
$\\{b^{\prime}_{i}\\}_{i\in[t]}\subseteq B\setminus A$ such that
$\\{a^{\prime}_{i},b^{\prime}_{i}\\}_{i\in[t]}$ induces a copy of some graph
in $\mathcal{M}_{t,t}$, a contradiction. ∎

Let $\mathcal{F}:=\\{N(v):v\in V(G)\\}$ and
$s=\frac{\varepsilon|\mathcal{F}|}{10}$. Let
$\mathcal{X}:=\\{N(v_{1}),N(v_{2}),\ldots,N(v_{m})\\}$ be a maximal
$(s+1)$-separated subfamily of ${\mathcal{F}}$. By Lemma 4.1 and 4.2, $m\leq
e(d+1)(\frac{2e|\mathcal{F}|}{s+1})^{d}=(\frac{1}{\varepsilon})^{O(\frac{1}{\varepsilon}+r)}$.
We then partition $V(G)=V_{1}\cup V_{2}\cup\cdots\cup V_{m}$ as follows. For
every $v\in V(G)$, let $v\in V_{i}$ where $i\in[m]$ is the smallest index such
that $|N(v)\triangle N(v_{i})|\leq s$; such an index $i$ exists by the
maximality of $\mathcal{X}$. Note that by the construction of our partition
and the triangle inequality, every pair of vertices $u,v$ in the same part
$V_{i}$ satisfies $|N(u)\triangle N(v)|\leq|N(u)\triangle
N(v_{i})|+|N(v)\triangle N(v_{i})|\leq 2s$.

######  Claim 4.3.

For any $i\in[m]$, $v,w\in V_{i}$, there is no $u\in V(G)$ with $uv\in E(G)$
but $uw\notin E(G)$.

###### Proof of claim.

By assumption, $G[N(u,w)]$ contains $\varepsilon n^{r-2}$ copies of $K_{r-2}$.
Since $v,w$ lies in the same part $V_{i}$, $|N(w)\setminus N(v)|\leq 2s$.
Thus, the number of $(r-2)$-cliques in $G[N(u,w)]$ with at least one vertex
lying in $N(w)\setminus N(v)$ is at most $2sn^{r-3}<\frac{\varepsilon
n^{r-2}}{2}$, and so there is a copy of $K_{r-2}$ in $G[N(u,v)]$,
contradicting $G$ being $K_{r}$-free. ∎

For two disjoint subsets $A,B\subseteq V(G)$, we say that $A$ and $B$ are
_complete_ to each other if every vertex of $A$ is adjacent to every vertex of
$B$, and _anti-complete_ to each other if no vertex of $A$ is adjacent to any
vertex of $B$.

######  Claim 4.4.

For each pair of distinct $i,j\in[m]$, $V_{i}$ and $V_{j}$ are either
complete, or anti-complete.

###### Proof of claim.

If $|V_{i}|=|V_{j}|=1$, then we are done. Suppose that $V_{i}$ and $V_{j}$ are
neither complete, nor anti-complete. Then, without loss of generality, there
exist $v,w\in V_{i}$ and $u\in V_{j}$ such that $uv\in E(G)$ and $uw\notin
E(G)$, contradicting 4.3. ∎

######  Claim 4.5.

For each $i\in[m]$, if $|V_{i}|\geq r$, then $V_{i}$ is an independent set.

###### Proof of claim.

Since $|V_{i}|\geq r$, $G[V_{i}]$ cannot be a clique. Suppose that $V_{i}$ is
not an independent set, then there exists a triple $v,w,u\in V_{i}$ such that
$uv\in E(G)$ and $uw\notin E(G)$, again contradicting 4.3. ∎

Finally, if any $V_{i}$ has size smaller than $r$, further partition $V_{i}$
into $|V_{i}|$ singletons. 4.4 and 4.5 imply that $G=F[\cdot]$, where clearly
$F$ is maximal $K_{r}$-free and
$|F|\leq(r-1)m=(\frac{1}{\varepsilon})^{O(\frac{1}{\varepsilon}+r)}$. ∎

###  4.2 Proof of Theorem 1.7

We first prove that the theorem holds for the case $r=3$.

######  Lemma 4.6.

There exists an $n$-vertex triangle-free graph $G$ such that for any pair of
non-adjacent vertices $u,v$, $|N_{G}(u,v)|\geq\varepsilon n$, but $G$ has no
triangle-free homomorphic image of size smaller than
$2^{\frac{1}{8\varepsilon}}$.

###### Proof.

Let $d=\lfloor\frac{1}{8\varepsilon}-\frac{1}{2}\rfloor$ and note that
$\varepsilon\leq\frac{1}{8d+4}$. Let $H$ be a graph on vertex set $D\cup Q$,
where $D=\\{a_{i}^{(0)},a_{i}^{(1)}\\}_{i\in[d]}$ and $Q=\\{0,1\\}^{d}$.
Clearly, $H$ has $2d+2^{d}$ vertices. For each $\bm{u}\in Q$, write
$\bar{\bm{u}}=\bm{1}-\bm{u}$, where $\bm{1}$ is the all one vector. The edge
set $E(H)$ is defined as follows:

  * •

$a_{i}^{(0)}a_{i}^{(1)}\in E(H)$ for each $i\in[d]$;

  * •

$\bm{u}\bar{\bm{u}}\in E(H)$ for each $\bm{u}\in Q$;

  * •

each $\bm{u}=(u_{1},u_{2},\ldots,u_{d})\in Q$ is adjacent to $d$ vertices
$\\{a_{1}^{(u_{1})},\ldots,a_{d}^{(u_{d})}\\}\subseteq D$.

Let us observe some properties of $H$. It is easy to see that the graph $H$ is
maximal triangle-free.

######  Claim 4.7.

In $H$, the set $Q$ contains $2^{d-1}$ vertices between any pair of which
there is an induced $P_{4}$. In particular, $H$ has no triangle-free
homomorphic image of size smaller than $2^{d-1}$.

###### Proof of claim.

By construction, the subgraph of $H$ induced on $Q$ is a perfect matching $M$
of size $2^{d-1}$. Let $X\subseteq Q$ be an independent set of $2^{d-1}$
vertices containing exactly one endpoint of an edge in $M$. Then, for any two
distinct vertices $\bm{u}=(u_{1},\ldots,u_{d}),\bm{v}=(v_{1},\ldots,v_{d})\in
X$, they must differ at some coordinate, say $u_{i}=1$ and $v_{i}=0$ for some
$i\in[d]$. Then $\bm{u}a_{i}^{(1)}a_{i}^{(0)}\bm{v}$ is an induced $P_{4}$.
The rest then follows from Lemma 3.2. ∎

Next, let $G$ be a graph obtained from $H$ by blowing up each vertex
$a_{i}^{(j)}$ in $D$ to a set $A_{i}^{(j)}$ of $2^{d}$ identical copies. Let
$V(G)=P\cup Q$, where $P=\bigcup_{i\in[d]}(A_{i}^{(0)}\cup A_{i}^{(1)})$. The
graph $G$ satisfies the required co-degree condition.

######  Claim 4.8.

For each non-adjacent pair of vertices $u,v$ in $G$, $|N_{G}(u,v)|\geq
2^{d-2}$.

###### Proof of claim.

Consider the following cases.

  1. Case 1.

If both of $u,v$ belong to $Q$, then write them as $\bm{u}$ and $\bm{v}$.
Since $\bm{u}\bm{v}\notin E(G)$, we have $\bm{u}\neq\bar{\bm{v}}$. Therefore,
there exists some coordinate $j\in[d]$ such that $u_{j}=v_{j}$, which implies
that $A_{j}^{(u_{j})}\subseteq N_{G}(\bm{u},\bm{v})$, and therefore
$|N_{G}(\bm{u},\bm{v})|\geq 2^{d}$.

  2. Case 2.

If $\bm{u}\in Q$ and $v\in P$. Assume without loss of generality that $v\in
A_{i}^{(0)}$, then $\bm{u}v\notin E(G)$ implies that $u_{i}\neq 0$. Then
$A_{i}^{(1)}\subseteq N_{G}(\bm{u},v)$, and therefore $|N_{G}(\bm{u},v)|\geq
2^{d}$.

  3. Case 3.

If $u,v\in P$ and they are copies of the same vertex in $D$, say $u,v\in
A_{j}^{(0)}$ for some $j\in[d]$, then $A_{j}^{(1)}\subseteq N_{G}(u,v)$, and
so $|N_{G}(u,v)|\geq 2^{d}$.

  4. Case 4.

If $u,v\in P$ but they are copies of distinct vertices in $D$. Suppose that
$u\in A_{i}^{(x)}$ and $v\in A_{j}^{(y)}$ for distinct $i,j\in[d]$ and some
$x,y\in\\{0,1\\}$, then $\\{\bm{w}\in Q:w_{i}=x\textup{\leavevmode\nobreak\
and\leavevmode\nobreak\ }w_{j}=y\\}\subseteq N_{G}(u,v)$, which implies that
$|N_{G}(u,v)|\geq 2^{d-2}$.

The proof of the claim is complete. ∎

Thus, $G$ is a triangle-free graph with $n=(2d+1)2^{d}$ vertices such that any
non-adjacent pair of vertices has $2^{d-2}=\frac{n}{8d+4}\geq\varepsilon n$
common neighbors. Moreover, as $G$ is a blow-up of $H$, by 4.7, $G$ has no
triangle-free homomorphic image of size smaller than $2^{d-1}\leq
2^{\frac{1}{8\varepsilon}}$ as desired. ∎

For larger $r\geq 4$, let us take an $(r-2)$-partite Turán graph
$T_{(r-2)n,r-2}$ and add a copy of $G$ into one of its partite set. It is easy
to check that the resulting graph is $\alpha$-ultra maximal $K_{r}$-free,
where $\alpha=\frac{\varepsilon}{r^{r}}$ and has no $K_{r}$-free homomorphic
image of size $2^{\frac{1}{8\varepsilon}}=2^{\frac{1}{8\alpha r^{r}}}$.

Addressing 2.17, we note that the induced subgraph $G[Q]$ is an induced
matching of size $2^{d-1}$ with parts say $L\cup R$. Then $L$ is shattered by
${\mathcal{M}}(G)$ and so ${\mathcal{M}}(G)$ has VC-dimension at least
$2^{d-1}=2^{\Omega(\frac{1}{\varepsilon})}$.

###  4.3 Proof of 1.8

We first show that the minimum degree condition is a stronger condition than
the ultra $K_{r}$-freeness condition. The converse is obviously not true by
considering a blow-up of a large maximal $K_{r}$-free graph.

######  Proposition 4.9.

Let $\varepsilon>0$ and $G$ be an $n$-vertex maximal $K_{r}$-free graph with
$\delta(G)\geq(\frac{2r-5}{2r-3}+\varepsilon)n$, then $G$ is
$\varepsilon^{r-2}$-ultra maximal $K_{r}$-free.

###### Proof.

Let $S\subseteq V$ be a set of vertices and $N(S)$ be the set of common
neighborhood of vertices in $S$. Note that for any $S\subseteq V(G)$,
$|N(S)|\geq|S|\cdot\delta(G)-(|S|-1)n$. Let $u,v$ be a non-adjacent pair of
vertices in $G$. Then for any $r-3$ vertices $w_{1},w_{2},\ldots,w_{r-3}\in
V(G)\setminus\\{u,v\\}$, we have

$|N(\\{w_{1},w_{2},\ldots,w_{r-3}\\})|\geq(r-3)\delta(G)-(r-4)n\geq\bigg{(}\frac{3}{2r-3}+(r-3)\varepsilon\bigg{)}n.$

It was proven in [46, Proposition 2.1] that, $N(u,v)\geq
r\delta(G)-(r-2)n\geq(\frac{2r-6}{2r-3}+r\varepsilon)n$.

Therefore, the common neighborhood of $u,v$ and $w_{1},w_{2},\ldots,w_{r-3}$
satisfy

$|N(\\{u,v,w_{1},w_{2},\ldots,w_{r-3}\\})|\geq|N(\\{w_{1},w_{2},\ldots,w_{r-3}\\})|-(n-N(u,v))\geq(2r-3)\varepsilon
n\geq\varepsilon n.$

Therefore, for any fixed non-adjacent pair of vertices $u,v$, we can greedily
pick $r-2$ vertices $z_{1},z_{2},\ldots,z_{r-2}$, where $z_{i}$ lies in the
common neighborhood of $\\{u,v,z_{1},\ldots,z_{i-1}\\}$ and the number of
choices of each $z_{i}$ is at least $\varepsilon n$. Thus, $G$ is
$\varepsilon^{r-2}$-ultra maximal $K_{r}$-free. ∎

######  Proposition 4.10.

For an $n$-vertex graph $G$, if $\delta^{(2)}(G)\geq cn$, then
$\hat{\delta}^{(2,2)}(G)\geq 2-1/c$.

###### Proof.

Pick arbitrary $uv\notin E(G)$ with $d(u,v)=\delta^{(2)}(G)\geq cn$. Let
$G^{\prime}=G[N(u,v)]$ and $n^{\prime}=|G^{\prime}|\geq cn$. It suffices to
show that $\delta(G^{\prime})\geq(2-1/c)n^{\prime}$. Let $w\in V(G^{\prime})$,
then

$d_{G^{\prime}}(w)\geq(\delta(G)-2)+n^{\prime}-(n-2)\geq\delta^{(2)}(G)+n^{\prime}-n=2n^{\prime}-n.$

Thus,
$\frac{\delta(G^{\prime})}{n^{\prime}}\geq\frac{2n^{\prime}-n}{n^{\prime}}\geq
2-1/c$ as desired. ∎

###### Proof of 1.8.

For the lower bound, take the $(r-2)$-partite Turán graph and add to one of
its parts a triangle-free graph with large chromatic number, say $k$. Let the
resulting graph be $H$. Obviously $H$ has no homomorphic image of size at most
$k$ and one can easily check that $\delta^{(a)}(H)=\frac{r-3}{r-2}\cdot n$ and
$\hat{\delta}^{(a,b)}(H)=\pi_{b}(K_{r-2})$, proving the desired lower bound.

For the upper bound, as the condition gets stronger when $a$ increases, we may
assume that $a=2$. We first prove
$\delta^{(2,b)}_{\textup{hom}}(K_{r})\leq\pi_{b}(K_{r-2})$ for each $2\leq
b\leq r-2$. Let $G$ be an $n$-vertex $K_{r}$-free graph with
$\delta^{(2)}(G)=\Omega(n)$ and
$\hat{\delta}^{(a,b)}(G)\geq\pi_{b}(K_{r-2})+\varepsilon$. For any pair of
non-adjacent vertices $u,v$, as $G[N(u,v)]$ has $K_{b}$-density larger than
$\pi_{b}(K_{r-2})$, by a supersaturation version of Erdős’s result [20],
$G[N(u,v)]$ has positive $K_{r-2}$-density. Since
$|N(u,v)|\geq\delta^{(2)}(G)=\Omega(n)$, we get that $G$ is $\Omega(1)$-ultra
maximal $K_{r}$-free and the conclusion follows from Theorem 1.6 applies.

It remains to prove $\delta^{(2)}_{\textup{hom}}(K_{r})\leq\frac{r-3}{r-2}$.
If an $n$-vertex graph $G$ has
$\delta^{(2)}(G)\geq(\frac{r-3}{r-2}+\varepsilon)n$, then by 4.10,
$\hat{\delta}^{(2,2)}(G)\geq\frac{r-4}{r-3}+\varepsilon>\pi_{2}(K_{r-2})$. The
result then follows from the upper bound we proved:
$\delta^{(2,2)}_{\textup{hom}}(K_{r})\leq\pi_{2}(K_{r-2})$. ∎

##  5 Concluding remarks

###  5.1 Thresholds with bounded VC-dimension

Based on the proof of Theorem 1.6, we give a new short proof of the following
result of Łuczak and Thomassé [38].

######  Theorem 5.1.

Let $c>0$ and $d\in{\mathbbm{N}}$. Let $G$ be an $n$-vertex triangle-free
graph with VC-dimension $d$ and minimum degree $\delta(G)\geq cn$, then
$\chi(G)\leq e(d+1)\big{(}\frac{2e}{3c}\big{)}^{d}$.

###### Proof.

Let ${\mathcal{F}}=\\{N_{G}(v):v\in V(G)\\}$. Applying Lemma 4.1 with
$s=\frac{c|\mathcal{F}|}{3}$, we get a partition $V(G)=V_{1}\cup
V_{2}\cup\cdots\cup V_{m}$ with $m\leq e(d+1)\big{(}\frac{2e}{3c}\big{)}^{d}$
such that for any pair of vertices $u,v$ from the same part $V_{i}$,
$|N_{G}(u)\triangle N_{G}(v)|\leq 2s$. This implies that $u,v$ have at least
$cn-2s\geq\frac{cn}{3}$ common neighbors and thus $uv\notin E(G)$ as $G$ is
triangle-free. Hence, each $V_{i}$ is an independent set and $\chi(G)\leq m$.
∎

Motivated by 3.1, we can define the _Bounded-VC chromatic/homomorphism
thresholds_ for graph $H$ as follows:

$\displaystyle\delta_{\chi}^{\textup{VC}}(H):=\inf\big{\\{}\alpha\geq 0:$
$\displaystyle\leavevmode\nobreak\ \forall
d\in{\mathbbm{N}},\exists\leavevmode\nobreak\ C=C(\alpha,H,d)\
\textup{s.t.\leavevmode\nobreak\ }\forall\leavevmode\nobreak\
n\textup{-vertex\ }H\textup{-free}\leavevmode\nobreak\ G,$
$\displaystyle\leavevmode\nobreak\ \mathrm{dim}_{\mathsf{VC}}(G)\leq
d,\leavevmode\nobreak\ \delta(G)\geq\alpha n\Rightarrow\chi(G)\leq
C\big{\\}},$

and

$\displaystyle\delta_{\textup{hom}}^{\textup{VC}}(H):=\inf\big{\\{}\alpha\geq
0:$ $\displaystyle\leavevmode\nobreak\ \forall
d\in{\mathbbm{N}},\exists\leavevmode\nobreak\
H\textup{-free}\leavevmode\nobreak\ \textup{graph}\leavevmode\nobreak\
F=F(\alpha,H,d)\ \textup{s.t.\leavevmode\nobreak\ }\forall\leavevmode\nobreak\
n\textup{-vertex\ }H\textup{-free}\leavevmode\nobreak\ G,$
$\displaystyle\leavevmode\nobreak\ \mathrm{dim}_{\mathsf{VC}}(G)\leq
d,\leavevmode\nobreak\ \delta(G)\geq\alpha n\Rightarrow
G\xrightarrow{\textup{hom}}F\big{\\}}.$

Then Theorem 5.1 implies that $\delta_{\chi}^{\textup{VC}}(K_{3})=0$, while
Theorem 1.5 implies that
$\delta_{\textup{hom}}^{\textup{VC}}(K_{3})\geq\frac{1}{4}$. By adding the
graph from Theorem 1.5 into one part of a complete $(r-2)$-partite graph, we
can obtain that
$\delta^{\textup{VC}}_{\textup{hom}}(K_{r})\geq\frac{3r-8}{3r-5}$. It would be
interesting to determine $\delta^{\textup{VC}}_{\textup{hom}}(K_{r})$. The
following summarize what we know:

$\delta_{\textup{hom}}^{(2,b)}(K_{r})<\cdots<\delta_{\textup{hom}}^{(2,2)}(K_{r})<\delta_{\textup{hom}}^{(2)}(K_{r})=\frac{r-3}{r-2}=\delta_{\chi}^{\textup{VC}}(K_{r})<\frac{3r-8}{3r-5}\leq\delta_{\textup{hom}}^{\textup{VC}}(K_{r})\leq\frac{2r-5}{2r-3}$

###  5.2 Related results on large blow-ups

A well-known result of Nikiforov [44] states that any graph with positive
$K_{r}$-density contains a copy of $\Omega(\log{n})$-size blow-up of $K_{r}$.
Considering random graphs, the logarithmic order is best possible. Some recent
work studies natural conditions that guarantee much larger blow-ups, see e.g.
[48]. Theorem 1.6 can also be viewed as a result of this type, implying that
$\varepsilon$-ultra maximal $K_{r+1}$-freeness guarantees a linear size
$\Omega(n)$, the largest possible, blow-up of $K_{r}$.

######  Corollary 5.2.

Let $G$ be an $\varepsilon$-ultra maximal $K_{r+1}$-free graph, then $G$
contains a copy of $K_{r}[Cn]$, where $C=C(r,\varepsilon)$.

Our results are also related to an old result of Pach [47], where he studied
the property $I_{k}$ which is equivalent to $\delta^{(k)}(G)\geq 1$. Answering
a question of Erdős and Fajtlowics, Pach [47] proved that a triangle-free
graph has the property that every of its independent set has a common neighbor
if and only if it is a blow-up of the Cayley graph on
${\mathbbm{Z}}/(3k-1){\mathbbm{Z}}$ generated by a maximum size sum-free set.
Brandt [11] later extended Pach’s result, showing that a triangle-free graph
$G$ having this property is also equivalent to the property of not containing
any induced $C_{6}$.

###  5.3 Regularity lemma related

As ultra maximal $K_{r}$-free graphs have bounded VC-dimension, by a stronger
version of regularity lemma [23], it admits an almost homogeneous partition,
i.e. the density between most of of pairs are either $o(1)$ or $1-o(1)$. By
Theorem 1.6, we know that such graphs actually have a homogeneous partition.
It is an interesting problem on its own to find natural sufficient conditions
that would allow one to boost an almost homogeneous partition to a homogeneous
one. We refer the interested readers to an alternative proof of Theorem 1.6 in
[36], where we provide one such example.

By Lemma 2.22, ultra maximal $K_{r}$-free graph does not have a large half
graph as subgraph. This is also related to a _stable regularity lemma_ due to
Malliaris and Shelah [39] where they study graphs without a variation of the
half graph considered here. We refer the interested readers to the recent note
[40].

## Acknowledgement

The first author would like to thank Andreas Holmsen for many stimulating
conversations.

## References

  * [1] P. Allen, J. Böttcher, S. Griffiths, Y. Kohayakawa, and R. Morris.  The chromatic thresholds of graphs.  Adv. Math., 235:261–295, 2013.
  * [2] N. Alon, G. Kalai, J. Matoušek, and R. Meshulam.  Transversal numbers for hypergraphs arising in geometry.  Adv. in Appl. Math., 29(1):79–101, 2002.
  * [3] N. Alon and D. J. Kleitman.  Piercing convex sets and the Hadwiger-Debrunner $(p,q)$-problem.  Adv. Math., 96(1):103–112, 1992.
  * [4] N. Amenta, J. A. De Loera, and P. Soberón.  Helly’s theorem: new variations and applications.  In Algebraic and geometric methods in discrete mathematics. AMS special session on algebraic and geometric methods in applied discrete mathematics, San Antonio, TX, USA, January 11, 2015. Proceedings, pages 55–95. Providence, RI: American Mathematical Society (AMS), 2017.
  * [5] B. Andrásfai, P. Erdős, and V. T. Sós.  On the connection between chromatic number, maximal clique and minimal degree of a graph.  Discrete Math., 8:205–218, 1974.
  * [6] I. Bárány.  Combinatorial convexity, volume 77 of University Lecture Series.  American Mathematical Society, Providence, RI, [2021] ©2021.
  * [7] I. Bárány and J. Matoušek.  A fractional Helly theorem for convex lattice sets.  Adv. Math., 174(2):227–235, 2003.
  * [8] I. Bárány and P. Soberón.  Tverberg’s theorem is 50 years old: a survey.  Bull. Amer. Math. Soc. (N.S.), 55(4):459–492, 2018.
  * [9] P. V. M. Blagojević and G. M. Ziegler.  Beyond the Borsuk-Ulam theorem: the topological Tverberg story.  In A journey through discrete mathematics, pages 273–341. Springer, Cham, 2017.
  * [10] S. Brandt.  On the structure of dense triangle-free graphs.  Combin. Probab. Comput., 8(3):237–245, 1999.
  * [11] S. Brandt.  Triangle-free graphs and forbidden subgraphs.  volume 120, pages 25–33. 2002.  Sixth Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1999).
  * [12] S. Brandt and S. Thomassé.  Dense triangle-free graphs are four-colorable: A solution to the Erdős-Simonovits problem.  preprint, 2011.
  * [13] C. C. Chen, G. P. Jin, and K. M. Koh.  Triangle-free graphs with large degree.  Combin. Probab. Comput., 6(4):381–396, 1997.
  * [14] J. A. De Loera, X. Goaoc, F. Meunier, and N. H. Mustafa.  The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg.  Bull. Amer. Math. Soc. (N.S.), 56(3):415–511, 2019.
  * [15] J.-P. Doignon.  Convexity in cristallographical lattices.  J. Geom., 3:71–85, 1973.
  * [16] O. Ebsen and M. Schacht.  Homomorphism thresholds for odd cycles.  Combinatorica, 40(1):39–62, 2020.
  * [17] J. Eckhoff.  Intersection properties of boxes. I. An upper-bound theorem.  Israel J. Math., 62(3):283–301, 1988.
  * [18] J. Eckhoff.  Helly, Radon, and Carathéodory type theorems.  In Handbook of convex geometry, Vol. A, B, pages 389–448. North-Holland, Amsterdam, 1993.
  * [19] P. Erdős.  Graph theory and probability.  Canadian J. Math., 11:34–38, 1959.
  * [20] P. Erdős.  On the number of complete subgraphs contained in certain graphs.  Magyar Tud. Akad. Mat. Kutató Int. Közl., 7:459–464, 1962.
  * [21] P. Erdős and M. Simonovits.  On a valence problem in extremal graph theory.  Discrete Math., 5:323–334, 1973.
  * [22] P. Erdős.  Some recent results on extremal problems in graph theory. (Results).  Theory Graphs, Int. Symp. Rome 1966, 117-123 (English), 124-130 (French) (1967)., 1967.
  * [23] J. Fox, J. Pach, and A. Suk.  Erdős-Hajnal conjecture for graphs with bounded VC-dimension.  Discrete Comput. Geom., 61(4):809–829, 2019.
  * [24] W. Goddard and J. Lyle.  Dense graphs with small clique number.  J. Graph Theory, 66(4):319–331, 2011.
  * [25] H. Hadwiger and H. Debrunner.  Über eine Variante zum Hellyschen Satz.  Arch. Math. (Basel), 8:309–313, 1957.
  * [26] R. Häggkvist.  Odd cycles of specified length in nonbipartite graphs.  In Graph theory (Cambridge, 1981), North-Holland Math. Stud., 62, pages 89–99. 1982.
  * [27] D. Haussler.  Sphere packing numbers for subsets of the Boolean $n$-cube with bounded Vapnik-Chervonenkis dimension.  J. Combin. Theory Ser. A, 69(2):217–232, 1995.
  * [28] D. Haussler and E. Welzl.  $\epsilon$-nets and simplex range queries.  Discrete Comput. Geom., 2(2):127–151, 1987.
  * [29] E. Helly.  Über Mengen konvexer Körper mit gemeinschaftlichen Punkten.  Jahresber. Dtsch. Math.-Ver., 32:175–176, 1923.
  * [30] A. F. Holmsen.  Large cliques in hypergraphs with forbidden substructures.  Combinatorica, 40(4):527–537, 2020.
  * [31] A. F. Holmsen and D. Lee.  Radon numbers and the fractional Helly theorem.  Isr. J. Math., 241(1):433–447, 2021.
  * [32] G. P. Jin.  Triangle-free four-chromatic graphs.  Discrete Math., 145(1-3):151–170, 1995.
  * [33] M. Katchalski and A. Liu.  A problem of geometry in ${\mathbb{R}}^{n}$.  Proc. Amer. Math. Soc., 75(2):284–288, 1979.
  * [34] S. Letzter and R. Snyder.  The homomorphism threshold of $\\{C_{3},C_{5}\\}$-free graphs.  J. Graph Theory, 90(1):83–106, 2019.
  * [35] F. W. Levi.  On Helly’s theorem and the axioms of convexity.  J. Indian Math. Soc. (N.S.), 15(Part):65–76, 1951.
  * [36] H. Liu, C. Shangguan, J. Skokan, and Z. Xu.  Blow-up phenomenon via strong regularity lemma.  www.ibs.re.kr/ecopro/zixiangxu/wp-content/uploads/sites/7/2024/03/SecondProof.pdf, 2024.
  * [37] T. Łuczak.  On the structure of triangle-free graphs of large minimum degree.  Combinatorica, 26(4):489–493, 2006.
  * [38] T. Łuczak and S. Thomassé.  Coloring dense graphs via VC-dimension.  arXiv preprint, arXiv: 1007.1670, 2010.
  * [39] M. Malliaris and S. Shelah.  Regularity lemmas for stable graphs.  Trans. Amer. Math. Soc., 366(3):1551–1585, 2014.
  * [40] M. Malliaris and S. Shelah.  Notes on the stable regularity lemma.  Bull. Symb. Log., 27(4):415–425, 2021.
  * [41] J. Matoušek.  Lectures on discrete geometry, volume 212 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 2002.
  * [42] J. Matoušek.  Bounded VC-dimension implies a fractional Helly theorem.  Discrete Comput. Geom., 31(2):251–255, 2004.
  * [43] S. Moran and A. Yehudayoff.  On weak $\epsilon$-nets and the Radon number.  Discrete Comput. Geom., 64(4):1125–1140, 2020.
  * [44] V. Nikiforov.  Graphs with many $r$-cliques have large complete $r$-partite subgraphs.  Bull. Lond. Math. Soc., 40(1):23–25, 2008.
  * [45] V. Nikiforov.  Chromatic number and minimum degree of ${K}_{r}$-free graphs.  arXiv preprint, arXiv: 1001.2070, 2010.
  * [46] H. Oberkampf and M. Schacht.  On the structure of dense graphs with bounded clique number.  Comb. Probab. Comput., 29(5):641–649, 2020.
  * [47] J. Pach.  Graphs whose every independent set has a common neighbour.  Discrete Math., 37(2-3):217–228, 1981.
  * [48] J. Pach and I. Tomon.  Ordered graphs and large bi-cliques in intersection graphs of curves.  European J. Combin., 82:102994, 12, 2019.
  * [49] J. Radon.  Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten.  Math. Ann., 83(1-2):113–115, 1921.
  * [50] M. Sankar.  Homotopy and the homomorphism threshold of odd cycles.  arXiv preprint, arXiv: 2206.07525, 2022.
  * [51] M. Simonovits.  A method for solving extremal problems in graph theory, stability problems.  Theory of Graphs, Proc. Colloq. Tihany, Hungary 1966, 279-319 (1968)., 1968.
  * [52] E. Szemerédi.  Regular partitions of graphs.  Problèmes combinatoires et théorie des graphes, Orsay 1976, Colloq. int. CNRS No. 260, 399-401 (1978)., 1978.
  * [53] C. Thomassen.  On the chromatic number of triangle-free graphs of large minimum degree.  Combinatorica, 22(4):591–596, 2002.
  * [54] C. Thomassen.  On the chromatic number of pentagon-free graphs of large minimum degree.  Combinatorica, 27(2):241–243, 2007.
  * [55] P. Turán.  Eine extremalaufgabe aus der graphentheorie.  Fiz Lapok, pages 436–452, 1941.
  * [56] M. L. J. van de Vel.  Theory of convex structures, volume 50 of North-Holland Mathematical Library.  North-Holland Publishing Co., Amsterdam, 1993.