# Andrásfai and Vega graphs in Ramsey-Turán theory

Tomasz Łuczak  A. Mickiewicz University, Department of Discrete Mathematics,
Poznań, Poland<EMAIL_ADDRESS><EMAIL_ADDRESS>,  Joanna Polcyn  and
Christian Reiher  Fachbereich Mathematik, Universität Hamburg, Hamburg,
Germany<EMAIL_ADDRESS>
###### Abstract.

Given positive integers $n\geq s$, we let $\mathrm{ex}(n,s)$ denote the
maximum number of edges in a triangle-free graph $G$ on $n$ vertices with
$\alpha(G)\leq s$. In the early sixties Andrásfai conjectured that for
$n/3<s<n/2$ the function $\mathrm{ex}(n,s)$ is piecewise quadratic with
critical values at $s/n={k}/({3k-1})$ for $k\in{\mathds{N}}$. We confirm that
this is indeed the case whenever $s/n$ is slightly larger than a critical
value, thus determining $\mathrm{ex}(n,s)$ for all $n$ and $s$ such that
$s/n\in[{k}/({3k-1}),{k}/({3k-1})+\gamma_{k}]$, where
$\gamma_{k}=\Theta(k^{-6})$.

###### Key words and phrases:

Ramsey-Turán theory, extremal graph theory, triangle-free graphs.

###### 2010 Mathematics Subject Classification:

Primary: 05C35.

The first author is partially supported by National Science Centre, Poland,
grant 2017/27/B/ST1/00873.

##  1\. Introduction

The structure of dense triangle-free graphs has been the subject of extensive
studies for a long time. The first result in this direction is Mantel’s
celebrated theorem [M] from 1907, which states that balanced bipartite graphs
are the densest triangle-free graphs. It is natural to ask for the densest
triangle-free graphs when we impose some additional restrictions on them; for
instance, we may bound their chromatic or independence number.

Let us first discuss the case when we require the chromatic number of a dense
triangle-free graph to be large. It is easy to see that in this case the
appropriate measure of the density of a graph is not the number of its edges
(as one can always add a small graph of large chromatic number to a complete
bipartite graph), but rather its minimum degree. This avenue of research was
started by Andrásfai, Erdős, and Sós [AES] who showed that among triangle-free
graphs with chromatic number three those with the largest minimum degree are
‘balanced blow-ups’ of the pentagon. Erdős and Simonovits [ES] noticed that a
construction due to Hajnal shows that for every $k\geq 2$, $\varepsilon>0$,
and sufficiently large $n$, there exists a triangle-free graph on $n$ vertices
whose minimum degree is larger than $(1/3-\varepsilon)n$, and whose chromatic
number is $k$. On the other hand, they conjectured that every triangle-free
graph on $n$ vertices whose minimum degree is larger than $n/3$ is
$3$-colourable. This was refuted by Häggkvist [H], who found a $10$-regular
triangle-free graph on $29$ vertices whose chromatic number is four. Jin [Jin]
showed that this example is insofar optimal that every triangle-free graph
whose minimum degree is strictly larger than $10n/29$ has chromatic number
three. Moreover, Thomassen [Th] proved that for every $\varepsilon>0$ there
exists a constant $c_{\varepsilon}$ such that every triangle-free $n$-vertex
graph with minimum degree at least $(1/3+\varepsilon)n$ has chromatic number
at most $c_{\varepsilon}$, and Łuczak [Lu06] supplemented this result by
proving, roughly speaking, that for some constant $C_{\varepsilon}$ there are
at most $C_{\varepsilon}$ ‘types’ of such graphs. Finally, Brandt and Thomassé
[BT] characterised all triangle-free graphs on $n$ vertices whose minimum
degree is larger than $n/3$; their theorem, stated in Section 5 below, plays a
decisive rôle in the proof of our main result.

In this article, however, we mainly study triangle-free graphs $G$ with
bounded independence number $\alpha(G)$. More specifically, we are interested
in the behaviour of the function $\mathrm{ex}(n,s)$, which for $n\geq s\geq 1$
gives the largest number of edges in a triangle-free graph on $n$ vertices
whose independent sets have at most the size $s$, i.e.,

$\mathrm{ex}(n,s)=\max\\{e(G)\colon v(G)=n,\ G\not\supseteq K_{3},\ \text{ and
}\alpha(G)\leq s\\}\,.$

Notice that Mantel’s theorem yields

$\mathrm{ex}(n,s)=\lfloor n^{2}/4\rfloor\quad\text{ for every }s>\lfloor
n/2\rfloor\,.$

Next we observe that in a triangle-free graph the neighbourhood of every
vertex forms an independent set, which implies the so-called trivial bound

$\mathrm{ex}(n,s)\leq ns/2$

for all $n$ and $s$. Brandt [B10] provided several explicit constructions
showing that this upper bound is asymptotically optimal for $s\leq n/3$, i.e.,
that we have

$\mathrm{ex}(n,s)=ns/2+o(n^{2})$

in this range. Thus, it remains to study the behaviour of $\mathrm{ex}(n,s)$
for $s/n\in(1/3,1/2)$.

This line of research was started over 50 years ago by Andrásfai [A], who
proved

$\mathrm{ex}(n,s)=n^{2}-4ns+5s^{2}\quad\text{ for }s/n\in[2/5,1/2]\,.$

He also speculated that $\mathrm{ex}(n,s)$ might be a piecewise quadratic
function with cusps at points of the form $s=kn/(3k-1)$. We slightly revised
his conjecture in [LPR] and resolved the next case by showing

$\mathrm{ex}(n,s)=3n^{2}-15ns+20s^{2}\quad\text{ for }s/n\in[3/8,2/5]\,.$

The new version of the conjecture reads as follows.

######  Conjecture 1.1.

If $n/3<s\leq n/2$, then

$\mathrm{ex}(n,s)=\min_{k}g_{k}(n,s)\,,$ (1.1)

where

$g_{k}(n,s)=k(k-1)n^{2}/2-k(3k-4)ns+(3k-4)(3k-1)s^{2}/2$ (1.2)

for every $k\geq 1$.

Let us remark that we also have a conjecture on the extremal graphs for which
equality holds in (1.1). Since the definition of these graphs requires some
preparation, we state this stronger conjecture only at the end the article.

As for the function $g(n,s)=\min_{k}g_{k}(n,s)$, which stands on the right
side of (1.1), an elementary calculation (see [LPR]*Cor. 2.7) shows that for
$k\geq 2$ and $\frac{k}{3k-1}n\leq s<\frac{k-1}{3k-4}n$ we have
$g(n,s)=g_{k}(n,s)$. Thus, for fixed $n$ the function $g(n,s)$ is piecewise
quadratic in $s\in(n/3,n/2)$ with cusps at the points $s=kn/(3k-1)$ for $k\geq
2$.

The main goal of this work is to add further plausibility to Conjecture 1.1 by
proving it whenever $s/n$ is slightly larger than one of the ‘critical points’
$k/(3k-1)$.

######  Theorem 1.2.

For every $k\geq 2$ there exists $\gamma=\gamma(k)>0$ such that

$\mathrm{ex}(n,s)=g_{k}(n,s)=\min_{\ell}g_{\ell}(n,s)$

whenever

$\frac{k}{3k-1}n\leq s\leq\left(\frac{k}{3k-1}+\gamma\right)n\,.$

For instance, this holds for $\gamma(k)=(600k^{6})^{-1}$.

Along the way, we establish the following minimum degree version of Conjecture
1.1.

######  Theorem 1.3.

Let $k\geq 2$ and $n\geq s\geq 1$. If $H$ denotes a triangle-free graph on $n$
vertices with $\alpha(H)\leq s$ and

$\delta(H)>\frac{k+1}{3k+2}n\,,$

then $e(H)\leq g_{k}(n,s)$.

Let us mention that similar problems could be and, in many cases, have been,
considered for $K_{r}$-free graphs and, more generally, for $H$-free graphs
for any given graph $H$. It hardly seems necessary to recall that Turán’s
problem to determine the maximum number of edges in an $H$-free graph on $n$
vertices is fairly well understood thanks to the work of Turán himself [T],
Erdős, Stone, and Simonovits [ES46, ESim]. The studies of the chromatic
threshold (equal to 1/3 for triangle-free graphs by the aforementioned result
of Thomassen [Th]) were begun by Łuczak and Thomassé [LT] and culminated in
the work of Allen et al. [Aet] who determined this parameter for $H$-free
graphs when an arbitrary graph $H$ is given (for the precise definition of the
‘chromatic threshold’ we refer to either of those two articles).

The question on the behaviour of $\mathrm{ex}(n,s)$ considered in this work
belongs to an area called Ramsey-Turán theory, which has been initiated by
Vera T. Sós and extensively investigated during the last fifty years. There is
a comprehensive survey on this subject by Sós and Simonovits [SS01]. Important
milestones in the Ramsey-Turán theory of general $K_{r}$-free graphs were
obtained by Bollobás, Erdős, Hajnal, Sós, Szemerédi [BE76, EHSS, ES69, Sz72],
and, more recently, by Lüders and Reiher [LR-a]. Due to their work, we
asymptotically know the value of

$\mathrm{ex}_{r}(n,s)=\max\\{e(G)\colon v(G)=n,\ G\not\supseteq K_{r},\ \text{
and }\alpha(G)\leq s\\}$

for all $r\geq 3$ provided that $s/n\ll r^{-1}$ is sufficiently small. It
would, of course, be interesting to study this function for larger values of
$s/n$ as well, but, as the present article demonstrates, even the case $r=3$
of triangles seems to be fairly difficult.

We believe that with considerably more work the methods of this article would
allow to prove Theorem 1.3 under the weaker assumption $\delta(H)>n/3$ as
well, which would lead to some numerical improvement on the value of
$\gamma(k)$ in Theorem 1.2.

The structure of the article is the following. In Section 2 we start with the
definition and some basic properties of the blow-up operation. The two
subsequent sections define and study Andrásfai and Vega graphs, which – by a
result of Brandt and Thomassé – are the main protagonists in the story of
dense triangle-free graphs (see Theorem 5.1 below). In particular, in this
part of the article we prove some special cases of Theorem 1.2 addressing
blow-ups of these two types of graphs (see Lemma 3.3 and Lemma 4.1). In
Section 5 these results will be employed in the proofs of the Theorems 1.2 and
1.3. Moreover, we shall state there a precise version of our conjecture on
extremal cases in Conjecture 1.1. These are the same as the extremal graphs
for the two aforementioned lemmata, which we characterise in Lemma 3.5 and
Lemma 4.4, respectively.

##  2\. Blow-ups of graphs

Given a graph $F$ with vertex set $V(F)=\\{v_{1},\ldots,v_{r}\\}$, a blow-up
of $F$ is a graph $H$ obtained from $F$ upon replacing its vertices by
independent sets $V_{1},V_{2},\ldots,V_{r}$, and each of its edges
$v_{i}v_{j}\in E(F)$, $1\leq i<j\leq r$, by the complete bipartite graph
$K(V_{i},V_{j})$ between $V_{i}$ and $V_{j}$. The sets $V_{1},\ldots,V_{r}$
are called the vertex classes of $H$. As above, we shall always denote the
vertices of the original graph $F$ by lower case letters and the vertex
classes of $H$ by capitalised versions of the same letters. A blow-up is
proper if all vertex classes are non-empty and balanced if all of them are of
the same size. As the isomorphism type of $H$ depends only on the sizes of its
vertex classes it will be convenient to write $H=F(h)$, where the function
$h\colon V(F)\longrightarrow{\mathds{Z}}_{\geq 0}$ is defined by
$h(v_{i})=|V_{i}|$ for every $v_{i}\in V(F)$. In the special case where $h$ is
the constant function attaining always the value $p$ it will be convenient to
write $H=F(p)$. For later use we remark that a blow-up of a blow-up of $F$ is
again a blow-up of $F$.

Resuming the discussion of the blow-up $H$ of $F$ with vertex classes
$V_{1},\ldots,V_{r}$ we set

$N(V_{i})=\bigcup_{v_{j}\in N(v_{i})}V_{j}$

for each of these vertex classes, where $N(v_{i})$ denotes the neighbourhood
of $v_{i}$ in $F$. Clearly, all vertices in $V_{i}$ have the neighbourhood
$N(V_{i})$ in $H$ and, consequently, every non-empty vertex class $V_{i}$
satisfies

$\delta(H)\leq|N(V_{i})|\leq\Delta(H)\,.$ (2.1)

Now simple averaging leads to the following observation.

######  Fact 2.1.

Let $H$ be an $n$-vertex blow-up of a $k$-regular graph $F$ on the $r$-element
vertex set $V(F)=\\{v_{1},\ldots,v_{r}\\}$.

  1. ( )

We have

$\sum_{i=1}^{r}|N(V_{i})|=kn\,.$ (2.2)

  2. ( )

If the blow-up $H$ is proper, then

$\delta(H)\leq\frac{kn}{r}\leq\Delta(H)\,.$

###### Proof.

The double counting argument

$\sum_{i=1}^{r}|N(V_{i})|=\sum_{i=1}^{r}\sum_{v_{j}\in
N(v_{i})}|V_{j}|=\sum_{j=1}^{r}|N(v_{j})|\,|V_{j}|=k\sum_{j=1}^{r}|V_{j}|=kn$

establishes part ( ) ‣ 2.1. If $H$ is a proper blow-up, then (2.1) yields

$r\delta(H)\leq\sum_{i=1}^{r}|N(V_{i})|\leq r\Delta(H)$

and part ( ) ‣ 2.1 follows. ∎

The second part of the foregoing fact has the following useful consequence.

######  Lemma 2.2.

Let $d,k\geq 2$ be two integers and let $J$ be a graph. Suppose that $J$ has a
$k$-regular proper blow-up $F$ on $3k-1$ vertices and that $H$ denotes a
further proper blow-up of $J$ having $n$ vertices. If

$\frac{d+1}{3d+2}n<\delta(H)\quad\text{ and
}\quad\Delta(H)<\frac{d-1}{3d-4}n\,,$ (2.3)

then $k=d$.

###### Proof.

Notice that every balanced blow-up $H(p)$ of $H$ is a proper blow-up of $J$ as
well. By applying this observation to a sufficiently large integer $p$ we
learn that we may assume, without loss of generality, that $H$ is a proper
blow-up of $F$. Now Fact 2.1( ) ‣ 2.1 reveals

$\delta(H)\leq\frac{kn}{3k-1}\leq\Delta(H)\,,$

which together with (2.3) implies

$\frac{d+1}{3d+2}<\frac{k}{3k-1}<\frac{d-1}{3d-4}\,.$

Taking reciprocals we obtain

$3-\frac{1}{d-1}<3-\frac{1}{k}<3-\frac{1}{d+1}\,,$

i.e., $d-1<k<d+1$. ∎

The main result of this section is the following upper bound on the number of
edges of a blow-up.

######  Lemma 2.3.

Suppose that $F$ is a $k$-regular graph on $r$ vertices and that $H$ is an
$n$-vertex blow-up of $F$ all of whose vertex classes have at least the size
$x$. If we have $|N(Z)|\leq s$ for every vertex class $Z$ of $H$, then

$e(H)\leq\frac{ns}{2}-\frac{x(rs-kn)}{2}\,.$ (2.4)

Moreover, if $rs\neq kn$ and (2.4) holds with equality, then

  1. $\bullet$

at least one vertex class of $H$ has size $x$;

  2. $\bullet$

every vertex class $V_{i}$ of $H$ with $|V_{i}|>x$ satisfies $|N(V_{i})|=s$.

###### Proof.

As usual, we write the vertex set of $F$ in the form
$V(F)=\\{v_{1},\ldots,v_{r}\\}$. Setting $x_{i}=|V_{i}|$ for $i\in[r]$ we have

$\displaystyle 2e(H)$ $\displaystyle=\sum_{v\in
V(H)}\deg_{H}(v)=\sum_{i=1}^{r}|V_{i}|\cdot|N(V_{i})|$
$\displaystyle=\sum_{i=1}^{r}x\cdot|N(V_{i})|+\sum_{i=1}^{r}(x_{i}-x)\cdot|N(V_{i})|$
$\displaystyle\leq
x\sum_{i=1}^{r}|N(V_{i})|+\sum_{i=1}^{r}(x_{i}-x)s\overset{\eqref{eq:1734}}{=}xkn+s(n-xr)=ns-x(rs-
kn)\,,$

which proves the desired upper bound on $e(H)$.

Suppose from now on that this estimate holds with equality and that $rs\neq
kn$. This means that $(x_{i}-x)|N(V_{i})|=(x_{i}-x)s$ holds for every
$i\in[r]$, or in other words that $x_{i}>x$ implies $|N(V_{i})|=s$. This
proves the second bullet. Now, if the first bullet fails, we have
$|N(V_{i})|=s$ for every $i\in[r]$ and (2.2) yields the contradiction $rs=kn$.
∎

Let us notice the following consequence of the above result.

######  Corollary 2.4.

Suppose that $k\geq 2$ is a natural number, $F$ is a $k$-regular graph on
$3k-1$ vertices and $H$ is an $n$-vertex blow-up of $F$. If $|N(Z)|\leq s$ and
$|Z|\geq(k-1)n-(3k-4)s$ hold for every vertex class $Z$ of $H$, then

$e(H)\leq g_{k}(n,s)\,.$

Moreover, if $e(H)=g_{k}(n,s)$, then

  1. ( )

$kn/(3k-1)\leq s\leq(k-1)n/(3k-4)$;

  2. ( )

$H$ contains a vertex class of size $(k-1)n-(3k-4)s$;

  3. ( )

the neighbourhood of each vertex class of $H$ containing more than
$(k-1)n-(3k-4)s$ vertices has size $s$.

###### Proof.

In order to prove the desired upper bound on $e(H)$ we remark that Lemma 2.3
applied to $r=3k-1$ and $x=(k-1)n-(3k-4)s$ yields

$e(H)\leq\tfrac{1}{2}\bigl{[}ns-\bigl{(}(k-1)n-(3k-4)s\bigr{)}\bigl{(}(3k-1)s-kn\bigr{)}\bigr{]}=g_{k}(n,s)\,.$

Let us now study the case that equality holds in this estimate. If clause ( )
‣ 2.4 failed, then the trivial upper bound $e(H)\leq ns/2$ would contradict
$e(H)=g_{k}(n,s)$.

The remaining two clauses follow from the moreover-part in Lemma 2.3 provided
that its assumption $(3k-1)s\neq kn$ holds. So it remains to deal with the
case $s=kn/(3k-1)$. Now $(k-1)n-(3k-4)s=n/(3k-1)$ is at the same time the
average size of the vertex classes of $H$ and a lower bound on the sizes of
these vertex classes. In other words, $H$ is the balanced blow-up
$F\bigl{(}n/(3k-1)\bigr{)}$ and ( ) ‣ 2.4, ( ) ‣ 2.4 hold trivially. ∎

##  3\. Andrásfai graphs and their blow-ups

The characterisation of triangle-free graphs on $n$ vertices whose minimum
degree is larger than $n/3$ due to Brandt and Thomassé [BT] involves two
explicit families of such graphs, called Andrásfai graphs and Vega graphs (see
Theorem 5.1 below). In this section we study the first of these graph
sequences, which has been introduced by Andrásfai in [A] and has been
rediscovered several times throughout the years.

One way to construct a $k$-regular triangle-free graph is to take an Abelian
group ${\mathds{G}}$, a symmetric sum-free subset $S$ of size $k$, and to form
the Cayley graph $\textrm{Cayley}({\mathds{G}};S)$. A natural (and, as we
shall soon argue, generic) example occurs when we take the cyclic group
${\mathds{Z}}_{3k-1}$ and its sum-free subset $S_{k}=\\{k,k+1,\ldots,2k-1\\}$.
The _Andrásfai graph $\Gamma_{k}$_ is defined to be the corresponding Cayley
graph $\textrm{Cayley}({\mathds{Z}}_{3k-1};S_{k})$. Describing the same graph
in more concrete terms, we set

$V(\Gamma_{k})=\\{v_{0},v_{1},\dots,v_{3k-2}\\}$

and declare the adjacencies in $\Gamma_{k}$ by

$v_{i}v_{j}\in E(\Gamma_{k})\,\,\,\Longleftrightarrow\,\,\,k\leq|i-j|\leq
2k-1$ (3.1)

for all vertices $v_{i},v_{j}\in V(\Gamma_{k})$. For instance,
$\Gamma_{1}=K_{2}$, $\Gamma_{2}=C_{5}$, and Figure 3.1 shows some further
Andrásfai graphs.

Figure 3.1. Andrásfai graphs $\Gamma_{3}$, $\Gamma_{4}$, $\Gamma_{5}$, and
$\Gamma_{6}$.

Let us remark that given an Abelian group ${\mathds{G}}$ containing a sum-free
set $S$ with $|S|>|{\mathds{G}}|/3$ one can show by means of Kneser’s theorem
(see [LS]) that for some positive integer $k$ there exists a homomorphism
$\varphi\colon{\mathds{G}}\longrightarrow{\mathds{Z}}_{3k-1}$ satisfying
$\varphi[S]\subseteq S_{k}$. Such a group homomorphism $\varphi$ induces a
graph homomorphism
$\varphi_{\star}\colon\textrm{Cayley}({\mathds{G}};S)\longrightarrow\Gamma_{k}$,
or, in other words, it indicates that $\textrm{Cayley}({\mathds{G}};S)$ is
contained in a sufficiently large blow-up of $\Gamma_{k}$. These
considerations reveal that balanced blow-ups of Andrásfai graphs are universal
in the class of triangle-free Cayley graphs whose density is larger than
$1/3$. Somewhat relatedly, a finite graph is a subgraph of a blow-up of an
Andrásfai graph if and only if it is isomorphic to a subgraph of the infinite
triangle-free Cayley graph
$\textrm{Cayley}\bigl{(}{\mathds{R}}/{\mathds{Z}};(1/3,2/3)+{\mathds{Z}}\bigr{)}$,
see [BMPP2018]*Lemma 2.1. We proceed with three well known, useful properties
of Andrásfai graphs.

######  Fact 3.1.

Let $k\geq 2$ be an integer.

  1. ( )

We have $\Gamma_{k-1}\subseteq\Gamma_{k}$. Conversely, if we remove a vertex
from $\Gamma_{k}$, then the resulting graph is a subgraph of a proper blow-up
of $\Gamma_{k-1}$. Consequently, every subgraph of $\Gamma_{k}$ is a subgraph
of a proper blow-up of $\Gamma_{\ell}$ for some $\ell\leq k$.

  2. ( )

The chromatic number of $\Gamma_{k}$ is $3$.

  3. ( )

Every independent set in $\Gamma_{k}$ is contained in the neighbourhood of
some vertex of $\Gamma_{k}$. In particular, $\alpha(\Gamma_{k})=k$.

###### Proof.

The first part of ( ) ‣ 3.1 follows from
$\Gamma_{k-1}\cong\Gamma_{k}-\\{v_{0},v_{k},v_{2k}\\}$. Furthermore, the graph
$\Gamma_{k}^{-}=\Gamma_{k}-\\{v_{k}\\}$ satisfies
$N(v_{0},\Gamma_{k}^{-})\subseteq N(v_{1},\Gamma_{k}^{-})$ and
$N(v_{2k},\Gamma_{k}^{-})\subseteq N(v_{2k-1},\Gamma_{k}^{-})$, which proves
$\Gamma_{k}^{-}$ to be a subgraph of the blow-up of
$\Gamma_{k}-\\{v_{0},v_{k},v_{2k}\\}$ obtained by doubling the vertices
$v_{1}$ and $v_{2k-1}$. This establishes the second part of ( ) ‣ 3.1 and the
last part follows inductively.

Proceeding with ( ) ‣ 3.1 we observe that, due to ( ) ‣ 3.1, $\Gamma_{k}$
contains a pentagon $\Gamma_{2}$ as a subgraph, whence
$\chi(\Gamma_{k})\geq\chi(\Gamma_{2})=3$. To verify the reverse inequality, we
partition $V(\Gamma_{k})$ into the three independent sets
$\\{v_{0},v_{1},\ldots,v_{k-1}\\}$, $\\{v_{k},v_{k+1},\ldots,v_{2k-1}\\}$, and
$\\{v_{2k},v_{2k+1},\ldots,v_{3k-2}\\}$.

Finally, let $S\subseteq V(\Gamma_{k})$ be a nonempty independent set we want
to cover by the neighbourhood of an appropriate vertex. By symmetry we may
suppose that $v_{k}\in S$, which due to (3.1) entails
$S\subseteq\\{v_{1},v_{2},\ldots,v_{2k-1}\\}$. Let $i,j\in[2k-1]$ be the
smallest and largest index with $v_{i},v_{j}\in S$. Now
$S\subseteq\\{v_{i},\ldots,v_{j}\\}$, a further application of (3.1) shows
$j-i\leq k-1$, and altogether we have $S\subseteq N(v_{j+k})$. ∎

Let us consider for $k\geq 2$ and $n\geq s\geq 1$ an $n$-vertex blow-up $H$ of
the Andrásfai graph $\Gamma_{k}$ with $\alpha(H)\leq s$. According to the
notation of Section 2, this blow-up comes together with a fixed partition

$V(H)=V_{0}\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}V_{1}\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}\ldots\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}V_{3k-2}$

of its vertex set. Clearly, since $\Gamma_{k}$ is triangle-free, so is $H$.
Therefore the neighbourhood of each vertex class of $H$ is an independent set,
which proves

$|N(V_{i})|=|V_{i+k}|+\ldots+|V_{i+2k-1}|\leq s$ (3.2)

for every $i\in{\mathds{Z}}_{3k-1}$. We use this inequality to bound the sizes
of the vertex classes of $H$.

######  Fact 3.2.

For every $i\in{\mathds{Z}}_{3k-1}$ we have

$(k-1)n-(3k-4)s\leq|V_{i}|\leq 3s-n\,.$

###### Proof.

The upper bound holds because of

$\displaystyle|V_{i}|$ $\displaystyle=|V_{0}\cup V_{1}\cup\dots\cup
V_{3k-2}|+|V_{i}|-n$
$\displaystyle=|N(V_{i})|+|N(V_{i+k})|+|N(V_{i-k})|-n\overset{\eqref{eq:inde}}{\leq}3s-n\,.$

By applying this estimate to $V_{i+k+1},\ldots,V_{i+2k-2}$ instead of $V_{i}$
we infer

$\displaystyle|V_{i}|$
$\displaystyle=n-\bigl{(}|N(V_{i+(k-1)})|+|N(V_{i-(k-1)})|+|V_{i+k+1}|+\dots+|V_{i+2k-2}|\bigr{)}$
$\displaystyle\overset{\eqref{eq:inde}}{\geq}n-\bigl{(}2s+(k-2)(3s-n)\bigr{)}=(k-1)n-(3k-4)s\,.\qed$

By combining Corollary 2.4 and Fact 3.2 we arrive at the main result of this
section.

######  Lemma 3.3.

Let $k$ be a natural number. If for $n\geq s\geq 1$ the graph $H$ is an
$n$-vertex blow-up of the Andrásfai graph $\Gamma_{k}$ satisfying
$\alpha(H)\leq s$, then

$e(H)\leq g_{k}(n,s)\,.\qed$

As remarked in [LPR]*Fact 1.5, this estimate can hold with equality. We would
now like to complement this observation by an explicit description of all
extremal cases. As it turns out, every $n$-vertex blow-up $H$ of $\Gamma_{k}$
with $\alpha(H)\leq s$ and $e(H)=g_{k}(n,s)$ belongs to the following family
of graphs.

######  Definition 3.4.

Given natural numbers $k\geq 2$, $n$, and $s\in[kn/(3k-1),(k-1)n/(3k-4)]$ the
family $\mathscr{G}^{n}_{k}(s)$ consists of all graphs obtained from
$\Gamma_{k}$ by blowing up its vertices

  1. $\bullet$

$v_{0}$ and $v_{k}$ by $(k-1)n-(3k-4)s$,

  2. $\bullet$

$v_{2k-1}$ by $a$, $v_{2k}$ by $b$, where $a,b\in[(k-1)n-(3k-4)s,3s-n]$ are
two integers summing up to $(k-2)n-(3k-7)s$,

  3. $\bullet$

and all remaining vertices by $3s-n$.

Observe that if $s=kn/(3k-1)$, then $(k-1)n-(3k-4)s=3s-n$ and the only graph
in $\mathscr{G}^{n}_{k}(s)$ is the balanced blow-up $\Gamma_{k}(3s-n)$. At the
other end of the spectrum we have the case $s=(k-1)n/(3k-4)$, where
$(k-1)n-(3k-4)s=0$ and the graphs in $\mathscr{G}^{n}_{k}(s)$ are actually
blow-ups of $\Gamma_{k}\smallsetminus\\{v_{0},v_{k}\\}$. In this graph,
$v_{2k}$ is a twin sister of $v_{2k-1}$ and again the class
$\mathscr{G}^{n}_{k}(s)$ consists of a single graph. In view of
$\Gamma_{k-1}\cong\Gamma_{k}-\\{v_{0},v_{k},v_{2k}\\}$ this graph is the
balanced blow-up $\Gamma_{k-1}(3s-n)$. However, if $s$ lies strictly between
$kn/(3k-1)$ and $(k-1)n/(3k-4)$, then $\mathscr{G}^{n}_{k}(s)$ consists of
$\big{\lfloor}\bigl{(}(3k-1)s-kn\bigr{)}/2\big{\rfloor}+1$ mutually non-
isomorphic graphs.

######  Lemma 3.5.

If $H$ denotes an $n$-vertex blow-up of $\Gamma_{k}$ satisfying

$\alpha(H)\leq s\quad\text{ and }\quad e(H)=g_{k}(n,s)$

for some $k\geq 2$, then $kn/(3k-1)\leq s\leq(k-1)n/(3k-4)$ and $H$ is
isomorphic to some graph in $\mathscr{G}^{n}_{k}(s)$.

###### Proof.

As usual we denote the vertex classes of $H$ corresponding to the vertices of
$\Gamma_{k}$ by $V_{0},\ldots,V_{3k-2}$. Recall that by Fact 3.2 we have

$(k-1)n-(3k-4)s\leq|V_{i}|\leq 3s-n\quad\text{ for every
}i\in{\mathds{Z}}_{3k-1}\,.$ (3.3)

In particular, $H$ has the properties enumerated in the moreover-part of
Corollary 2.4 and clause ( ) ‣ 2.4 corresponds to the estimates on $s$ stated
in the lemma. Next, ( ) ‣ 2.4 allows us to assume, without loss of generality,
that

$|V_{0}|=(k-1)n-(3k-4)s\,.$ (3.4)

In the special case

$|V_{k}|=|V_{2k-1}|=(k-1)n-(3k-4)s$

we have

$n=|V_{0}|+\ldots+|V_{3k-2}|\overset{\eqref{eq:1847}}{\leq}3\bigl{(}(k-1)n-(3k-4)s\bigr{)}+(3k-4)(3s-n)=n\,,$

which yields $|V_{i}|=3s-n$ for every $i\neq 0,k,2k-1$, meaning that
$a=(k-1)n-(3k-4)s$ exemplifies $H\in\mathscr{G}^{n}_{k}(s)$. By symmetry we
may therefore suppose $|V_{2k-1}|>(k-1)n-(3k-4)s$ from now on, which in view
of Corollary 2.4( ) ‣ 2.4 entails

$s=|N(V_{2k-1})|=|V_{0}|+\ldots+|V_{k-1}|\overset{\eqref{eq:1847}}{\leq}\bigl{(}(k-1)n-(3k-4)s\bigr{)}+(k-1)(3s-n)=s\,,$

i.e.,

$|V_{1}|=\ldots=|V_{k-1}|=3s-n\,.$ (3.5)

Because of $|V_{1}|+\ldots+|V_{k}|=|N(V_{2k})|\leq s$ and (3.3) this yields

$|V_{k}|=(k-1)n-(3k-4)s\,,$ (3.6)

which together with (3.4) establishes the first bullet in Definition 3.4.

Next we observe that, since by (3.4) the lower bound on $|V_{0}|$ provided by
Fact 3.2 holds with equality, an easy inspection of the proof of Fact 3.2
discloses

$|V_{k+1}|=\ldots=|V_{2k-2}|=3s-n$

and for the same reason (3.6) leads to $|V_{2k+1}|=\ldots=|V_{3k-2}|=3s-n$.
Combined with (3.5) these equations confirm the third bullet in Definition 3.4
and, finally, the second bullet follows easily in the light of $v(H)=n$ and
(3.3). ∎

##  4\. Vega graphs and their blow-ups

In this section we investigate another important class of dense triangle-free
graphs which, unlike Andrásfai graphs, have chromatic number four. Let us
recall that the first $4$-chromatic triangle-free graph on $n$ vertices whose
minimum degree is larger than $n/3$ was a blow-up of the Grötzsch graph
discovered in 1981 by Häggkvist [H]. In 1998, Brandt and Pisanski [BP] worked
with a computer program named Vega and found an infinite sequence of
$4$-chromatic triangle-free graphs admitting such blow-ups (see Fact 4.2). Due
to their origin, these graphs are called _Vega graphs_.

$a$$b$$c$$v$$w$$u$$x$$y$$v_{0}$$v_{i-1}$$v_{i}$$v_{2i-1}$$v_{2i}$$v_{3i-2}$
Figure 4.1. The Vega graph $\Upsilon^{00}_{i}$. The vertices of the external
6-cycle $\mathcal{C}_{6}$ are connected with the vertices of the same colour
of the Andrásfai graph $\Gamma_{i}$ in the middle.

###  4.1. Definitions and main results.

We commence by presenting a construction of Vega graphs following the work of
Brandt and Thomassé [BT]. Let an integer $i\geq 2$ be given. Start with an
Andrásfai graph $\Gamma_{i}$ on the vertex set $\\{v_{0},\ldots,v_{3i-2}\\}$
and add an edge $xy$ together with an induced $6$-cycle $avcubw$ such that $x$
is joined to $a,b,c$ and $y$ is joined to $u,v,w$. Moreover, connect

  1. $\bullet$

$a$, $u$ to $\\{v_{0},\ldots,v_{i-1}\\}$,

  2. $\bullet$

$b$, $v$ to $\\{v_{i},\ldots,v_{2i-1}\\}$,

  3. $\bullet$

and $c$, $w$ to $\\{v_{2i},\ldots,v_{3i-2}\\}$.

This completes the definition of the sole Vega graph on $3i+7$ vertices, which
we denote by $\Upsilon_{i}^{00}$ and sometimes just by $\Upsilon_{i}$ (see
Figure 4.1).

There are two Vega graphs on $3i+6$ vertices obtainable from
$\Upsilon_{i}^{00}$ by simple vertex deletions, namely
$\Upsilon_{i}^{10}=\Upsilon_{i}^{00}-\\{y\\}$ and
$\Upsilon_{i}^{01}=\Upsilon_{i}^{00}-\\{v_{2i-1}\\}$. Finally, the last Vega
graph, $\Upsilon_{i}^{11}=\Upsilon_{i}^{00}-\\{y,v_{2i-1}\\}$, has $3i+5$
vertices. Observe that the vertex $y$ is present in $\Upsilon_{i}^{\mu\nu}$ if
and only if $\mu=0$. Similarly, $\nu=1$ in $\Upsilon_{i}^{\mu\nu}$ indicates
the absence of the vertex $v_{2i-1}$. For instance, $\Upsilon_{2}^{11}$ is the
well known Grötzsch graph. For later use we would like to remark that
$\Upsilon_{2}^{11}\subseteq\Upsilon_{i}^{\mu\nu}$ gives a quick proof of the
aforementioned estimate $\chi(\Upsilon_{i}^{\mu\nu})\geq 4$. The main result
of this section reads as follows.

######  Lemma 4.1.

Let integers $i\geq 2$ and $\mu,\nu\in\\{0,1\\}$ be given and set
$k=9i-(6+\mu+\nu)$. If for $n\geq s\geq 1$ the graph $H$ is an $n$-vertex
blow-up of the Vega graph ${\Upsilon}_{i}^{\mu\nu}$ satisfying $\alpha(H)\leq
s$, then

$e(H)\leq g_{k}(n,s)\,.$

The proof of the above lemma is based on Corollary 2.4, which will become
applicable once we have exhibited a $k$-regular blow-up of
${\Upsilon}_{i}^{\mu\nu}$ on $3k-1$ vertices. To this end we shall use an
appropriate weight function

$\omega_{\mu\nu}\colon V(\Upsilon_{i})\longrightarrow{\mathds{Z}}_{\geq 0}$

from [BT]. In the special case $\mu=\nu=0$ this function is defined by the
following table.

vertex $z$ |  $x$, $y$ |  $a$, $b$, $u$, $v$ |  $c$, $w$ |  $v_{0}$, $v_{2i-1}$ |  $v_{j}$ (where $j\neq 0,2i-1$)
---|---|---|---|---|---
weight $\omega_{00}(z)$ | $1$ | $3i-2$ | $3i-3$ | $1$ | $3$

In general, one uses the function

$\omega_{\mu\nu}=\omega_{00}-\mu f-\nu g\,,$ (4.1)

where $f,g\colon V(\Upsilon_{i})\longrightarrow{\mathds{Z}}$ are defined by

$f(z)=\begin{cases}1&\text{if }z=u,v,w,y\cr-1&\text{if }z=x\cr
0&\text{otherwise }\end{cases}$

and

$g(z)=\begin{cases}1&\text{if }z=b,v,v_{i-1},v_{2i-1}\cr-1&\text{if
}z=v_{0}\cr 0&\text{otherwise. }\end{cases}$

The weight function $\omega_{\mu\nu}$ is visualised in Figure 4.2.

$a$$b$$c$$v$$w$$u$$x$$y$$v_{0}$$v_{i-1}$$v_{i}$$v_{2i-1}$$v_{2i}$$v_{3i-2}$$3i-2$$3i-2-\nu$$3i-3$$3i-2-\mu-\nu$$3i-3-\mu$$3i-2-\mu$$1+\mu$$1-\mu$$1+\nu$$3-\nu$$3$$3$$1-\nu$$3$$3$$3$$a$$b$$c$$v$$w$$u$$x$$y$$v_{0}$$v_{i-1}$$v_{i}$$v_{2i-1}$$v_{2i}$$v_{3i-2}$
Figure 4.2. Positive integers assigned to the vertices of the original graph
$\Upsilon_{i}^{\mu\nu}$.

One checks easily that the support of $\omega_{\mu\nu}$ always contains
$V(\Upsilon_{i}^{11})$, that $y$ is in this support if and only if $\mu=0$,
and that $v_{2i-1}$ is in this support if and only if $\nu=0$. Consequently,

$\text{ the support of $\omega_{\mu\nu}$ is $V(\Upsilon_{i}^{\mu\nu})$}\,.$
(4.2)

Given a signed weight function $h\colon
V(\Upsilon_{i})\longrightarrow{\mathds{Z}}$ and a subset $A\subseteq
V(\Upsilon_{i})$ of the vertex set we define

$h(A)=\sum_{z\in A}h(z)\,.$

For instance, some quick calculations disclose the formulae

$\displaystyle\omega_{00}\bigl{(}V(\Upsilon_{i})\bigr{)}$
$\displaystyle=27i-19$ $\displaystyle\text{ and }\quad
f\bigl{(}V(\Upsilon_{i})\bigr{)}$
$\displaystyle=g\bigl{(}V(\Upsilon_{i})\bigr{)}=3\,,$

which by linearity, (4.1), and (4.2) imply

$\omega_{\mu\nu}\bigl{(}V(\Upsilon^{\mu\nu}_{i})\bigr{)}=3\bigl{(}9i-(6+\mu+\nu)\bigr{)}-1\,.$
(4.3)

Similarly, for every vertex $z$ we have

$\displaystyle\omega_{00}\bigl{(}N(z)\bigr{)}$ $\displaystyle=9i-6\,,$
$\displaystyle f\bigl{(}N(z)\bigr{)}$ $\displaystyle=\begin{cases}1&\text{ if
$z\neq y$}\cr 2&\text{ if $z=y$,}\end{cases}$ $\displaystyle\text{and}\quad
g\bigl{(}N(z)\bigr{)}$ $\displaystyle=\begin{cases}1&\text{ if $z\neq
v_{2i-1}$}\cr 2&\text{ if $z=v_{2i-1}$,}\end{cases}$

whence

$\omega_{\mu\nu}\bigl{(}N(z)\bigr{)}=9i-(6+\mu+\nu)\quad\text{for all }z\in
V(\Upsilon_{i}^{\mu\nu})\,.$ (4.4)

Let $G^{\mu\nu}_{i}={\Upsilon}_{i}^{\mu\nu}(\omega_{\mu\nu})$ be the blow-up
of $\Upsilon^{\mu\nu}_{i}$ obtained by replacing every vertex $z$ by an
independent set $Z$ of size $\omega_{\mu\nu}(z)$, and let

$k=9i-(6+\mu+\nu)$ (4.5)

be the number occurring in Lemma 4.1. We summarise (4.3) and (4.4) in the
following observation due to [BP].

######  Fact 4.2.

If $i\geq 2$ and $\mu,\nu\in\\{0,1\\}$, then $G^{\mu\nu}_{i}$ is a $k$-regular
blow-up of ${\Upsilon}_{i}^{\mu\nu}$ on $3k-1$ vertices. ∎

Finally, as in the case of Andrásfai graphs, we characterize all extremal Vega
graphs.

######  Definition 4.3.

Given natural numbers $k\geq 10$ and $n\geq s\geq 1$ the family
$\mathscr{H}^{n}_{k}(s)$ is the smallest collection of blow-ups of Vega graphs
with the following properties.

  1. ( )

If $s=kn/(3k-1)$, then $G^{\mu\nu}_{i}(3s-n)\in\mathscr{H}^{n}_{k}(s)$
whenever $k=9i-(6+\mu+\nu)$.

  2. ( )

If $kn/(3k-1)<s\leq(k-1)n/(3k-4)$, then
$\Upsilon^{0\nu}_{i}\bigl{(}(3s-n)\omega_{\mu\nu}-\lambda
f\bigr{)}\in\mathscr{H}^{n}_{k}(s)$ whenever $k=9i-(6+\nu)$.

  3. ( )

If $kn/(3k-1)<s\leq(k-1)n/(3k-4)$, then $\Upsilon^{\mu
0}_{i}\bigl{(}(3s-n)\omega_{\mu\nu}-\lambda
g\bigr{)}\in\mathscr{H}^{n}_{k}(s)$ whenever $k=9i-(6+\mu)$.

Observe that for

  * •

$s\notin[kn/(3k-1),(k-1)n/(3k-4)]$ the family $\mathscr{H}^{n}_{k}(s)$ is
empty;

  * •

$k\nequiv 1,2,3\pmod{9}$ the family $\mathscr{H}^{n}_{k}(s)$ is empty;

  * •

$k\equiv 1\pmod{9}$ we have $\mu+\nu=2$ and the family
$\mathscr{H}^{n}_{k}(s)$ is nonempty if and only if $s=nk/(3k-1)$, in which
case it only consists of the graph $G^{11}_{(k+8)/9}(3s-n)$;

  * •

$k\equiv 2,3\pmod{9}$ and $s=nk/(3k-1)$ there are one or two graphs in
$\mathscr{H}^{n}_{k}(s)$ as described in ( ) ‣ 4.3.

  * •

$k\equiv 2,3\pmod{9}$ and $kn/(3k-1)<s\leq(k-1)n/(3k-4)$ the family
$\mathscr{H}^{n}_{k}(s)$ consists of two graphs, one of which is as described
in ( ) ‣ 4.3 while the other one is as described in ( ) ‣ 4.3.

######  Lemma 4.4.

Given integers $i\geq 2$, $\mu,\nu\in\\{0,1\\}$, and $n\geq s\geq 1$, let $H$
be a blow-up of ${\Upsilon}_{i}^{\mu\nu}$ on $n$ vertices. If

$\alpha(H)\leq s\quad\text{ and }\quad e(H)=g_{k}(n,s)$

hold for $k=9i-(6+\mu+\nu)$, then $H$ is isomorphic to a graph in the family
$\mathscr{H}^{n}_{k}(s)$.

###  4.2. Proof of Lemma 4.1.

Throughout this subsection, we fix some integers $i\geq 2$,
$\mu,\nu\in\\{0,1\\}$, and $n\geq s\geq 1$. We keep using the weight function
$\omega_{\mu\nu}\colon V(\Upsilon_{i})\longrightarrow{\mathds{Z}}_{\geq 0}$
and the natural number $k$ defined in (4.1) and (4.5), respectively. Let $H$
be an $n$-vertex blow-up of $\Upsilon^{\mu\nu}_{i}$ such that $\alpha(H)\leq
s$. It will be convenient to view $H$ as a blow-up of $\Upsilon_{i}$ as well
by adding an empty vertex class $Y$ in case $\mu=1$ and an empty $V_{2i-1}$ in
case $\nu=1$. The independence of the neighbourhoods of the vertices in
$\Upsilon_{i}$ entails

$|N(Z)|\leq s$ (4.6)

for every vertex class $Z\subseteq V(H)$ corresponding to a vertex
$z\in\Upsilon_{i}$ (even if this vertex $z$ fails to belong to
${\Upsilon}_{i}^{\mu\nu}$.)

We first bound the size of the vertex classes of $H$ from above and below. The
ideas in the proofs of the two following facts are similar to those in the
proof of Fact 3.2.

######  Fact 4.5.

Every vertex $z\in V(\Upsilon_{i})$ with $\omega_{\mu\nu}(z)\geq 2$ satisfies

$|Z|\leq\omega_{\mu\nu}(z)(3s-n)\,.$

Moreover, we have

$\displaystyle|X|+|Y|$ $\displaystyle\leq
2(3s-n)=\omega_{\mu\nu}(\\{x,y\\})(3s-n)$ $\displaystyle\text{ and
}|V_{0}|+|V_{2i-1}|$ $\displaystyle\leq
2(3s-n)=\omega_{\mu\nu}(\\{v_{0},v_{2i-1}\\})(3s-n)\,.$

###### Proof.

The upper bound on $|X|+|Y|$ follows from

$|X|+|Y|+2n=|N(A)|+|N(V)|+|N(C)|+|N(U)|+|N(B)|+|N(W)|\overset{\eqref{eq:nh}}{\leq}6s\,.$

Similarly,

$|V_{0}|+|V_{2i-1}|+2n=|N(A)|+|N(B)|+|N(U)|+|N(V)|+|N(V_{i-1})|+|N(V_{i})|\overset{\eqref{eq:nh}}{\leq}6s$

yields the desired upper bound on $|V_{0}|+|V_{2i-1}|$. It remains to prove
$|Z|\leq\omega_{\mu\nu}(z)(3s-n)$ for every $z\in
V(\Upsilon_{i})\smallsetminus\\{v_{0},v_{2i-1},x,y\\}$. Following the same
strategy we have just used, this task reduces to exhibiting a list of
$3\omega_{\mu\nu}(z)$ vertices of $\Upsilon_{i}$ whose neighbourhoods cover
the entire vertex set $\omega_{\mu\nu}(z)$ many times and the set $Z$ itself
even once more. As there are several cases and plenty of vertices to consider,
it seems useful to devise the following notation. For a set $Q\subseteq
V(\Upsilon_{i})$ we denote its characteristic function by ${\mathds{1}}(Q)$,
so

${\mathds{1}}(Q)(q)=\begin{cases}1&\text{ if $q\in Q$}\cr 0&\text{
otherwise}\cr\end{cases}$

for all $q\in V(\Upsilon_{i})$. If $Q=\\{q_{1},\ldots,q_{r}\\}$ comes with an
explicit enumeration of its members, it will be convenient to omit a pair of
curly braces, thus writing ${\mathds{1}}(q_{1},\ldots,q_{r})$ for this
function. For instance, the functions $f$ and $g$ considered earlier can now
be represented as

$f={\mathds{1}}(u,v,w,y)-{\mathds{1}}(x)\quad\text{ and }\quad
g={\mathds{1}}(b,v,v_{i-1},v_{2i-1})-{\mathds{1}}(v_{0})\,.$

Instead of ${\mathds{1}}\bigl{(}V(\Upsilon_{i})\bigr{)}$ we shall just write
${\mathds{1}}$. Next, given a function $h\colon
V(\Upsilon_{i})\longrightarrow{\mathds{Z}}$ we let
$\Sigma(h)=h(V(\Upsilon_{i}))=\sum_{t\in V(\Upsilon_{i})}h(t)$ be the sum of
the values it attains and by $\mathscr{N}(h)\colon
V(\Upsilon_{i})\longrightarrow{\mathds{Z}}$ we mean the function $\sum_{t\in
V(\Upsilon_{i})}h(t)\,{\mathds{1}}\bigl{(}N(t)\bigr{)}$. In other words, this
function satisfies

$\mathscr{N}(h)(t)=\sum_{t^{\prime}\in
N(t)}h(t^{\prime})=h\bigl{(}N(t)\bigr{)}\quad\text{ for every }t\in
V(\Upsilon_{i})\,.$ (4.7)

So we used earlier that

$\displaystyle\mathscr{N}(f)$ $\displaystyle={\mathds{1}}+{\mathds{1}}(y)\,,$
$\displaystyle\Sigma(f)$ $\displaystyle=3\,,$ $\displaystyle\text{and
}\quad\mathscr{N}(g)$ $\displaystyle={\mathds{1}}+{\mathds{1}}(v_{2i-1})\,,$
$\displaystyle\Sigma(g)$ $\displaystyle=3\,,$ (4.8)

the upper bound on $|X|+|Y|$ relies on the fact that the hexagon
$\mathscr{C}_{6}=\\{a,v,c,u,b,w\\}$ has the properties

$\mathscr{N}\bigl{(}{\mathds{1}}(\mathscr{C}_{6})\bigr{)}=2\cdot{\mathds{1}}+{\mathds{1}}(x,y)\,,\quad\Sigma\bigl{(}{\mathds{1}}(\mathscr{C}_{6})\bigr{)}=|\mathscr{C}_{6}|=6$
(4.9)

and soon we are going to need that the inner Andrásfai graph
$\Gamma=\\{v_{0},v_{1},\dots,v_{3i-2}\\}$ satisfies

$\mathscr{N}\bigl{(}{\mathds{1}}(\Gamma)\bigr{)}=i\cdot{\mathds{1}}(\Gamma)+(i-1)\cdot{\mathds{1}}(\mathscr{C}_{6})+{\mathds{1}}(a,b,u,v)\,,\qquad\Sigma\bigl{(}{\mathds{1}}(\Gamma)\bigr{)}=|\Gamma|=3i-1\,.$
(4.10)

Now it suffices to exhibit for every vertex $z\in
V(\Upsilon_{i})\smallsetminus\\{v_{0},v_{2i-1},x,y\\}$ a function

$h^{z}\colon V(\Upsilon_{i})\longrightarrow{\mathds{Z}}_{\geq 0}$

such that

  1. ( )

$\mathscr{N}(h^{z})$ agrees on $V(\Upsilon^{\mu\nu}_{i})$ with
$\omega_{\mu\nu}(z)\cdot{\mathds{1}}+{\mathds{1}}(z)$

  2. ( )

and $\Sigma(h^{z})=3\omega_{\mu\nu}(z)$.

Indeed, once we have such a function $h^{z}$ at our disposal, we can imitate
the above reasoning and argue that

$\displaystyle\omega_{\mu\nu}(z)n+|Z|$
$\displaystyle\overset{\text{\ref{it:0111a}}}{=}\sum_{t\in
V(\Upsilon_{i})}\mathscr{N}(h^{z})(t)|T|\overset{\eqref{eq:1205}}{=}\sum_{t\in
V(\Upsilon_{i})}\sum_{t^{\prime}\in N(t)}h^{z}(t^{\prime})\,|T|$
$\displaystyle=\sum_{t^{\prime}\in
V(\Upsilon_{i})}h^{z}(t^{\prime})\,|N(T^{\prime})|\overset{\eqref{eq:nh}}{\leq}\Sigma(h^{z})s\overset{\text{\ref{it:0111b}}}{=}3\omega_{\mu\nu}(z)s\,,$

which proves the desired inequality $|Z|\leq\omega_{\mu\nu}(z)(3s-n)$.

Starting with the vertices in $\Gamma$ we observe that for every
$k\in{\mathds{Z}}_{3i-1}\smallsetminus\\{0,2i-1\\}$ we have

$\mathscr{N}\bigl{(}{\mathds{1}}(v_{k-i},v_{k},v_{k+i})\bigr{)}={\mathds{1}}(\mathscr{C}_{6})+{\mathds{1}}(\Gamma)+{\mathds{1}}(v_{k})\,.$

By adding (4.9) we infer

$\mathscr{N}\bigl{(}{\mathds{1}}(\mathscr{C}_{6})+{\mathds{1}}(v_{k-i},v_{k},v_{k+i})\bigr{)}=3\cdot{\mathds{1}}+{\mathds{1}}(v_{k})\,,$
(4.11)

which shows that for $k\neq 0,i-1,2i-1$ the function
$h^{v_{k}}={\mathds{1}}(\mathscr{C}_{6})+{\mathds{1}}(v_{k-i},v_{k},v_{k+i})$
has the required properties. Moreover, for $k=i-1$ we deduce from (4.11) with
the help of (4.8) that

$\mathscr{N}\bigl{(}{\mathds{1}}(\mathscr{C}_{6})+{\mathds{1}}(v_{i-1},v_{2i-1},v_{3i-2})-\nu
g\bigr{)}=(3-\nu){\mathds{1}}+{\mathds{1}}(v_{i-1})-\nu{\mathds{1}}(v_{2i-1})\,,$

meaning that we can take
$h^{v_{i-1}}={\mathds{1}}(\mathscr{C}_{6})+{\mathds{1}}(v_{i-1},v_{2i-1},v_{3i-2})-\nu
g$. It remains to deal with the vertices on the hexagon. Starting with $a$, we
observe

$\mathscr{N}\bigl{(}{\mathds{1}}(a,x)-{\mathds{1}}(v_{2i-1})\bigr{)}={\mathds{1}}(a,c,w,x,y)\,,$
(4.12)

which in view of (4.9) and (4.10) entails that the function

$h^{a}=(i-1){\mathds{1}}(\mathscr{C}_{6})+{\mathds{1}}(\Gamma)+{\mathds{1}}(a,x)-{\mathds{1}}(v_{2i-1})$

satisfies

$\mathscr{N}(h^{a})=[(2i-2)\cdot{\mathds{1}}+(i-1)\cdot{\mathds{1}}(x,y)]+[i\cdot{\mathds{1}}(\Gamma)+(i-1)\cdot{\mathds{1}}(\mathscr{C}_{6})+{\mathds{1}}(a,b,u,v)]\\\
+{\mathds{1}}(a,c,w,x,y)=(3i-2)\cdot{\mathds{1}}+{\mathds{1}}(a)\,.$

Together with $\Sigma(h^{a})=6(i-1)+(3i-1)+2-1=3(3i-2)$ this proves that
$h^{a}$ has all required properties. By symmetry, for
$\widetilde{h}^{b}=(i-1)\cdot{\mathds{1}}(\mathscr{C}_{6})+{\mathds{1}}(\Gamma)+{\mathds{1}}(b,x)-{\mathds{1}}(v_{0})$
we obtain $\mathscr{N}(\widetilde{h}^{b})=(3i-2){\mathds{1}}+{\mathds{1}}(b)$
and $\Sigma(\widetilde{h}^{b})=3(3i-2)$, so by (4.8) we may set
$h^{b}=\widetilde{h}^{b}-\nu g$. Next,

$\mathscr{N}\bigl{(}{\mathds{1}}(x)-{\mathds{1}}(v_{0},v_{2i-1},w)\bigr{)}={\mathds{1}}(c)-{\mathds{1}}(a,b,u,v)-{\mathds{1}}(\Gamma)$
(4.13)

reveals that the function
$h^{c}=(i-1)\cdot{\mathds{1}}(\mathscr{C}_{6})+{\mathds{1}}(\Gamma)+{\mathds{1}}(x)-{\mathds{1}}(v_{0},v_{2i-1},w)$
has the property

$\mathscr{N}(h^{c})=[(2i-2)\cdot{\mathds{1}}+(i-1)\cdot{\mathds{1}}(x,y)]+[i\cdot{\mathds{1}}(\Gamma)+(i-1)\cdot{\mathds{1}}(\mathscr{C}_{6})+{\mathds{1}}(a,b,u,v)]\\\
+[{\mathds{1}}(c)-{\mathds{1}}(a,b,u,v)-{\mathds{1}}(\Gamma)]=(3i-3){\mathds{1}}+{\mathds{1}}(c)$

and because of $\Sigma(h^{c})=6(i-1)+(3i-1)+1-3=3(3i-3)$ this establishes the
desired bound $|C|\leq(3i-3)(3s-n)$. Utilising that similar to (4.12), (4.13)
we have

$\displaystyle\mathscr{N}\bigl{(}{\mathds{1}}(u,y)-{\mathds{1}}(v_{2i-1})\bigr{)}$
$\displaystyle={\mathds{1}}(c,u,w,x,y)$
$\displaystyle\mathscr{N}\bigl{(}{\mathds{1}}(v,y)-{\mathds{1}}(v_{0})\bigr{)}$
$\displaystyle={\mathds{1}}(c,v,w,x,y)$ $\displaystyle\text{ and
}\quad\mathscr{N}\bigl{(}{\mathds{1}}(y)-{\mathds{1}}(c,v_{0},v_{2i-1})\bigr{)}$
$\displaystyle={\mathds{1}}(w)-{\mathds{1}}(a,b,u,v)-{\mathds{1}}(\Gamma)$

one confirms easily that the functions

$\displaystyle h^{u}$
$\displaystyle=(i-1){\mathds{1}}(\mathscr{C}_{6})+{\mathds{1}}(\Gamma)+{\mathds{1}}(u,y)-{\mathds{1}}(v_{2i-1})-\mu
f$ $\displaystyle h^{v}$
$\displaystyle=(i-1){\mathds{1}}(\mathscr{C}_{6})+{\mathds{1}}(\Gamma)+{\mathds{1}}(v,y)-{\mathds{1}}(v_{0})-\mu
f-\nu g$ $\displaystyle\text{ and }\quad h^{w}$
$\displaystyle=(i-1){\mathds{1}}(\mathscr{C}_{6})+{\mathds{1}}(\Gamma)+{\mathds{1}}(y)-{\mathds{1}}(c,v_{0},v_{2i-1})-\mu
f$

take care of the three remaining vertex classes. ∎

Adding all inequalities provided by Fact 4.5 we obtain $n\leq(3k-1)(3s-n)$
(recall (4.3) and (4.5)), whence

$\frac{kn}{(3k-1)}\leq s$

and the number

$\lambda=(3k-1)s-kn=k(3s-n)-s$ (4.14)

is nonnegative. For later use we rewrite this in the form

$n=(3k-1)(3s-n)-3\lambda\overset{\eqref{eq:2212}}{=}\omega_{\mu\nu}\bigl{(}V(\Upsilon_{i})\bigr{)}(3s-n)-3\lambda\,.$
(4.15)

Similarly, (4.6) and (4.4) yield

$|N(Z)|\leq
s=k(3s-n)-\lambda=\omega_{\mu\nu}\bigl{(}N(z)\bigr{)}(3s-n)-\lambda$ (4.16)

for every vertex $z\in V(\Upsilon^{\mu\nu}_{i})$. Now we are ready for a lower
bound on the sizes of the vertex classes of $H$.

######  Fact 4.6.

If $z\in V(\Upsilon_{i})$, then

$|Z|\geq\omega_{\mu\nu}(z)(3s-n)-\lambda\,.$ (4.17)

###### Proof.

As we shall prove by means of a complete case analysis, there exist two
adjacent non-neighbours $z^{\prime}$, $z^{\prime\prime}$ of $z$ in
$\Upsilon^{\mu\nu}_{i}$ such that each of the sets $\\{x,y\\}$ and
$\\{v_{0},v_{2i-1}\\}$ is either contained in $N(z^{\prime})\cup
N(z^{\prime\prime})\cup\\{z\\}$ or in its complement.

Once we have two such vertices $z^{\prime}$ and $z^{\prime\prime}$, the
argument proceeds as follows. Due to $z^{\prime}z^{\prime\prime}\in
E(\Upsilon_{i})$ and $zz^{\prime},zz^{\prime\prime}\not\in E(\Upsilon_{i})$
the union $R=\\{z\\}\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}N(z^{\prime})\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}N(z^{\prime\prime})$
is disjoint. Let $S=V(\Upsilon_{i})\smallsetminus R$ be the complement of $R$
and write

$R_{H}=Z\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}N(Z^{\prime})\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}N(Z^{\prime\prime})\quad\text{
as well as }\quad S_{H}=V(H)\smallsetminus R_{H}$

for the sets corresponding to $R$ and $S$ in $H$. Fact 4.5 implies

$|S_{H}|\leq\omega_{\mu\nu}(S)(3s-n)$ (4.18)

and, consequently, we have

$\displaystyle|Z|$
$\displaystyle+|N(Z^{\prime})|+|N(Z^{\prime\prime})|=|R_{H}|=n-|S_{H}|$
$\displaystyle\overset{\eqref{eq:1709}}{\geq}\omega_{\mu\nu}\bigl{(}V(\Upsilon_{i})\bigr{)}(3s-n)-3\lambda-\omega_{\mu\nu}(S)(3s-n)=\omega_{\mu\nu}(R)(3s-n)-3\lambda$
$\displaystyle\overset{\eqref{eq:vs}}{\geq}\omega_{\mu\nu}(z)(3s-n)-\lambda+|N(Z^{\prime})|+|N(Z^{\prime\prime})|\,,$

i.e., $|Z|\geq\omega_{\mu\nu}(z)(3s-n)-\lambda$. So it remains to check that
the auxiliary vertices $z^{\prime}$ and $z^{\prime\prime}$ do indeed exist and
we list some possible choices in the table that follows.

$z$ | $v_{0}$ | $v_{1},\ldots,v_{2i-2}$ | $v_{2i-1}$ | $v_{2i},\ldots,v_{3i-2},a,v$ | $b,u$ | $c,w$ | $x$ | $y$
---|---|---|---|---|---|---|---|---
$z^{\prime}$, $z^{\prime\prime}$ |  $c$, $v$ |  $c$, $x$ |  $c$, $u$ |  $b$, $u$ |  $a$, $v$ |  $v_{0}$, $v_{i}$ |  $u$, $v_{0}$ |  $a$, $v_{0}$

This concludes the proof of Fact 4.6. ∎

We are left with the task of proving Lemma 4.1 itself. To this end we remark
that $H$ can be regarded as a blow-up of the graph $G^{\mu\nu}_{i}$ considered
in Fact 4.2. In fact, every vertex $z$ of $\Upsilon^{\mu\nu}_{i}$ corresponds
to some vertex class $Z$ of $H$ and due to $\omega_{\mu\nu}(z)\geq 1$ we can
partition each such vertex class into $\omega_{\mu\nu}(z)$ “particles” of size
$\lfloor|Z|/\omega_{\mu\nu}(z)\rfloor$ or $\lceil|Z|/\omega_{\mu\nu}(z)\rceil$
each. Owing to Fact 4.6 the sizes of these particles are at least

$\displaystyle\left\lfloor\frac{|Z|}{\omega_{\mu\nu}(z)}\right\rfloor$
$\displaystyle\overset{\eqref{vegalow}}{\geq}\left\lfloor\frac{\omega_{\mu\nu}(z)(3s-n)-\lambda}{\omega_{\mu\nu}(z)}\right\rfloor=3s-n-\left\lceil\frac{\lambda}{\omega_{\mu\nu}(z)}\right\rceil$
(4.19) $\displaystyle\geq
3s-n-\lambda\overset{\eqref{eq:lamda}}{=}(k-1)n-(3k-4)s\,.$

As the particles endow $H$ with the structure of a blow-up of
$G^{\mu\nu}_{i}$, Corollary 2.4 shows that we have indeed

$e(H)\leq g_{k}(n,s)\,.$

This concludes the proof of Lemma 4.1. ∎

###  4.3. Proof of Lemma 4.4.

Corollary 2.4( ) ‣ 2.4 yields

$\frac{kn}{3k-1}\leq s\leq\frac{(k-1)n}{3k-4}\,,$

whence $0\leq\lambda\leq 3s-n$. In the special case $\lambda=0$ the Facts 4.5
and 4.6 imply that every vertex $z\in V({\Upsilon}_{i}^{\mu\nu})$ satisfies
$|Z|=\omega_{\mu\nu}(z)(3s-n)$, meaning that statement ( ) ‣ 4.3 holds. From
now on we suppose $\lambda\geq 1$, which entails the estimate on $s$ occurring
in ( ) ‣ 4.3 and ( ) ‣ 4.3.

######  Claim 4.7.

There exists a vertex $z\in
V({\Upsilon}_{i}^{\mu\nu})\cap\\{x,y,v_{0},v_{2i-1}\\}$ such that
$\omega_{\mu\nu}(z)=1$ and $|Z|=3s-n-\lambda$.

###### Proof.

Recall that in the proof of Lemma 4.1 we viewed $H$ as a blow-up of the
$k$-regular graph $G_{i}^{\mu\nu}$. By Corollary 2.4 at least one of the
particles occurring in this construction has the size
$(k-1)n-(3k-4)s=(3s-n)-\lambda$. Let $z\in V({\Upsilon}_{i}^{\mu\nu})$ be a
vertex one of whose $\omega_{\mu\nu}(z)$ particles has this size. Now (4.19)
needs to hold with equality and we have
$\lceil\lambda/\omega_{\mu\nu}(z)\rceil=\lambda$. For this reason at least one
of the equations $\omega_{\mu\nu}(z)=1$ or $\lambda=1$ is true. In the former
case, $z\in\\{x,y,v_{0},v_{2i-1}\\}$ is immediate and we are done.

Now suppose for the sake of contradiction that $\lambda=1$ and that $|Z|\neq
3s-n-\lambda$ holds for every $z\in
V({\Upsilon}_{i}^{\mu\nu})\cap\\{x,y,v_{0},v_{2i-1}\\}$ with
$\omega_{\mu\nu}(z)=1$. Together with the Facts 4.5 and 4.6 this yields
$|Z|\leq\omega_{\mu\nu}(z)(3s-n)$ for all vertices $z\in
V({\Upsilon}_{i}^{\mu\nu})$.

Concerning the set $M=\\{z\in
V({\Upsilon}_{i}^{\mu\nu})\colon|Z|<\omega_{\mu\nu}(z)(3s-n)\\}$ of vertices
for which this estimate fails to be sharp we can deduce from

$n=\sum_{z\in
V({\Upsilon}_{i}^{\mu\nu})}|Z|\leq\omega_{\mu\nu}\bigl{(}V({\Upsilon}_{i}^{\mu\nu})\bigr{)}(3s-n)-|M|$

and (4.15) that $|M|\leq 3$. Owing to $\chi({\Upsilon}_{i}^{\mu\nu})=4$ this
shows that the neighbourhoods of the vertices in $M$ cannot cover the entire
vertex sets of ${\Upsilon}_{i}^{\mu\nu}$ or, in other words, that there is a
vertex $z_{\star}\in V({\Upsilon}_{i}^{\mu\nu})$ whose neighbourhood is
disjoint to $M$. But now

$s\geq|N(Z_{\star})|=\sum_{z\in N(z_{\star})}|Z|=\sum_{z\in
N(z_{\star})}\omega_{\mu\nu}(z)(3s-n)=k(3s-n)$

contradicts (4.16). This completes the proof of Claim 4.7. ∎

Let us observe that if the vertex $z$ delivered by Claim 4.7 is either $x$ or
$y$, then $\mu=0$, while if it is one of $v_{0}$, $v_{2i-1}$, then $\nu=0$.

First Case. We have $\mu=0$ and one of $X$, $Y$ has size $3s-n-\lambda$.

The product of the four transpositions $x\longleftrightarrow y$,
$a\longleftrightarrow u$, $b\longleftrightarrow v$, and $c\longleftrightarrow
w$ is an automorphism of ${\Upsilon}_{i}^{\mu\nu}$ and, since we only aim at
determining $H$ up to isomorphism this fact shows that without loss of
generality we may suppose $|Y|=3s-n-\lambda$.

Now for $y$ in place of $z$ the proof of Fact 4.6 goes through with equality.
In particular, if we work with the pair
$\\{z^{\prime},z^{\prime\prime}\\}=\\{a,v_{0}\\}$ indicated in the table, we
need to have equality in (4.18), which in turn implies in view of Fact 4.5
that

$|Z|=\omega_{\mu\nu}(z)(3s-n)$ (4.20)

holds for all $z\in\\{b,c,v_{2i},\ldots,v_{3i-2}\\}$. Working with the pair
$\\{a,v_{i-1}\\}$ or $\\{b,v_{i}\\}$ instead we learn that (4.20) is also
valid for all $z\in\\{v_{i},\ldots,v_{2i-2}\\}$ and all
$z\in\\{a,v_{1},\ldots,v_{i-1}\\}$. Altogether, this proves (4.20) for all
$z\neq v_{0},v_{2i-1},u,v,w,x,y$.

Now $|N(V_{2i})|\leq s=\omega_{\mu\nu}\bigl{(}N(v_{2i})\bigr{)}(3s-n)-\lambda$
and Fact 4.6 yield

$|W|=\omega_{\mu\nu}(w)(3s-n)-\lambda\,,$

meaning for $z=w$ the estimates entering the proof of Fact 4.6 hold with
equality as well. Applying this observation to $\\{v_{0},v_{i}\\}$ playing the
rôle of $\\{z^{\prime},z^{\prime\prime}\\}$ and to (4.18) we conclude
$|X|+|Y|=2(3s-n)$, which in turn entails $|X|=(3s-n)+\lambda$. Thus
$|N(C)|\leq s$ and Fact 4.6 are only compatible if
$|Z|=\omega_{\mu\nu}(z)(3s-n)-\lambda$ holds for $z=u,v$ as well.

Finally, $|V_{i}|>\omega_{\mu\nu}(v_{i})(3s-n)-\lambda$ and Corollary 2.4( ) ‣
2.4 yield $|N(V_{i})|=s$, whence

$|V_{0}|=\omega_{\mu\nu}(v_{0})(3s-n)\,.$

The same argument applied to $V_{i-1}$ discloses
$|V_{2i-1}|=\omega_{\mu\nu}(v_{2i-1})(3s-n)$ and altogether this concludes the
proof that $|Z|=\omega_{\mu\nu}(z)(3s-n)-\lambda f(z)$ holds for every $z\in
V({\Upsilon}_{i}^{\mu\nu})$, i.e., that $H$ is as described in ( ) ‣ 4.3.

Second Case. We have $\nu=0$ and one of $V_{0}$, $V_{2i-1}$ has size
$3s-n-\lambda$.

We will show that outcome ( ) ‣ 4.3 of our lemma occurs. The argument will be
very similar to the one we saw in previous case. First, we note that the
reflection $v_{j}\longmapsto v_{2i-1-j}$ of $\Gamma$ composed with the
transpositions $a\longleftrightarrow b$, $u\longleftrightarrow v$ constitutes
an automorphism of ${\Upsilon}_{i}^{\mu\nu}$ that exchanges $v_{0}$ and
$v_{2i-1}$. Thus we may suppose without loss of generality that
$|V_{2i-1}|=3s-n-\lambda$.

As before, we need to have equality in (4.18) when running the proof of Fact
4.6 for $z=v_{2i-1}$ and $\\{z^{\prime},z^{\prime\prime}\\}$ being one of the
pairs $\\{a,x\\}$, $\\{a,w\\}$, or $\\{c,u\\}$. Consequently, (4.20) holds
whenever $z\in\\{v_{i},\ldots,v_{2i-2},v_{2i},\ldots,v_{3i-2},a,c,u,w\\}$. Now
$|N(V_{3i-2})|\leq s$ and Fact 4.6 yield

$|V_{i-1}|=\omega_{\mu\nu}(v_{i-1})(3s-n)-\lambda\,.$

This equality case of Fact 4.6 can be analysed by using the pair $\\{c,x\\}$
in place of $\\{z^{\prime},z^{\prime\prime}\\}$. In this manner we infer that
(4.20) holds for $z\in\\{v_{1},\ldots,v_{i-2}\\}$ as well and, moreover, that
$|V_{0}|=(3s-n)+\lambda$. Together with $|N(V_{i})|\leq s$ and Fact 4.6 this
establishes $|Z|=\omega_{\mu\nu}(z)(3s-n)-\lambda$ for $z=b,v$ and it remains
to check (4.20) for $z=x,y$. To this end, we observe that
$|A|>\omega_{\mu\nu}(a)(3s-n)-\lambda$ and Corollary 2.4( ) ‣ 2.4 yield
$|N(A)|=s$, whence $|X|=\omega_{\mu\nu}(x)(3s-n)$. The argument for $Y$ is
similar but considers $U$ instead of $A$. ∎

##  5\. Proofs of the main results

The main ingredient of our argument is a result of Brandt and Thomassé [BT]
which states that all maximal triangle-free graphs of large minimum degree are
blow-ups of Andrásfai and Vega graphs. A graph $G$ is _maximal triangle-free_
if adding any missing edge to $G$ creates a triangle.

######  Theorem 5.1.

Every maximal triangle-free graph on $n$ vertices with minimum degree greater
than $n/3$ is a proper blow-up of some Andrásfai graph or Vega graph.

Next we recall [LPR]*Fact 2.6, which will allows us to restrict to the
‘correct’ range of $s$ when proving Theorem 1.3.

######  Fact 5.2.

If $n\geq s\geq 1$ and $k\geq 2$ are such that
${s\notin\bigl{(}\frac{k}{3k-1}n,\frac{k-1}{3k-4}n\bigr{)}}$, then

$\mathrm{ex}(n,s)\leq g_{k}(n,s)$

We are now ready for the proof of our second main result.

###### Proof of Theorem 1.3.

Observe that adding any edges to $H$ can neither increase its independence
number nor decrease its minimum degree. Thus, we may and shall assume that $H$
is a maximal triangle-free graph.

Due to Fact 5.2, it suffices to consider the case

$\Delta(H)\leq\alpha(H)\leq s<\frac{k-1}{3k-4}n\,.$

Since $\delta(H)>(k+1)n/(3k+2)>n/3$, Theorem 5.1 tells us that $H$ is a proper
blow-up of some graph $J$, which is either an Andrásfai graph $\Gamma_{\ell}$,
or a Vega graph ${\Upsilon}_{i}^{\mu\nu}$. In the latter case we set
$\ell=9i-(6+\mu+\nu)$. Now in both cases $J$ has a proper $\ell$-regular blow-
up on $3\ell-1$ vertices and Lemma 2.2 yields $k=\ell$. If $J=\Gamma_{k}$ is
an Andrásfai graph the assertion follows from Lemma 3.3 and if $J$ is a Vega
graph we use Lemma 4.1 instead. ∎

The other main result follows by means of a vertex deletion argument.

###### Proof of Theorem 1.2.

Define

$\zeta=\frac{1}{8k^{2}}\quad\text{ and }\quad\gamma=\frac{1}{600k^{6}}\,.$

Consider a triangle-free graph $G$ on $n$ vertices with $\alpha(G)\leq s$ and
$e(G)=\mathrm{ex}(n,s)$, where

$\frac{k}{3k-1}n\leq s\leq\left(\frac{k}{3k-1}+\gamma\right)n\,.$ (5.1)

Since $\gamma$ is sufficiently small, we have $s<(k-1)n/(3k-4)$ and Fact 5.2
implies $e(G)\leq g_{\ell}(n,s)$ for every $\ell\neq k$. On the other hand,
Lemma 3.5 yields

$e(G)=\mathrm{ex}(n,s)\geq g_{k}(n,s)$ (5.2)

and it remains to prove that this holds with equality. It will be convenient
to rewrite (5.2) as

$e(G)\geq
g_{k}(n,s)=\tfrac{1}{2}\bigl{[}ns-\bigl{(}(k-1)n-(3k-4)s\bigr{)}\bigl{(}(3k-1)s-kn\bigr{)}\bigr{]}\,.$

Since

$0\leq(3k-1)s-kn<3k\gamma n$

and

$(k-1)n-(3k-4)s\leq\frac{(3k-1)(k-1)}{k}s-(3k-4)s=\frac{s}{k}\,,$

we have

$\bigl{(}(k-1)n-(3k-4)s\bigr{)}\bigl{(}(3k-1)s-kn\bigr{)}<3\gamma ns\,,$

and thus

$ns-2e(G)<3\gamma ns\,.$

Therefore, the set

$A=\left\\{v\in V(G)\colon d(v)<\left(1-\zeta\right)s\right\\}$ (5.3)

satisfies

$\zeta s|A|\leq\sum_{v\in V}\left(s-d(v)\right)=ns-2e(G)<3\gamma ns$

and, consequently,

$|A|<\frac{3\gamma n}{\zeta}=\frac{n}{25k^{4}}\,.$ (5.4)

Now our argument will proceed as follows. We shall verify that the graph
$G^{\prime}=G-A$ satisfies the assumptions of Theorem 1.3 and, hence,
$e(G^{\prime})$ is bounded from above by $g_{k}(n-|A|,s)$. Then, using the
fact that all vertices in $A$ are of small degree, we derive an upper bound of
$g_{k}(n,s)$ on the number of edges in $G$.

For the minimum degree of $G^{\prime}$ we obtain

$\displaystyle\delta(G^{\prime})$
$\displaystyle\geq\left(1-\zeta\right)s-|A|>\frac{k}{3k-1}n-\frac{n/2}{8k^{2}}-\frac{n}{25k^{4}}$
$\displaystyle>\left(\frac{k+1}{3k+2}+\frac{1}{12k^{2}}-\frac{1}{16k^{2}}-\frac{1}{100k^{2}}\right)n$
$\displaystyle>\frac{k+1}{3k+2}n\geq\frac{k+1}{3k+2}|V(G^{\prime})|\,.$

As the graph $G^{\prime}$ is triangle-free and satisfies
$\alpha(G^{\prime})\leq s$, this shows that Theorem 1.3 applies to
$G^{\prime}$ and we are led to

$e(G^{\prime})\leq
g_{k}(n-|A|,s)=g_{k}(n,s)-|A|\left(k(k-1)n-\tfrac{1}{2}k(k-1)|A|-k(3k-4)s\right)\,.$
(5.5)

Now our choice of $\zeta$ and $\gamma$ yields

$\displaystyle\bigl{(}(k-1)(3k-1)-\zeta\bigr{)}s$
$\displaystyle\leq\left((k-1)(3k-1)-\frac{1}{8k^{2}}\right)\left(\frac{k}{3k-1}+\frac{1}{600k^{6}}\right)n$
$\displaystyle<\left(k(k-1)+\frac{1}{200k^{4}}-\frac{1}{8k(3k-1)}\right)n$
$\displaystyle<\left(k(k-1)+\frac{1}{50k^{2}}-\frac{1}{25k^{2}}\right)n<k(k-1)\left(1-\frac{1}{50k^{4}}\right)n$
$\displaystyle\overset{\eqref{eq:0027}}{<}k(k-1)(n-\tfrac{1}{2}|A|)\,,$

and for this reason (5.5) can be continued to

$\displaystyle e(G^{\prime})$ $\displaystyle\leq
g_{k}(n,s)-\bigl{(}(k-1)(3k-1)-\zeta-k(3k-4)\bigr{)}|A|s$
$\displaystyle=g_{k}(n,s)-(1-\zeta)|A|s\,.$

Every vertex in $A$ has degree at most $(1-\zeta)s$ in $G$, so we arrive at

$e(G)\leq e(G^{\prime})+(1-\zeta)|A|s\leq g_{k}(n,s)\,,$ (5.6)

which together with (5.2) concludes the proof of Theorem 1.2. ∎

Finally, let us remark that our results allow to determine the extremal graphs
for Theorem 1.2.

######  Corollary 5.3.

Suppose that $k\geq 2$ and that $G$ denotes a triangle-free graph on $n$
vertices with $\alpha(G)\leq s$ for some integer $s$ satisfying

$\frac{k}{3k-1}n\leq s\leq\left(\frac{k}{3k-1}+\frac{1}{600k^{6}}\right)n\,.$

If $e(G)=\mathrm{ex}(n,s)$, then $G$ is isomorphic to a graph in
$\mathscr{G}^{n}_{k}(s)\cup\mathscr{H}^{n}_{k}(s)$.

###### Proof.

Following the proof of Theorem 1.2, we see that (5.6) holds with equality, for
which reason the set $A$ defined in (5.3) has to be empty. In other words,
$G^{\prime}=G$ and the proof of Theorem 1.3 discloses that $G^{\prime}$ is a
blow-up of either the Andrásfai graph $\Gamma_{k}$, or of a Vega graph
$\Upsilon^{\mu\nu}_{i}$ with $k=9i-(6+\mu+\nu)$. In the former case, Lemma 3.5
shows that $G$ is isomorphic to a graph in $\mathscr{G}^{n}_{k}(s)$ and in the
latter case we apply Lemma 4.4. ∎

In fact, we strongly suspect that these are the only extremal graphs for the
whole range of $s$, i.e., that the following stronger version of our initial
conjecture holds.

######  Conjecture 5.4.

If $n/3<s\leq n/2$, then

$\mathrm{ex}(n,s)=\min_{k}g_{k}(n,s)\,,$

where $g_{k}(n,s)$ is defined by (1.2). Moreover, each extremal graph with
$\mathrm{ex}(n,s)$ edges is isomorphic to one of the graphs from the families
$\mathscr{G}^{n}_{k}(s)$ and $\mathscr{H}^{n}_{k}(s)$ described in the
Definitions 3.4 and 4.3, respectively.

## References


11institutetext: Niels Bohr Institute, Copenhagen University, Denmark

# The challenges at FCC-ee

Mogens Dam

(Received: / Revised version: )

###### Abstract

At FCC-ee, about $1.7\times 10^{11}$ Z $\to$ +- events will be produced. This
high statistics in the clean e+e- environment opens the possibility of much
improved determinations of -lepton properties and, via the measurement of the
polarisation, of the neutral-current couplings of electrons and $\tau$s.
Improved measurements of -lepton properties – lifetime, leptonic branching
fractions, and mass – allow important tests of lepton universality. The
experimental challenge is to match as far as possible statistical
uncertainties generally at the $10^{-5}$ level. This applies in particular to
the lifetime measurement, which is derived from the 2.2-mm average flight
distance, and for the branching fraction and polarisation measurements, where
the cross-channel contamination is of particular concern. These issues raise
strict detector requirements, in particular, on the accuracy of the
construction and alignment of the vertex detector and of the precise
calorimetric separation and measurement of photons and 0s in the collimated
decay topologies.

###### pacs:

PACS-keydescribing text of that key and PACS-keydescribing text of that key

††offprints:

##  1 Introduction

At an instantaneous luminosity of $2.3\times 10^{36}$ cm-2s-1 at two (possibly
four) interaction points, the FCC-ee will produce about $5\times 10^{12}$ Z
decays during a four-year high-statistics scan around the Z pole FCC:2018evy ;
Abada:2019lih ; Blondel:2021ema . This will result in about $1.7\times
10^{11}$ decays Z $\to$ +-, and opens the door to a very rich -physics
programme, as recently pointed out in Pich:2020qna . Included are unique,
high-precision measurements of the Z-to- couplings as well as measurements of
a wide palette of -lepton properties in general. With the experimental
advantage of a sizeable, well-defined -lepton boost-factor, $\beta\gamma\simeq
26$, very clean background conditions, and somewhat larger statistics than at
Belle II Belle-II:2018jsg  and at a potential future high-luminosity -charm
factory BNPI-STCF ; Luo:2018njj , complementary and very competitive
measurements can be expected.

The lepton is a compelling probe in precision tests of the Standard Model (SM)
because of the well-understood mechanisms that govern its production and
decay. In the SM, the electroweak couplings of the three generations of
leptons are universal, and the three lepton family numbers are individually
conserved. This conservation is violated in the neutral sector by the
observation of neutrino oscillations. Via loop diagrams, this induces also
lepton flavour violation among charged leptons. The rates of such processes
are however unobservably small at the $10^{-50}$ level Illana:1999ww , so that
any observation of charged lepton flavour violation, in the same way as any
observation of the violation of lepton universality, would be an unambiguous
signal for physics beyond the SM.

The FCC-ee -physics programme includes the precise determination of the
neutral-current chiral couplings of the electron and via measurement of the
polarisation; a much improved test of the universality between lepton
generations of the charged-current couplings via measurement of -lepton
properties, lifetime, mass, and leptonic branching fractions; and very
sensitive tests of charged lepton flavour violations in and in Z decays.
Experimental challenges are numerous in order to exploit the rich data sample
to the maximum. Careful design of the detector systems is necessary to enable
control of systematic effects down as far as possible towards the targets
defined by the statistical precisions. The collimated -decay topologies call,
in particular, for a very good multi-particle separation both for charged and
for neutral final-states particles. In general, high performance vertexing,
tracking and electromagnetic calorimetry will be essential.

With focus on the measurement methodology and on the associated detector
requirements, three main topics are considered in this essay: _i_) measurement
of the polarisation and of exclusive branching fractions, _ii_) test of lepton
universality via precision measurements of -lepton properties, and _iii_)
tests of charged lepton flavour violations in Z and in decays. A wider
discussion of detector requirements at FCC-ee can be found in Ref.
Azzi:2021ylt .

##  2  polarisation and exclusive branching fractions

The polarization in Z decays is one of the most sensitive electroweak
observables ALEPH:2005ab . The analysis of the polarization’s dependence on
the scattering angle $\theta$ between the - and the e- beam gives access to
both the and electron chiral coupling asymmetries
$\mathcal{A}_{\text{\texttau}}$ and $\mathcal{A}_{\mathrm{e}}$ independently,

$P(\cos\theta)=\frac{\mathcal{A}_{\text{\texttau}}(1+\cos^{2}\theta)+2\mathcal{A}_{\mathrm{e}}\cos\theta}{(1+\cos^{2}\theta)+2\mathcal{A}_{\mathrm{e}}\mathcal{A}_{\text{\texttau}}\cos\theta},$
(1)

and serves as a crucial ingredient of a full lepton-by-lepton extraction of
the neutral-current chiral couplings. In the leptonic decays,
$\text{\texttau}\to\text{e}\bar{\text{\textnu}}\text{\textnu}$,
$\text{\textmu}\bar{\text{\textnu}}\text{\textnu}$, and in decays to a single
final-state hadron, $\text{\texttau}\rightarrow h\text{\textnu}$,
$h=\text{\textpi, K}$, the polarization is derived from the charged-particle
momentum distribution. For decays with multiple final-state hadrons, more
variables are exploited. As an important example, for the dominant decay mode,
$\text{\texttau}\to\text{\textpi\textpi}^{0}\text{\textnu}$, the two sensitive
variables are the 0-system total energy and the asymmetry between the and 0
energies. With each channel having its own set of variables with different
dependence on the polarization, a clean separation between channels, e.g.
between $\text{\texttau}\to\text{\textpi\textnu}$ and
$\text{\texttau}\to\text{\textpi\textpi}^{0}\text{\textnu}$, is essential.

It is important to realise that not only does one have to separate channels
according to 0 multiplicity, but one also has to identify and measure
precisely the individual 0s. The collimation of final states tends to
complicate 0 reconstruction, since photons are close to one another and/or
close to showers generated by charged hadrons. The two photons from a high-
energy 0 may merge due to the limited spatial resolving power of the ECAL. On
the other hand, fake photons may occur due to hadronic interactions or
fluctuations of electromagnetic showers. Detailed simulation studies are
called for in order to quantify precisely the requirements on the ECAL.
Different calorimeter designs have been proposed each with different
performance charateristics in terms of transverse and longitudinal granularity
and energy and spatial resolutions R1calo . Studies should allow a comparison
and optimisation of these designs.

An experimentally related measurement is that of the -decay branching
fractions. Experience from LEP ALEPH_TauBf05  shows that the branching
fractions are most precisely determined via a global analysis method, where,
in a preselected +- event sample, all decays are categorised concurrently
according to a set of predefined decay modes. An important outcome of the
analysis is a precise determination of the vector and axial-vector spectral
functions, which provide important information for the extraction of
$\alpha_{\mathrm{s}}(m^{2}_{\text{\texttau}})$ and
$\alpha_{\mathrm{QED}}(q^{2})$.

For a complete determination of the -decay branching fractions, K/ separation
Wilkinson:2021ehf  is needed over the full allowed momentum range of the final
state mesons, i.e. from the lowest observable momentum to the beam momentum.
Whether this is also the case for the precise -polarization measurement has to
be understood. Due to the different masses of the and K mesons, the kinematics
of the and K ( and K∗) final states obviously differ. And since the
polarisation is extracted from the kinematic distributions, it will be
necessary to know the relative proportions of relative to K ( relative to K∗)
in the selected samples. For experiments with no K/ separation capabilities,
this would have to rely on branching-fraction measurements from other
experiments and/or facilities.

With the current limit on the still unobserved seven-prong -decay mode, up to
$\mathcal{O}(10^{5})$ such decays could be produced at FCC-ee. Kinematically,
up to 11 charged pions (plus one 0) are allowed. For the design of the
tracking detectors R1tracking , it is a worthy exercise to make sure that such
strongly collimated, high-multipicity topologies can be correctly
reconstructed. The precise, high-statistics measurement of multiprong decays
should bring a much improved determination of the -neutrino mass, where the
current 18.2-MeV limit stems from LEP ALEPHnuTauMass . Also for this
measurement, K/ separation will be an important asset in selecting heavy final
states with one or multiple charged kaons. As an interesting, and
experimentally probably very challenging, example, the 3K+2 final state has a
minimum mass only 17 MeV below the mass.

##  3 Tau lepton properties and lepton universality

Precision measurements of -lepton properties – mass, lifetime, and leptonic
branching fractions – provide compelling tests of lepton universality, the
expectation that the couplings between the charged lepton and its associated
neutrino are equal for the three generations,
$g_{\mathrm{e}}=g_{\text{\textmu}}=g_{\text{\texttau}}$. Firstly, the ratio
$g_{\text{\textmu}}/g_{\mathrm{e}}$ can be readily derived from the ratio of
the branching fractions for the two decay modes,
$\text{\texttau}\to\text{\textmu}\bar{\text{\textnu}}\text{\textnu}$ and
$\text{\texttau}\to\mathrm{e}\bar{\text{\textnu}}\text{\textnu}$. Secondly,
the ratio, $g_{\text{\texttau}}/g_{\ell}$, between and light lepton
$\ell=\mathrm{e},\text{\textmu}$, can be derived from the relation

$\left(\frac{g_{\text{\texttau}}}{g_{\ell}}\right)^{2}=\mathcal{B}(\text{\texttau}\to\ell\bar{\text{\textnu}}\text{\textnu})\cdot\frac{\tau_{\text{\textmu}}}{\tau_{\text{\texttau}}}\cdot\left(\frac{m_{\text{\textmu}}}{m_{\text{\texttau}}}\right)^{5},$
(2)

where (small and known) effects due to phase space and radiative and
electroweak corrections have been omitted. In both cases, current data support
lepton universality at the $\mathcal{O}(10^{-3})$ level.

Historically, lepton universality tests took a giant leap with the LEP
measurements based on around one million
$\text{Z}\rightarrow\text{\texttau}^{+}\text{\texttau}^{-}$ events (for a
complete set of references, see ParticleDataGroup:2020ssz ; HFLAV:2019otj ).
Whereas precise -mass measurements (currently $\mathcal{O}(10^{-4})$
precision) have been dominated by threshold scans, LEP provided important
measurements of both the lifetime and the leptonic branching fractions.
Indeed, the LEP branching fraction measurements ($\mathcal{O}(10^{-3}$)) still
stand unchallenged, whereas the world-average life-time measurement
($\mathcal{O}(10^{-3}$)), since LEP, has seen an improvement by about a factor
two from a high-statistics Belle measurement Belle_TauLT14 .

At FCC-ee, with the large number of decays available for study, statistical
precisions on -lepton properties will be generally at the $10^{-5}$ level.
Detailed studies are needed in order to identify the key detector requirements
that will allow systematic uncertainties to follow down as far as possible
towards this target. At this stage, a list of observations are:

Lifetime:

At Z-pole energies, the lifetime is determined via measurement of the 2.2-mm
average flight distance. A lifetime measurement matching the statistical
precision would then correspond to a flight-distance measurement to a few tens
of nanometers accuracy. Approaching towards this target imposes formidable
requirements on the construction and alignment accuracy of the vertex
detector. With a 10–15-mm beam pipe radius, the first vertex detector layer
will be very close to the beam line, and an impact-parameter resolution of
about 3 µm is projected. This is a factor five smaller than at LEP, and
combined with the possibility of much improved systematics checks from the
enormous event samples, a substantial improvement with respect to LEP should
be certainly within reach.

Leptonic branching fractions:

At Z-pole energies, where the separation of a clean and relatively unbiased
sample of $\text{\texttau}^{+}\text{\texttau}^{-}$ events has been
demonstrated, accurate measurements of the leptonic branching fractions rely
primarily on the ability to separate precisely the two leptonic decay modes,
on the one hand, from the single-prong hadronic modes, on the other. The
separation relies critically on a fine-grained calorimeter system combined
with a dedicated muon system R1muondet . In order to reach the required
precise understanding of efficiencies and backgrounds, an independent means of
particle identification will undoubtedly prove indispensable. In this respect,
it is important to realise that the precise LEP results came from experiments
were powerful $\mathrm{d}E/\mathrm{d}x$ measurements played an important rôle
for particle identification. For the separation of low-momentum electrons and
pions, a ring-imaging Cherenkov detector may also be an import asset.

Mass:

With the very large statistics, an important improvement of the -mass
measurement may be possible via the so-called pseudomass method pioneered by
ARGUS ARGUS_TauMass92  and later exploited by OPAL OPAL_TauMass00 , BaBar
BaBar_TauMass09 , and Belle Belle_TauMass07 . In three-prong decays, the
pseudomass variable depends on the measured mass and momentum of the 3 system
and on the beam energy. At FCC-ee, the beam energy is controlled to a
negligible $10^{-6}$ level via resonant spin depolarisation Blondel:2019jmp ,
and only the measurement of the 3 system contributes to the uncertainty. As a
reference process, in order to control the mass and momentum scale, it is
suggested to exploit the very large J/$\psi$ sample from Z decays
($\mathcal{B}(\text{Z}\rightarrow\text{J}/\psi X)=3.5\times 10^{-3}$), and the
fact that the $\text{J}/\psi$ mass is known to the 10-6 precision level from a
measurement by KEDR Anashin:2015rca  at the VEPP-4M collider, likewise based
on resonant spin depolarisation. It can be also considered to make use of
decays with higher charged-particle multiplicities that will provide a larger
fraction of events close to the end-point of the pseudomass distribution.

##  4 Charged Lepton Flavour Violation

With the huge FCC-ee statistics, very sensitive tests of charged lepton
flavour violating (cLFV) processes can be performed in Z decays as well as in
decays.

###  4.1 Z decays

Searches for flavour violating Z decays into µe, µ, and e final states have
been performed at LEP with the most precise limits from DELPHI DELPHI97_CLFVZ
and OPAL OPAL95_CLFVZ , and, more recently, at LHC by ATLAS Aad:2014bca ;
ATLAS:2021bdj . With the recent ATLAS updates on the modes ATLAS:2021bdj , all
LEP bounds have now, finally after 25 years, been superseded. Bounds are
slightly below $10^{-6}$ for the µe mode and slightly below $10^{-5}$ for the
two modes.

In $\text{e}^{+}\text{e}^{-}$ collisions, the $\text{Z}\to\text{\textmu e}$
process would have the astonishing clean signature of a beam-energy electron
in one hemisphere recoiling against a beam-energy muon in the other. The
dominant experimental challenge is believed to be that of so-called
_catastrophic bremsstrahlung_ , a rare process by which a muon radiates off
the major fraction of its energy in the ECAL material. This way, a
$\text{Z}\to\text{\textmu\textmu}$ event could fake the µe signature. Control
of this effect would to first order rely on the ECAL energy resolution and on
the aggressive veto on a possible soft muon track penetrating beyond the ECAL.
Moreover, longitudinal ECAL segmentation would allow vetoing of
electromagnetic showers starting uncharacteristically late. Finally, an
independent method of electron/muon separation such as that provided by a
precise $\text{d}E/\text{d}x$ measurement could potentially be used to control
this effect possibly to a negligible level. Early estimates indicate that an
improvement of the current limit by 2–3 orders of magnitude should be within
reach.

The pursuit of $\text{Z}\to\text{\texttau\textmu}\ (\text{{\texttau}e})$
decays amounts to a search for events with a _clear tau decay_ in one
hemisphere recoiling against a _beam-momentum muon (electron)_ in the other.
This signature receives backgrounds from ordinary final states, where one
decays leptonically,
$\text{\texttau}\to\text{\textmu}\bar{\text{\textnu}}\text{\textnu}$
($\text{\texttau}\to\text{e}\bar{\text{\textnu}}\text{\textnu}$), with the two
neutrinos being very soft, and the charged lepton consequently appearing close
to the end-point at the beam momentum. The separation of signal and background
therefore depends on the experimental precision by which a _beam-momentum
particle_ can be defined, and hence on the momentum resolution at 45.6 GeV.
Studies have demonstrated Dam:2018rfz  that the search sensitivity scales
linear in the momentum resolution combined (in quadrature) with the
contribution from the spread on the collision energy ($\delta
E_{\mathrm{CM}}/E_{\mathrm{CM}}=0.9\times 10^{-3}$) arising from the 60 MeV
beam-energy spread FCC:2018evy . For a realistic momentum resolution of
$1.5\times 10^{-3}$, limits of $\mathcal{O}(10^{-9})$ on the Z branching
fractions look to be within reach.

###  4.2  decays

Very stringent tests of cLFV have been performed in muon decay experiments
where branching-fraction limits below $10^{-12}$ on both of the neutrinoless
decay modes $\text{\textmu}^{-}\to\text{e}^{-}\text{\textgamma}$
MEG_MuToEGamma16  and $\text{\textmu}^{+}\to\mathrm{e^{+}e^{+}e^{-}}$
SINDRUM_MuTo3E88  have been established. All models predicting cLFV in the
muon sector imply a violation also in the sector, whose strength is often
enhanced by several orders of magnitude, usually by some power in the tau-to-
muon mass ratio. Studying cLFV processes in decays offers several advantages
compared to muon decays. Since the is heavy, more cLFV processes are
kinematically allowed, and in addition to the modes
$\text{\texttau}\to\text{{\textmu}(e)}+\text{\textgamma}$ and
$\text{\texttau}\to\text{{\textmu}(e)}+\ell^{+}\ell^{-}$, also semileptonic
and fully hadronic modes can be probed.

A first FCC-ee simulation study Dam:2018rfz  was carried out of
$\text{\texttau}\to\text{\textmu\textgamma}$ and $\text{\texttau}\to
3\text{\textmu}$ as benchmark modes. The analysis strategy employed a _tag
side_ to identify a clear Standard-Model decay and a _signal side_ where cLFV
decays were searched for. Search variables employed were the total energy and
the invariant mass of the final-state system. The present
$\mathcal{O}(10^{-8})$ bounds on both modes are set at the $b$ factories
BABAR_TauToLeptGam10 ; Belle:2021ysv ; BELLE_TauTo3Lept10 . The study suggests
possible improvements of about one (two) orders of magnitude for the
$\text{\texttau}\to\text{\textmu\textgamma}$ ($\text{\texttau}\to
3\text{\textmu}$) mode, largely compatible with similar projections from Belle
II Belle-II:2018jsg . In particular, the
$\text{\texttau}\to\text{\textmu\textgamma}$ search is background limited, and
the sensitivity depends strongly on the assumed detector resolutions. Most
importantly, the sensitivity was found to scale linearly (or slightly
stronger) in the photon energy resolution, which was taken as
$16.5\%/\sqrt{E\,(\text{GeV})}$, inspired by the typical performance of
CALICE-like silicon-based calorimeters R1calo . The photon position resolution
is also important, as it contributes to the invariant-mass calculation. Here,
where a position resolution of 2 mm was assumed, the two contributions from
the energy and position resolutions were found to balance equally in the
invariant mass calculation. Interesting for this measurement is the recently
proposed fine-grained (two longitudinal layers, $1\times 1$ cm2 lateral
segmentation) crystal calorimeter Lucchini:2020bac , which would have an
extremely good energy resolution of $3\%/\sqrt{E\,(\text{GeV})}$ combined with
a spatial resolution of better than 1 mm.

From the two benchmark modes, there is a long way to the nearly 50 cLFV search
modes explored primarily by BaBar and Belle and summarised in HFLAV:2019otj .
More than one third of these modes involve charged kaons and would depend on
the ability to separate pions and kaons over a wide momentum range.

##  5 Unexplored Routes involving Muon Polarisation Measurement

It is interesting to notice that the enormous FCC-ee statistics allows the
observation and measurement of a sizeable sample of muons decaying inside the
detector volume. Indeed, 1.2 million muons from Z $\to$ µµ events will decay,
µ $\to$ e, for each meter of flight distance. This opens the possibility of
measuring the polarisation of muons from Z decays in the same way as the
polarisation of s is measured in the electronic decay mode,  $\to$ e. From the
distribution of the electron momentum fraction,
$x=p_{\text{e}}/p_{\text{\textmu}}$, where the electron energy is precisely
measured by the ECAL, a sample of one million decays would result in a
statistical precision of $4.5\times 10^{-3}$. This can be improved by about
20% by inclusion of the acollinearity angle between the decay electron and the
opposite hemisphere muon.

Parallel to this, but experimentally more challenging, is a unique possibility
of contributing to the determination of the Lorentz structure of the -decay
amplitude. A few hundred thousand muons from decays,  $\to$ µ, will decay, µ
$\to$ e, per meter flight distance inside the detector volume. The challenge
now is _i_) to recognise in each case that a decay has happened by identifying
the decay vertex via a change in the track curvature (and, if available,
possibly also in the specific ionisation), and _ii_) to measure the momentum
both before (muon momeutum, $p_{\text{\textmu}}$) and after (electron
momeutum, $p_{\mathrm{e}}$) the decay vertex. In cases where the decay happens
well inside the tracking volume, this may be possible, and from the
distribution of momentum fractions, $x=p_{\mathrm{e}}/p_{\text{\textmu}}$, the
polarisation of the muon may be derived.

##  6 Conclusions and Outlook

With its enormous sample of Z $\to$ +- events, it is justified to think of
FCC-ee (also!) as a dedicated factory. As an example, touched upon above, it
opens the possibility to measure the Fermi decay constant in decays with a
_statistical_ precision of 10-5, only about one order of magnitude less
precise than what is known today from muon decays. Clearly, it would be a
formidable, possibly impossible, task to control systematics down to this same
level of precision. However, it illustrates well the situation and emphasises
how a thorough study unearthing all aspects of the experimental possibilities
is deserved.

From the palette of measurements discussed in this essay, strong requirements
on the detector design have been already pointed to. Important issues include:
a very precisely constructed and aligned silicon vertex detector for ultimate
lifetime measurements; a light and precise tracking system with superior
multi-track separation for precise momentum and mass measurements; a fine-
grained electromagnetic calorimeter for precise measurement of photons and 0s
in dense topologies; a high-performant muon system for clean pion/muon
separation; particle identification abilities over the full momentum range for
kaon/pion separation and, very importantly, for an independent, non-
destructive electron/pion separation.

## References

  * (1) Future Circular Collider Study, A. Abada et al., FCC-ee: The Lepton Collider: Future Circular Collider Conceptual Design Report Volume 2, Eur. Phys. J. ST 228 no. 2, (2019) 261–623.
  * (2) Future Circular Collider Study, A. Abada et al., FCC Physics Opportunities: Future Circular Collider Conceptual Design Report Volume 1, Eur. Phys. J. C 79 no. 6, (2019) 474.
  * (3) A. Blondel and P. Janot, FCC-ee overview: new opportunities create new challenges, in A future Higgs and Electroweak factory (FCC): Challenges towards discovery, EPJ+ special issue, Focus on FCC-ee, arXiv:2106.13885 [hep-ex].
  * (4) A. Pich, Challenges for tau physics at the TeraZ, in A future Higgs and Electroweak factory (FCC): Challenges towards discovery, EPJ+ special issue, Focus on FCC-ee, arXiv:2012.07099 [hep-ph].
  * (5) Belle-II Collaboration, The Belle II Physics Book, PTEP 2019 no. 12, (2019) 123C01, arXiv:1808.10567 [hep-ex], [Erratum: PTEP 2020, 029201 (2020)].
  * (6) Budker Institute of Nuclear Physics, Project of super c-tau factory. https://ctd.inp.nsk.su/c-tau/.
  * (7) Q. Luo and D. Xu, Progress on Preliminary Conceptual Study of HIEPA, a Super Tau-Charm Factory in China, in 9th International Particle Accelerator Conference.  6, 2018.
  * (8) J. I. Illana, M. Jack, and T. Riemann, Predictions for Z $\to$ µ and related reactions, in 2nd Workshop of the 2nd Joint ECFA / DESY Study on Physics and Detectors for a Linear Electron Positron Collider.  12, 1999, arXiv:hep-ph/0001273.
  * (9) P. Azzi and E. Perez, Exploring requirements and detector solutions for FCC-ee in A future Higgs and Electroweak factory (FCC): Challenges towards discovery, EPJ+ special issue, Focus on FCC-ee, arXiv:2107.04509 [hep-ex].
  * (10) ALEPH, DELPHI, L3, OPAL, and SLD Collaborations, LEP Electroweak Working Group, SLD Electroweak Group, SLD Heavy Flavour Group, Precision electroweak measurements on the Z resonance, Phys. Rept. 427 (2006) 257–454, arXiv:hep-ex/0509008.
  * (11) M. Aleksa, F. Bedeschi, R. Ferrari, F. Sefkow, and C. Tully, Calorimetry at FCC-ee in A future Higgs and Electroweak factory (FCC): Challenges towards discovery, EPJ+ special issue, Focus on FCC-ee. https://www.overleaf.com/read/fqpnwxcpsrdd.
  * (12) ALEPH Collaboration, Branching ratios and spectral functions of $\tau$ decays: Final ALEPH measurements and physics implications, Phys. Rep. 421 no. 5, (2005) 191 – 284.
  * (13) G. Wilkinson, Particle Identification at FCC-ee in A future Higgs and Electroweak factory (FCC): Challenges towards discovery, EPJ+ special issue, Focus on FCC-ee, arXiv:2106.01253 [physics.ins-det].
  * (14) N. Bacchetta, P. Collins, and P. Riedler, Tracking and vertex detectors at FCC-ee in A future Higgs and Electroweak factory (FCC): Challenges towards discovery, EPJ+ special issue, Focus on FCC-ee. https://www.overleaf.com/read/qrwmnbdyxbtg.
  * (15) ALEPH Collaboration, An upper limit on the neutrino mass from three- and five-prong tau decays, European Physical Journal C 2 no. 3, (1998) 395–406.
  * (16) Particle Data Group, P. A. Zyla et al., Review of Particle Physics, PTEP 2020 no. 8, (2020) 083C01.
  * (17) HFLAV Collaboration, Y. S. Amhis et al., Averages of b-hadron, c-hadron, and $\tau$-lepton properties as of 2018, Eur. Phys. J. C 81 no. 3, (2021) 226, arXiv:1909.12524 [hep-ex].
  * (18) Belle Collaboration, Measurement of the $\tau$-lepton Lifetime at Belle, Phys. Rev. Lett. 112 (Jan, 2014) 031801.
  * (19) P. Giacomelli and S. Braibant, Muon detection at FCC-ee in A future Higgs and Electroweak factory (FCC): Challenges towards discovery, EPJ+ special issue, Focus on FCC-ee. https://www.overleaf.com/read/ygzbvphzmphp.
  * (20) ARGUS Collaboration, A measurement of the tau mass, Phys. Lett. B 292 no. 1, (1992) 221 – 228, http://www.sciencedirect.com/science/article/pii/037026939290634G.
  * (21) OPAL Collaboration, A measurement of the $\tau$ mass and the first CPT test with $\tau$ leptons, Phys. Lett. B 492 no. 1, (2000) 23 – 31.
  * (22) BaBar Collaboration, Measurements of the $\tau$ mass and the mass difference of the ${\tau}^{+}$ and ${\tau}^{-}$ at BaBar, Phys. Rev. D 80 (Nov, 2009) 092005.
  * (23) Belle Collaboration, Measurement of the $\tau$ Lepton Mass and an Upper Limit on the Mass Difference between ${\tau}^{+}$ and ${\tau}^{-}$, Phys. Rev. Lett. 99 (Jul, 2007) 011801.
  * (24) A. Blondel et al., Polarization and Centre-of-mass Energy Calibration at FCC-ee, arXiv:1909.12245 [physics.acc-ph].
  * (25) V. Anashin et al., Final analysis of KEDR data on J/$\psi$ and $\psi$(2S) masses, Phys. Lett. B 749 (2015) 50–56.
  * (26) DELPHI Collaboration, Search for lepton flavour number violating Z decays, Z. Phys. C - Particles and Fields 73 no. 2, (Jun, 1997) 243–251.
  * (27) OPAL Collaboration, A search for lepton flavour violating Z decays, Z. Phys. C - Particles and Fields 67 no. 4, (Dec, 1995) 555–563.
  * (28) ATLAS Collaboration, Search for the lepton flavor violating decay $\text{Z}\rightarrow\text{e}\mu$ in pp collisions at $\sqrt{s}=8$ TeV with the ATLAS detector, Phys. Rev. D90 no. 7, (2014) 072010.
  * (29) ATLAS Collaboration, Search for charged-lepton-flavour violation in Z-boson decays with the ATLAS detector, Nature Phys. 17 no. 7, (2021) 819–825, arXiv:2105.12491 [hep-ex].
  * (30) M. Dam, Tau-lepton Physics at the FCC-ee circular e+e- Collider, SciPost Phys. Proc. 1 (2019) 041, arXiv:1811.09408 [hep-ex].
  * (31) MEG Collaboration, Search for the lepton flavour violating decay $\mu^{+}\rightarrow\mathrm{e}^{+}\gamma$ with the full dataset of the MEG experiment, Eur. Phys. J. C76 no. 8, (2016) 434, arXiv:1605.05081 [hep-ex].
  * (32) SINDRUM Collaboration, Search for the decay $\mu^{+}\to\mathrm{e^{+}e^{+}e^{-}}$, Nucl. Phys. B 299 no. 1, (1988) 1 – 6.
  * (33) BaBar Collaboration, Searches for lepton flavor violation in the decays ${\tau}^{\pm{}}\rightarrow{e}^{\pm{}}\gamma$ and ${\tau}^{\pm{}}\rightarrow{\mu}^{\pm{}}\gamma$, Phys. Rev. Lett. 104 (Jan, 2010) 021802.
  * (34) Belle Collaboration, Search for lepton-flavor-violating tau decays to $\ell\gamma$ modes at Belle, arXiv:2103.12994 [hep-ex].
  * (35) Belle Collaboration, Search for lepton-flavor-violating $\tau$ decays into three leptons with 719 million produced $\tau^{+}\tau^{-}$ pairs, Phys. Lett. B 687 no. 2, (2010) 139–143.
  * (36) M. T. Lucchini, W. Chung, S. C. Eno, Y. Lai, L. Lucchini, M.-T. Nguyen, and C. G. Tully, New perspectives on segmented crystal calorimeters for future colliders, JINST 15 no. 11, (2020) P11005, arXiv:2008.00338 [physics.ins-det].