$P_{1},P_{2},P_{3}$, where $P_{i}$ is from $a_{i}$ to $x_{i}$, such that

     * •

$V(H)=(V(P_{1})\cup V(P_{2})\cup V(P_{3}))\setminus\\{x_{1},x_{2},x_{3}\\}$;

     * •

the sets $V(P_{1})$, $V(P_{2})$ and $V(P_{3})$ are pairwise disjoint; and

     * •

for distinct $i,j\in\\{1,2,3\\}$, there are no edges between $V(P_{i})$ and
$V(P_{j})$, except $a_{i}a_{j}$ and possibly $x_{i}x_{j}$.

We also need the following; for a proof see, for example, [3]:

######  Theorem 10.3.

Let $(T,\chi)$ be a tree decomposition of a graph $G$. Then there exist a
vertex $t_{0}\in T$ such that $|D|\leq\frac{1}{2}|V(G)|$ for every component
$D$ of $G\setminus\chi(t_{0})$.

We start with a lemma.

######  Lemma 10.4.

Let $n$ be an integer. Let $G$ be a chordal graph with $n-\epsilon n$
vertices, and assume that $G$ has no clique of size $\epsilon n$. Then there
is $Z\subseteq V(G)$ such that

  * •

$\kappa(Z)\leq 2$, and

  * •

there exist subsets $X_{1},X_{2},X_{3}$ of $V(G)\setminus Z$, pairwise
disjoint and anticomplete to each other, and such that
$|X_{i}|=\left\lceil\frac{1}{17}n\right\rceil$ for every $i\in\\{1,2,3\\}$.

###### Proof.

Since $G$ is chordal, there is a tree decomposition $(T,\chi)$ of $G$ such
that $\chi(t)$ is a clique for every $t\in T$ [33]. By Theorem 10.3, there
exists a vertex $t_{0}\in T$ such that $|D|\leq\frac{n}{2}$ for every
component $D$ of $G\setminus\chi(t_{0})$. Let $X$ be a minimal set of
components of $G\setminus\chi(t_{0})$ such that $|\bigcup_{D\in
X}D|\geq(\frac{1}{4}-2\epsilon)n$.

(44) _$|G\setminus(\bigcup_{D\in X}D\cup\chi(t_{0}))|\geq\frac{1}{4}n$._

Suppose not. Then $|\bigcup_{D\in
X}D\cup\chi(t_{0})|>(\frac{3}{4}-\epsilon)n$. Since $\chi(t_{0})$ is a clique,
it follows that $|\chi(t_{0})|<\epsilon n$, and so $|\bigcup_{D\in
X}D|\geq(\frac{3}{4}-2\epsilon)n$. Let $D_{0}\in X$. Then
$|D_{0}|\leq\frac{1}{2}n$, and so $|\bigcup_{D\in
X\setminus\\{D_{0}\\}}D|\geq(\frac{1}{4}-2\epsilon)n$, contrary to the
minimality of $X$. This proves (10).

Let $X_{1}=\bigcup_{D\in X}D$ and let $Z_{1}=\chi(t_{0})$. Let $Y$ be a subset
of $G\setminus(X_{1}\cup Z_{1})$ with $|Y|=\frac{1}{4}n$, and let
$G^{\prime}=G[Y]$. By Theorem 10.3, there exists a vertex $t_{0}^{\prime}\in
T$ such that $|D|\leq\frac{n}{8}$ for every component $D$ of
$G^{\prime}\setminus\chi(t_{0}^{\prime})$. Let $X^{\prime}$ be a minimal set
of components of $G^{\prime}\setminus\chi(t_{0}^{\prime})$ such that
$|\bigcup_{D\in X^{\prime}}D|\geq(\frac{1}{16}-2\epsilon)n$. Write
$X_{2}=\bigcup_{D\in X^{\prime}}D$ and $Z_{2}=\chi(t_{0}^{\prime})$. Let
$X_{3}=G^{\prime}\setminus(X_{2}\cup Z_{2})$. By (10),
$|X_{3}|\geq\frac{1}{16}n$. Let $Z=Z_{1}\cup Z_{2}$. Then $\kappa(Z)=2$, the
sets $X_{1},X_{2},X_{3}$ are pairwise disjoint and anticomplete to each other,
and $|X_{i}|\geq(\frac{1}{16}-2\epsilon)n=\frac{1}{17}n$. Now the conclusion
of the lemma follows. ∎

Next we prove the following, which immediately implies Theorem 10.1.

######  Theorem 10.5.

Let $G\in\mathcal{C}$ with $|V(G)|=n$, and let $a,b\in V(G)$ be non-adjacent.
Assume that $N(a)\cap\operatorname{Hub}(G)=\emptyset$ and $N(a)\neq\emptyset$.
Then there is a set $Z\subseteq V(G)\setminus\\{a,b\\}$ with
$\kappa(Z)\leq-C\frac{1}{\log(1-\gamma)}(\max(1,\log|N(a)|))$ and such that
every component of $G\setminus Z$ contains at most one of $a,b$.

###### Proof.

We may assume that $|N(a)|>-C\frac{1}{\log(1-\gamma)}$. Let $D$ be the
component of $G\setminus N[a]$ such that $b\in D$. We may assume that $G=D\cup
N[a]$. Write $X=N(a)$. Our first goal is to show the following:

(45) _Assume that either $X$ is pure, or there does not exist
$X^{\prime}\subseteq X$ with $|X^{\prime}|\geq\frac{1-4\epsilon}{2}|X|$ such
that $X^{\prime}$ is pure. Then there exists $S\subseteq X\cup(D\setminus b)$
with $\kappa(S)\leq C-2$ such the component $D(b)$ of $D\setminus S$ with
$b\in D(b)$ meets $N(x)$ for at most $(1-\epsilon)|X|$ vertices $x\in
X\setminus S$._

The proof proceeds in several steps.

(46) _$X$ is chordal._

Suppose that there is a hole $H\subseteq X$. Then $(H,a)$ is a wheel. But $D$
is connected and $H\subseteq N(D)$, contrary to Theorem 6.5. This proves (10).

(47) _If there is a clique $K$ of size $\epsilon|X|$ in $X$, then (10) holds._
.

Suppose such a clique $K$ exists. Now setting $S=K$, it follows that (10)
holds. This proves (10).

Let $Z^{\prime}=N(b)\cap X^{\prime}$. Since $G$ is $C_{4}$-free, it follows
that $Z^{\prime}$ is a clique. By (10), we can apply Lemma 10.4 to $X\setminus
Z^{\prime}$; let $Z,X_{1},X_{2},X_{3}\subseteq X\setminus Z^{\prime}$ as in
the conclusion of the lemma.

Let $\delta=\frac{1}{6\times 17^{2}}$. A triple $x_{1}x_{2}x_{3}$ is
partitioned if $x_{i}\in X_{i}$. We remind the reader that dangerous triples
were defined in Section 9.

(48) _Under the assumptions in ( 10), if for some $i\in\\{1,2,3\\}$, some
$x_{i}\in X_{i}$ is a center of $\delta|X|^{2}$ dangerous triples, then (10)
holds._

Since $\epsilon<\frac{1}{8}\delta$, it follows from (10) and Theorem 9.1 that
there exists $S^{\prime}\subseteq D\setminus b$ with $\kappa(X)\leq 4$ such
that the component $D(b)$ of $D\setminus S^{\prime}$ with $b\in D(b)$ is
disjoint from $N(x)$ for at least $\epsilon|X|$ vertices $x\in X$. Setting
$S=S^{\prime}\cup Z^{\prime}$, (10) holds. This proves (10).

In view of (10), in order to prove (10) we may assume that for every
$i\in\\{1,2,3\\}$, every $x_{i}\in X_{i}$ is a center fewer that
$\delta|X|^{2}$ dangerous triples.

(49) _At least $\frac{1}{2}\left\lceil\frac{1}{17}|X|\right\rceil^{3}$ of the
partitioned triples are not dangerous._

Since there are $\left\lceil\frac{1}{17}|X|\right\rceil^{3}$ partitioned
triples, it is enough to prove that at most
$\left\lceil\frac{1}{17}|X|\right\rceil^{3}/2$ of the partitioned triples are
dangerous. Let $i\in\\{1,2,3\\}$. By (10), the number of dangerous triples
with center in $X_{i}$ is at most

$|X_{i}|\times\delta|X|^{2}\leq=\left\lceil\frac{1}{17}|X|\right\rceil\cdot\frac{1}{6\times
17^{2}}|X|\leq\frac{1}{6}\left\lceil\frac{1}{17}|X|\right\rceil^{3}.$

Since every dangerous triple has a center in one of the sets
$X_{1},X_{2},X_{3}$, it follows that the total number of dangerous triples is
at most

$3\times\frac{1}{6}\left\lceil\frac{1}{17}|X|\right\rceil^{3}\leq\frac{1}{2}\left\lceil\frac{1}{17}|X|\right\rceil^{3},$

as required. This proves (10).

(50) _Every partitioned triple that is not dangerous is $b$-separated._

Let $x_{1}x_{2}x_{3}$ be a partitioned triple that is not dangerous. Let
$H=D\cup\\{x_{1},x_{2},x_{3},a\\}$. Let $F$ be a minimal connected subgraph of
$D$ such that each of $x_{1},x_{2},x_{3}$ has a neighbor in $F$. Since
$X\cap\operatorname{Hub}(G)=\emptyset$, it follows from Lemma 10.2 that
$\Sigma=F\cup\\{x_{1},x_{2},x_{3},a\\}$ is a pyramid with apex $a$. For
$i\in\\{1,2,3\\}$, let $Q_{i}=a\hbox{-}x_{i}$. Since $x_{1}x_{2}x_{3}$ is not
a dangerous triple, we deduce that $a$ is not contained in a cross-edge of an
extended near-prism in $H$. Now by Theorem 4.3 applied to
$\Sigma,Q_{1},Q_{2},Q_{3},$ and $H$, it follows that the triple
$x_{1}x_{2}x_{3}$ is $b$-separated, and (10) follows.

(51) _$X$ is a $(\frac{1}{2\times 17^{3}},b)$-breaker in $G$._

By (10), at least $\frac{1}{2}\left\lceil\frac{1}{17}|X|\right\rceil^{3}$ of
the partitioned triples are not dangerous. Now by (10) at least
$\frac{1}{2}\left\lceil\frac{1}{17}|X|\right\rceil^{3}\geq\frac{1}{2\times
17^{3}}|X|^{3}$ of the partitioned triples $x_{1}x_{2}x_{3}$ are
$b$-separated, and (10) follows.

By Theorem 8.3, there exist $S^{\prime}\subseteq D\setminus b$ with
$\kappa(S)\leq C-4$ such that the component $D(b)$ of $D\setminus S$ with
$b\in D(b)$ is disjoint from $N(x)$ for at least $\epsilon|X|$ vertices $x\in
X$. Setting $S=Z^{\prime}\cup S$, (10) follows.

We complete the proof of Theorem 10.5 by induction on $|N_{G}(a)|$. If $X$ is
pure, let $X_{0}=X$. If $X$ is not pure and there does not exist
$X^{\prime}\subseteq X$ with $|X^{\prime}|\geq\frac{1-4\epsilon}{2}|X|$ such
that $X^{\prime}$ is pure, let $X_{0}=X$. If $X$ is not pure and there exists
$X^{\prime}\subseteq X$ with $|X^{\prime}|\geq\frac{1-4\epsilon}{2}|X|$ such
that $X^{\prime}$ is pure, let $X_{0}$ be a pure subset of $X$ with
$|X_{0}|\geq\frac{1-4\epsilon}{2}|X|$. Let $G_{0}=G\setminus(X\setminus
X_{0})$. Note that $X_{0}=N_{G_{0}}(a)=N_{G_{0}}(D)$. Apply (10) in $G_{0}$
(and with $X=X_{0})$. Let $S$ be as in (10). Let $D_{1}$ be the component of
$D\setminus S$ with $b\in D_{1}$, let $X_{1}=N_{G_{0}}(D_{1})$ and let
$G_{1}=D_{1}\cup X_{1}\cup\\{a\\}$. By (10)
$|N_{G_{1}}(a)|\leq(1-\epsilon)|N_{G_{0}}(a)|\leq(1-\epsilon)|X_{0}|$. Let
$G_{2}=G[V(G_{1})\cup(X\setminus X_{0})]$. Since $N_{G_{2}}(a)=(X\setminus
X_{0})\cup N_{G_{1}}(a)$, it follows that

$|N_{G_{2}}(a)|\leq(1-\epsilon)|X_{0}|+|X|-|X_{0}|\leq|X|-\epsilon|X_{0}|\leq(1-\gamma)|X|.$

If $|N_{G_{2}}(a)|\leq 1$, let $Z_{1}=N_{G_{2}}(a)$. Otherwise,
$\log|N_{G_{2}}(a)|\geq 1$ and inductively, there is a set $Z_{1}\subseteq
V(G_{2})\setminus\\{a,b\\}$ with
$\kappa(Z)\leq-C\frac{1}{\log(1-\gamma)}(\log|N_{G_{2}}(a)|)$ and such that
every component of $G_{2}\setminus Z_{1}$ contains at most one of $a,b$. In
the latter case,
$\kappa(Z_{1})\leq-C\frac{1}{\log(1-\gamma)}\log(|N_{G}(a)|)-C$. Since
$\kappa(S)\leq C$, the set $Z_{1}\cup S$ satisfies the conclusion of the
theorem. In the former case, $|Z_{1}\cup S|\leq C$ and $Z_{1}\cup S$ satisfies
this conclusion of the theorem. ∎

##  11 Stable sets of safe hubs

As we discussed in Section 3, the in the course of the proof of Theorem 13.1,
we will repeatedly decompose the graph by star cutsets arising from a stable
set of appropriately chosen hubs (using Theorem 6.5). In this section we
prepare the tools for handling one such step: one stable set of safe hubs.

Let $d$ be an integer. In this section we again set $\epsilon=\frac{1}{4\times
17^{6}\times 48\times 192}$, $\gamma=\frac{\epsilon(1-4\epsilon)}{2}$ and
$C=96^{2}\times 4\times 17^{6}+4$. Let $a,b\in V(G)$ be non-adjacent and such
that no subset $Z$ of $G$ with $\kappa(Z)\leq-C\frac{1}{\log(1-\gamma)}\log
n+d$ separates $a$ from $b$. Following [13], we say that a vertex $v$ is
$d$-safe if $|N(v)\cap\operatorname{Hub}(G)|\leq d$. As in [13], the goal of
the next lemma is to classify $d$-safe vertices into “good ones” and “bad
ones”, and show that the bad ones are rare. A vertex $v\in G$ is
$ab$-cooperative if there exists a component $D$ of $G\setminus N[v]$ such
that $a,b\in N[D]$.

######  Lemma 11.1.

If $v\in G$ is $d$-safe and not $ab$-cooperative, then $v$ is adjacent to both
$a$ and $b$. In particular, the set of vertices that are not $ab$-cooperative
is a clique.

###### Proof.

Suppose $v$ is non-adjacent to $b$ and $v$ is not $ab$-cooperative. Let $D$ be
the component of $G\setminus N[v]$ such that $b\in D$. Let
$X=N(D)\setminus\operatorname{Hub}(G)$. Let $G^{\prime}=D\cup X\cup\\{v\\}$.
Then $a\not\in G^{\prime}$. We apply Theorem 10.1 to the vertices $v,b$ in
$G^{\prime}$ to obtain a subset $Z\subseteq G^{\prime}\setminus\\{v,b\\}$ with
$\kappa(Z)\leq-C\frac{1}{\log(1-\gamma)}\log n$ and such that every component
of $G^{\prime}\setminus Z$ contains at most one of $v,b$. We claim that
$Z^{\prime}=Z\cup(N(v)\cap\operatorname{Hub}(G))$ separates $a$ from $b$ in
$G$. Suppose that $P$ is a path from $a$ to $b$ with $P^{*}\cap
Z^{\prime}=\emptyset$. Since $b\in D$ and $a\not\in D$, there is a vertex
$x\in P$ such that $b\hbox{-}P\hbox{-}x\subseteq D$ and $x\not\in D$. Then
$x\in X$. But now $b\hbox{-}P\hbox{-}x\hbox{-}v$ is a path from $b$ to $v$ in
$G^{\prime}\setminus Z$, a contradiction. This proves the claim that
$Z^{\prime}$ separates $a$ from $b$ in $G$. But
$\kappa(Z^{\prime})\leq-C\frac{1}{\log(1-\gamma)}\log n+d$, a contradiction.
This proves Lemma 11.1. ∎

Let $S^{\prime}$ be a stable set of hubs of $G$ with
$S^{\prime}\cap\\{a,b\\}=\emptyset$, and assume that every $s\in S^{\prime}$
is $d$-safe. Let $S^{\prime}_{bad}=S^{\prime}\cap N(a)\cap N(b)$. Since $G$ is
$C_{4}$-free, it follows that $|S^{\prime}_{bad}|\leq 1$. Let
$S=S^{\prime}\setminus S^{\prime}_{bad}$. By Lemma 11.1, every vertex in $S$
is $ab$-cooperative.

A separation of $G$ is a triple $(X,Y,Z)$ of pairwise disjoint subsets of $G$
with $X\cup Y\cup Z=G$ such that $X$ is anticomplete to $Z$. We are now ready
to move on to star cutsets. As in other papers on the subject, we associate a
certain unique star separation to every vertex of $S$. The choice of the
separation is the same as in [13].

Let $v\in S$. Since $v$ is $ab$-cooperative, there is a component $D$ of
$G\setminus N[v]$ with $a,b\in N[D]$. Since $v\not\in S^{\prime}_{bad}$, it
follows that $v$ is not complete to $\\{a,b\\}$; consequently
$D\cap\\{a,b\\}\neq\emptyset$, and so the component $D$ is unique. Let
$B(v)=D$, let $C(v)=N(B(v))\cup\\{v\\}$, and let $A(v)=G\setminus(B(v)\cup
C(v))$. Then $(A(v),C(v),B(v))$ is the canonical star separation of $G$
corresponding to $v$.

As in [13], we observe:

######  Lemma 11.2.

The vertex $v$ is not a hub of $G\setminus A(v)$.

###### Proof.

Suppose that $(H,v)$ is a proper wheel or a loaded pyramid in $G\setminus
A(v)$. Then $H\subseteq N[B(v)]$, contrary to Theorem 6.5. ∎

Let $\mathcal{O}$ be a linear order on $S\cap\operatorname{Hub}(G)$. Following
[4], we say that two vertices of $S\cap\operatorname{Hub}(G)$ are star twins
if $B(u)=B(v)$, $C(u)\setminus\\{u\\}=C(v)\setminus\\{v\\}$, and
$A(u)\cup\\{u\\}=A(v)\cup\\{v\\}$.

Let $\leq_{A}$ be a relation on $S\cap\operatorname{Hub}(G)$ defined as
follows:

$\hskip 71.13188ptx\leq_{A}y\ \ \ \text{ if}\ \ \ \begin{cases}x=y,\text{
or}\\\ \text{$x$ and $y$ are star twins and $\mathcal{O}(x)<\mathcal{O}(y)$,
or}\\\ \text{$x$ and $y$ are not star twins and }y\in A(x).\\\ \end{cases}$

Note that if $x\leq_{A}y$, then either $x=y$, or $y\in A(x).$

The following two results were proved in [13] with a slightly different setup:
The set of hubs is defined differently. However, the proofs do not use the
definition of the set of hubs.

######  Lemma 11.3 (Chudnovsky, Gartland, Hajebi, Lokshtanov, Spirkl [13],
Lemma 4.8).

$\leq_{A}$ is a partial order on $S\cap\operatorname{Hub}(G)$.

Let $\operatorname{Core}(S^{\prime})$ be a the set of all $\leq_{A}$-minimal
elements of $S\cap\operatorname{Hub}(G)$.

######  Lemma 11.4 (Chudnovsky, Gartland, Hajebi, Lokshtanov, Spirkl [13],
Lemma 4.9).

Let $u,v\in\operatorname{Core}(S^{\prime})$. Then $A(u)\cap C(v)=C(u)\cap
A(v)=\emptyset$.

As in [13], we define the _central bag_

$\beta^{A}(S^{\prime})=\left(\bigcap_{v\in\operatorname{Core}(S^{\prime})}(B(v)\cup
C(v))\right)\setminus S^{\prime}_{bad}.$

The next result describes important properties of $\beta^{A}(S^{\prime})$.

######  Theorem 11.5.

The following hold:

  1. 1.

For every $v\in\operatorname{Core}(S^{\prime})$, we have
$C(v)\subseteq\beta^{A}(S^{\prime})$.

  2. 2.

For every component $D$ of $G\setminus(\beta^{A}(S^{\prime})\cup
S^{\prime}_{bad})$, there exists $v\in\operatorname{Core}(S^{\prime})$ such
that $D\subseteq A(v)$. Further, if $D$ is a component of
$G\setminus(\beta^{A}(S^{\prime})\cup S^{\prime}_{bad})$ and
$v\in\operatorname{Core}(S^{\prime})$ such that $D\subseteq A(v)$, then
$N(D)\subseteq C(v)\cup S^{\prime}_{bad}$.

  3. 3.

$S^{\prime}\cap\operatorname{Hub}(\beta^{A}(S^{\prime}))=\emptyset$.

###### Proof.

(1) is immediate from Lemma 11.4.

Next we prove (2). Let $D$ be a component of
$G\setminus(\beta^{A}(S^{\prime})\cup S^{\prime}_{bad})$. Since
$G\setminus(\beta^{A}(S^{\prime})\cup
S^{\prime}_{bad})=\bigcup_{v\in\operatorname{Core}(S^{\prime})}A(v)$, there
exists $v\in\operatorname{Core}(S^{\prime})$ such that $D\cap
A(v)\neq\emptyset$. If $D\setminus A(v)\neq\emptyset$, then, since $D$ is
connected, it follows that $D\cap N(A(v))\neq\emptyset$; but then $D\cap
C(v)\neq\emptyset$, contrary to (1). Since
$N(D)\subseteq\beta^{A}(S^{\prime})\cup S^{\prime}_{bad}$ and $N(D)\subseteq
A(v)\cup C(v)\cup S^{\prime}_{bad}$, it follows that $N(D)\subseteq C(v)\cup
S^{\prime}_{bad}$. This proves (2).

To prove (3), let $u\in
S^{\prime}\cap\operatorname{Hub}(\beta^{A}(S^{\prime}))$. Since
$\beta^{A}(S^{\prime})\cap S^{\prime}_{bad}=\emptyset$, we deduce that
$u\not\in S^{\prime}_{bad}$, and so $u\in S\cap\operatorname{Hub}(G)$. By
Lemma 11.2, it follows that $\beta^{A}(S^{\prime})\not\subseteq B(u)\cup
C(u)$, and therefore $u\not\in\operatorname{Core}(S^{\prime})$. But then $u\in
A(v)$ for some $v\in\operatorname{Core}(S^{\prime})$, and so
$u\not\in\beta^{A}(S^{\prime})$, a contradiction. This proves (3) and
completes the proof of Theorem 11.5. ∎

In the course of the proof of Theorem 13.1, we will inductively obtain a small
cutset separating $a$ from $b$ in $\beta^{A}(S^{\prime})$, using that the
vertices in $S^{\prime}$ are not hubs in $\beta^{A}(S^{\prime})$. The next
theorem lets us lift this cutset into a cutest that separates $a$ from $b$ in
$G$.

######  Theorem 11.6.

Let $(X,Y,Z)$ be a separation of $\beta^{A}(S^{\prime})$ such that $a\in X$
and $b\in Z$. Then there exists a set $Y^{\prime}\subseteq V(G)$ such that

  1. 1.

$Y^{\prime}$ separates $a$ from $b$ in $G$, and

  2. 2.

$\kappa(Y^{\prime})\leq\kappa(Y)+|Y\cap\operatorname{Core}(S^{\prime})|(-C\frac{1}{\log(1-\gamma)}\log
n+d)+1$.

###### Proof.

Let $s\in Y\cap\operatorname{Core}(S^{\prime})$. Let
$X=C(s)\setminus\operatorname{Hub}(G)$. Let $G^{\prime}=B(s)\cup
X\cup\\{s\\}$. Suppose first that $s$ is non-adjacent to $b$. We apply Theorem
10.1 to the vertices $s,b$ in $G^{\prime}$ to obtain a subset $Z(s)\subseteq
G^{\prime}\setminus\\{s,b\\}$ with
$\kappa(Z)\leq-C\frac{1}{\log(1-\gamma)}\log n$ and such that every component
of $G^{\prime}\setminus Z(s)$ contains at most one of $s,b$. Now suppose that
$s$ is adjacent to $b$. Since $s$ is cooperative, it follows that $s$ is non-
adjacent to $a$. Now we apply Theorem 10.1 to the vertices $s,a$ in
$G^{\prime}$ to obtain a subset $Z(s)\subseteq G^{\prime}\setminus\\{s,a\\}$
with $\kappa(Z(s))\leq-C\frac{1}{\log(1-\gamma)}\log n$ and such that every
component of $G^{\prime}\setminus Z(s)$ contains at most one of $s,a$. We
deduce:

(52) _For every $s\in\operatorname{Core}(S^{\prime})$, $Z(s)$ separates $s$
from at least one of $a,b$._

Now let

$Y^{\prime}=Y\cup\bigcup_{s\in
Y\cap\operatorname{Core}(S^{\prime})}Z(s)\cup\bigcup_{s\in
Y\cap\operatorname{Core}(S^{\prime})}(N(s)\cap\operatorname{Hub}(G))\cup
S^{\prime}_{bad}.$

Since every vertex of $S^{\prime}$ is safe, we have that
$\kappa(Y^{\prime})\leq\kappa(Y)+|Y\cap\operatorname{Core}(S^{\prime})|(-C\frac{1}{\log(1-\gamma)}\log
n+d)$.

We show that $Y^{\prime}$ separates $a$ from $b$ in $G$. Suppose not. Let
$D_{b}$ be the component of $\beta^{A}(S^{\prime})\setminus Y$ such that $b\in
D_{b}$, an let $D_{a}$ be the component of $\beta^{A}(S^{\prime})\setminus Y$
such that $a\in D_{a}$. Let $D_{b}^{\prime}=D_{b}\cup\bigcup_{s\in
D_{b}\cap\operatorname{Core}(S^{\prime})}A(s)$, and let
$D_{a}^{\prime}=D_{a}\cup\bigcup_{s\in
D_{a}\cap\operatorname{Core}(S^{\prime})}A(s)$. Let $P$ be a path from $b$ to
$a$ in $G\setminus Y^{\prime}$. Since $b\in D_{b}^{\prime}$ and $a\not\in
D_{b}^{\prime}$, there is $x\in P$ such that $b\hbox{-}P\hbox{-}x\subseteq
D_{b}^{\prime}$ and the neighbor $y$ of $x$ in the path $x\hbox{-}P\hbox{-}a$
does not belong to $D_{b}^{\prime}$. Since for every $s\in
D_{b}\cap\operatorname{Core}(S^{\prime})$,
$N_{G}(A(s))\cap\beta^{A}(S^{\prime})\subseteq C(s)\subseteq D_{b}\cup Y$, and
since $Y\subseteq Y^{\prime}$, it follows that
$y\not\in\beta^{A}(S^{\prime})$. Let $D^{\prime}$ be the component of
$G\setminus(\beta^{A}(S^{\prime})\cup S^{\prime}_{bad})$ such that $y\in
D^{\prime}$. By Theorem 11.5(2) there is an
$s\in\operatorname{Core}(S^{\prime})$ such that $D^{\prime}\subseteq A(s)$ and
$N(D^{\prime})\subseteq C\cup S^{\prime}_{bad}$; consequently by Theorem
11.5(1), $N(D^{\prime})\subseteq N_{\beta^{A}(S^{\prime})}(s)\cup
S^{\prime}_{bad}$. In particular, $x\in N_{\beta^{A}(S^{\prime})}(s)$. Since
$y\not\in D^{\prime}_{b}$, it follows that $s\not\in D_{b}$. Since
$N_{\beta^{A}(S^{\prime})}(s)\cap D_{b}\neq\emptyset$ and $s\not\in D_{b}$, it
follows that $s\in Y$. Consequently, $P\cap Z(s)=\emptyset$. Since $y\in A(s)$
and $a\in\beta^{A}(S^{\prime})\subseteq B(s)\cup C(s)$, there exists
$x^{\prime}\in y\hbox{-}P\hbox{-}a$ such that $x^{\prime}\in C(s)$ and $s$ has
no other neighbors in the path $x^{\prime}\hbox{-}P\hbox{-}a$. Now
$b\hbox{-}P\hbox{-}x\hbox{-}s$ and $a\hbox{-}P\hbox{-}x^{\prime}\hbox{-}s$ are
paths from $b$ to $s$ and from $a$ to $s$, respectively, and both are disjoint
from $Z(s)$, contrary to (11). ∎

##  12 Bounding the number of non-hubs

For $X\subseteq V(G)$, a component $D$ of $G\setminus X$ is full for $X$ if
$N(D)=X$. $X\subseteq V(G)$ is a minimal separator in $G$ if there exist two
distinct full components for $X$. In this section we again set
$\epsilon=\frac{1}{4\times 17^{6}\times 48\times 192}$,
$\gamma=\frac{\epsilon(1-4\epsilon)}{2}$ and $C=96^{2}\times 4\times
17^{6}+4$, and let $D=-C\frac{1}{\log(1-\gamma)}$. Let $a,b\in V(G)$ be non-
adjacent. The goal of this section is to start with a minimal separator in $G$
separating $a$ from $b$, and turn it into a separator that interfaces well
with Theorem 11.6. Let $d$ be an integer and let $S_{1}\subseteq
V(G)\setminus\operatorname{Hub}(G)$ be a stable set of $d$-safe vertices. For
a set $U\subseteq V(G)$ we denote by $\mu_{d}(U)$ the set $U\cap S_{1}$. We
will prove the following:

######  Theorem 12.1.

Let $d$ be an integer. Let $G$ be an even-hole-free graph and let $a,b\in
V(G)$ be non-adjacent. Let $|V(G)|=n$. Let $Y$ be a minimal separator in $G$
such that $a$ and $b$ belong to different components of $G\setminus Y$. Then
there exists a set $Y^{\prime}\subseteq V(G)\setminus\\{a,b\\}$ such that

  * •

$Y^{\prime}$ separates $a$ from $b$;

  * •

$|\kappa(Y^{\prime}\setminus Y)|\leq D(D\log n+d)\log n$; and

  * •

$|\mu_{d}(Y^{\prime})|\leq D(D\log n+d)\log n$.

The main ingredient of the proof is the following:

######  Lemma 12.2.

Let $d$ be an integer and let $G$ be an even-hole-free graph where
$G=D_{1}\cup D_{2}\cup X$, $X$ is a minimal separator in $G$, and
$D_{1},D_{2}$ are full components for $X$. Let $a\in D_{1}$ and $b\in D_{2}$.
Assume that $X$ is a stable set, $X\cap\operatorname{Hub}(G)=\emptyset$, and
that every vertex of $X$ is $d$-safe. Then there exists $Z\subseteq
V(G)\setminus\\{a,b\\}$ with $\kappa(Z)\leq D\log n+d$ such that either

  * •

the component $D(b)$ of $D_{2}\setminus Z$ with $b\in D(b)$ contains a
neighbor of $x$ for at most $(1-\epsilon)|X|$ vertices $x\in X\setminus Z$, or

  * •

the component $D(a)$ of $D_{1}\setminus Z$ with $a\in D(a)$ contains a
neighbor of $x$ for at most $(1-\epsilon)|X|$ vertices $x\in X\setminus Z$.

###### Proof.

We may assume that $|X|>D\log n+d$.

(53) _If some $v\in D_{1}$ has $\epsilon|X|$ neighbors in $X$, then the
theorem holds._

Suppose such $v$ exists. Let $G^{\prime}=D_{2}\cup N_{G}[v]$. Apply Theorem
10.1 to $v,b$ in $G^{\prime}$ (where $v$ plays the role of $a$) to obtain a
set $Z$ as in the conclusion of the theorem. Let $D(b)$ be the component of
$D_{2}\setminus Z$ with $b\in D(b)$. Then $N_{G^{\prime}}[v]\setminus Z$ is
anticomplete to $D(b)$ in $G^{\prime}$ and therefore in $G$. Since
$|N_{G^{\prime}}(v)|\geq\epsilon|X|$, (12) follows.

In view of (12) (using the symmetry between $a$ and $b$) from now on we assume
that no $v\in D_{1}\cup D_{2}$ has $\epsilon|X|$ neighbors in $X$.

(54) _If for some $x\in X\setminus N(a)$ at least $\epsilon|X|$ vertices of
$X$ are anticomplete to the component $D(a)$ of $D_{1}\setminus N(x)$ with
$a\in D(a)$, then the theorem holds._

Suppose that such a vertex $x$ exists. Let $D^{\prime}=D(a)$, let
$X^{\prime}=(N(x)\cap N(D(a))\setminus\operatorname{Hub}(G)$ and let
$G^{\prime}=D^{\prime}\cup X^{\prime}\cup\\{x\\}$. Apply Theorem 10.1 to $x,a$
in $G^{\prime}$ (where $x$ plays the role of $a$, and $a$ plays the role of
$b$) to obtain a set $Z$ as in the conclusion of the theorem. Let
$Z^{\prime}=Z\cup(N(x)\cap\operatorname{Hub}(G))$. Since $x$ is $d$-safe, it
follows that $\kappa(Z^{\prime})\leq D\log n+d$. Let $D^{\prime}(a)$ be the
component of $D_{1}\setminus Z^{\prime}$ with $a\in D^{\prime}(a)$. Since $Z$
separates $x$ from $a$ in $G^{\prime}$, it follows that $N[x]\setminus
Z^{\prime}$ is anticomplete to $D(a)\setminus Z^{\prime}$, and therefore
$D^{\prime}(a)\subseteq D(a)$.

Consequently, if $x^{\prime}\in X$ is anticomplete to $D(a)$, then
$x^{\prime}$ is anticomplete to $D^{\prime}(a)$. Since least $\epsilon|X|$
vertices of $X$ are anticomplete to $D(a)$, (12) follows.

In view of (12), from now on we assume that for every $x\in X\setminus N(a)$
fewer than $\epsilon|X|$ vertices of $X$ are anticomplete to the component
$D(a)$ of $D_{1}\setminus N(x)$ with $a\in D(a)$, and for every $x\in
X\setminus N(b)$ fewer than $\epsilon|X|$ vertices of $X$ are anticomplete to
the component $D(b)$ of $D_{2}\setminus N(x)$ with $b\in D(b)$. Let
$X^{\prime}=X\setminus(N(a)\cup N(b))$. Then
$|X^{\prime}|\geq(1-2\epsilon)|X|$. Since $X$ is a stable set, we can choose
disjoint and anticomplete subsets $X_{1},X_{2},X_{3}$ of $X^{\prime}$ such
that $|X_{1}|=|X_{2}|=|X_{3}|=\left\lceil\frac{1}{4}|X|\right\rceil$.

Let us say that a partitioned triple $x_{1}x_{2}x_{3}$ is $b$-triangular if
there is a minimal connected subgraph $H$ of $D_{2}$ containing neighbors of
$x_{1},x_{2},x_{3}$ such that either

  * •

$H$ satisfies the third outcome to Lemma 10.2, or

  * •

(possibly with the roles of $x_{1},x_{2},x_{3}$ exchanged) $H$ is the interior
of a path from $x_{1}$ to $x_{3}$, and $x_{2}$ has exactly two neighbors in
$H$ and they are adjacent.

We define $a$-triangular triples similarly.

(55) _Every partitioned triple is either $a$-triangular or $b$-triangular._

Let $x_{1}x_{2}x_{3}$ be a partitioned triple, and suppose that it is neither
$b$-triangular nor $a$-triangular. For $i\in\\{1,2\\}$, let $H_{i}$ be a
minimal connected induced subgraph of $D_{i}$ such that each of
$x_{1},x_{2},x_{3}$ has a neighbor in $H_{i}$. We apply Lemma 10.2 to $H_{1}$
and $H_{2}$. If the second outcome of the lemma holds for both $H_{1}$ and
$H_{2}$, then $H_{1}\cup H_{2}\cup\\{x_{1},x_{2},x_{3}\\}$ is a theta, a
contradiction. Thus we may assume that $H_{1}$ is the interior of a path from
$x_{1}$ to $x_{3}$ and $x_{2}$ has at least two non-adjacent neighbors in
$H_{1}$. If $H_{2}$ is the interior of a path from $x_{1}$ to $x_{3}$ and
$x_{2}$ has a neighbor in $H_{2}$, then $(H_{1}\cup H_{2},x_{2})$ is a wheel
in $G$, contrary to the fact that $x_{2}\not\in\operatorname{Hub}(G)$. Thus
$H_{2}$ is not the interior of a path from $x_{1}$ to $x_{3}$ such that
$x_{2}$ has a neighbor in $H_{2}$. Next suppose that the second outcome of
Lemma 10.2 holds for $H_{2}$. Let $P_{1},P_{2},P_{3}$ be as in the the second
outcome of Lemma 10.2, and let $a_{2}=P_{1}\cap P_{2}\cap P_{3}$. Then $x_{2}$
is non-adjacent to $a_{2}$, and so $H_{1}\cup
H_{2}\cup\\{x_{1},x_{2},x_{3}\\}$ contains a theta with ends $a_{2},x_{2}$, a
contradiction. It follows that the first outcome of Lemma 10.2 holds for
$H_{2}$, and, by symmetry between $x_{1}$ and $x_{3}$, we may assume that
$H_{2}$ is the interior of a path from $x_{1}$ to $x_{2}$, and $x_{3}$ has two
non-adjacent neighbors in $H_{2}$. Now we get a theta with ends $x_{2},x_{3}$
and paths $x_{2}\hbox{-}H_{1}\hbox{-}x_{3}$,
$x_{2}\hbox{-}H_{2}\hbox{-}x_{3}$, and
$x_{2}\hbox{-}H_{1}\hbox{-}x_{1}\hbox{-}H_{2}\hbox{-}x_{3}$, again a
contradiction. This proves (12).

In view of (12), by switching the roles of $D_{1}$ and $D_{2}$ if necessary,
we may assume that at least
$\frac{1}{2}\left\lceil\frac{1}{4}|X|\right\rceil^{3}$ of the partitioned
triples are $b$-triangular.

Let us say that the triple $x_{1}x_{2}x_{3}$ is acceptable if it is
partitioned and for every $\\{i,j,k\\}=\\{1,2,3\\}$ there is path $P_{ij}$
from $x_{i}$ to $x_{j}$ with interior in $D_{1}\setminus N(x_{k})$.

(56) _At most $6\epsilon\left\lceil\frac{1}{4}|X|\right\rceil^{2}|X|$
partitioned triples are not acceptable._

Let $x_{1}\in X_{1}$ and let $D(a)$ be the component of $D_{1}\setminus
N(x_{1})$ such that $a\in D(a)$. If $x_{1}x_{2}x_{3}$ is a partitioned triple
such that there is no path from $x_{2}$ to $x_{3}$ in $D_{1}\setminus
N(x_{1})$, then at least one of $x_{2},x_{3}$ is anticomplete to $D(a)$. By
the assumption following (12), there are fewer than
$2\epsilon|X|\times\left\lceil\frac{1}{4}|X|\right\rceil$ such pairs
$x_{2}x_{3}$, and therefore at most

$\left(2\epsilon|X|\times\left\lceil\frac{1}{4}|X|\right\rceil\right)\times\left\lceil\frac{1}{4}|X|\right\rceil\leq
2\epsilon\left\lceil\frac{1}{4}|X|\right\rceil^{2}|X|$

such triples. Repeating this argument with $x_{2}$ and $x_{3}$ playing the
role of $x_{1}$, we get that there are at most
$6\epsilon\left\lceil\frac{1}{4}|X|\right\rceil^{2}|X|$ partitioned triples
that are not acceptable, and (12) follows.

Let $G^{\prime}=D_{2}\cup X$. Our next goal is to show the following:

(57) _$X$ is a $(\frac{1}{256},b)$-breaker in $G^{\prime}$._

By (12), there are fewer than
$6\epsilon\left\lceil\frac{1}{4}|X|\right\rceil^{2}|X|$ partitioned triples
that are not acceptable. Since the total number of $b$-triangular triples at
least $\frac{1}{2}\left\lceil\frac{1}{4}|X|\right\rceil^{3}$, we deduce that
there are at least
$\left(\frac{1}{2}-24\epsilon\right)\left\lceil\frac{1}{4}|X|\right\rceil^{3}$
triples that are both acceptable and $b$-triangular.

Let $x_{1}x_{2}x_{3}$ be a $b$-triangular acceptable triple. Let $H$ be a
minimal connected subgraph of $D_{2}$ as in the definition of $b$-triangular.
Then there exists a triangle $h_{1}h_{2}h_{3}$ in
$H\cup\\{x_{1},x_{2},x_{3}\\}$ and three paths $P_{1},P_{2},P_{3}$, where
$P_{i}$ is a path from $h_{i}$ to $x_{i}$ (possibly of length zero), such
that:

  * •

$V(H)=(V(P_{1})\cup V(P_{2})\cup V(P_{3}))\setminus\\{x_{1},x_{2},x_{3}\\}$;

  * •

the sets $V(P_{1})$, $V(P_{2})$ and $V(P_{3})$ are pairwise disjoint; and

  * •

for distinct $i,j\in\\{1,2,3\\}$, there are no edges between $V(P_{i})$ and
$V(P_{j})$, except $h_{i}h_{j}$.

If the path $P_{i}$ has even length, let $q_{i}=2$, and if the path $P_{i}$
has odd length, let $q_{i}=3$. Let $G^{\prime\prime}$ be the graph obtained
from $D_{2}\cup\\{x_{1},x_{2},x_{3}\\}$ by adding a new vertex $v$ and paths
$Q_{i}$ from $v$ to $x_{i}$ such that

  * •

$Q_{i}$ has length $q_{i}$.

  * •

$(Q_{1}\cup Q_{2}\cup Q_{3})\setminus\\{x_{1},x_{2},x_{3}\\}$ is anticomplete
to $D_{2}$.

  * •

$Q_{1}\setminus v$, $Q_{2}\setminus v$ , $Q_{3}\setminus v$ are pairwise
disjoint and anticomplete to each other.

(58) _$G^{\prime\prime}$ is even-hole-free._

Suppose not, and let $H$ be an even hole in $G^{\prime\prime}$. Since $H$ is
not an even hole in $G$, and since all internal vertices of each $Q_{i}$ have
degree two, we may assume that $Q_{1}\cup Q_{2}\subseteq H$. Then
$H\setminus(Q_{1}^{*}\cup Q_{2}^{*})$ is a path from $x_{1}$ to $x_{2}$ with
interior in $D_{2}\cup\\{x_{3}\\}$ and whose length has the same parity as
$q_{1}+q_{2}$. Since the triple $x_{1}x_{2}x_{3}$ is acceptable, there is a
path $R$ from $x_{1}$ to $x_{2}$ with $R^{*}\subseteq D_{1}\setminus
N(x_{3})$. Since $(H\setminus(Q_{1}\cup Q_{2}))\cup R$ is not an even hole in
$G$, it follows that the length of $R$ has the same parity as $q_{1}+q_{2}+1$.
But now
$x_{1}\hbox{-}P_{1}\hbox{-}h_{1}\hbox{-}h_{2}\hbox{-}P_{2}\hbox{-}x_{2}\hbox{-}R\hbox{-}x_{1}$
is an even hole in $G$, a contradiction. This proves (12).

By (12) and since $X\cap\operatorname{Hub}(G)=\emptyset$, the assumptions of
Theorem 4.3 are satisfied. Now Theorem 4.3 applied in $G^{\prime\prime}$
implies that the triple $x_{1}x_{2}x_{3}$ is $b$-separated in $G^{\prime}$.

Since there are at least
$\left(\frac{1}{2}-24\epsilon\right)\left\lceil\frac{1}{4}|X|\right\rceil^{3}$
acceptable $b$-triangular triples, and since $\epsilon\leq 1/96$, (12)
follows.

By Theorem 8.3 applied in $G^{\prime}$, there exists $Z\subseteq
D_{2}\setminus b$ with $\kappa(Z)\leq 96^{2}\cdot 256^{2}\leq C-4$ such the
component $D(b)$ of $D\setminus S$ with $b\in D(b)$ is disjoint from $N(x)$
for at least $\epsilon|X|$ vertices $x\in X$. This completes the proof. ∎

Next we prove the following, which immediately implies Theorem 12.1.

######  Theorem 12.3.

Let $d$ be an integer. Let $G$ be an even-hole-free graph and let $a,b\in
V(G)$ be non-adjacent. Let $|V(G)=n$. Let $Y$ be a minimal separator in $G$
such that $a$ and $b$ belong to different full components $D_{1}$ and $D_{2}$
of $G\setminus Y$. Assume that $\mu_{d}(Y)\neq\emptyset$. Then there exists a
set $Y^{\prime}\subseteq V(G)\setminus\\{a,b\\}$ such that

  * •

$Y^{\prime}$ separates $a$ from $b$;

  * •

$\kappa(Y^{\prime}\setminus Y)\leq D(D\log n+d)\max(1,\log|\mu_{d}(Y)|)$; and

  * •

$|\mu_{d}(Y^{\prime})|\leq D(D\log n+d)\max(1,\log|\mu_{d}(Y)|)$.

###### Proof.

We may assume that $|\mu_{d}(Y)|\geq D(D\log n+d)$. By Lemma 12.2 applied to
the graph $D_{1}\cup D_{2}\cup\mu_{d}(Y)$ with $X=\mu_{d}(Y)$, we may assume
that there exists $Z\subseteq V(G)\setminus\\{a,b\\}$ with $\kappa(Z)\leq
D\log n+d$ such that the component $D(b)$ of $D_{2}\setminus Z$ with $b\in
D(b)$ meets $N(x)$ for at most $(1-\epsilon)|X|$ vertices $x\in X\setminus Z$.
Let $G^{\prime}=G\setminus Z$. Let $Y_{1}=N_{G^{\prime}}(D(b))$. Then
$Y_{1}\subseteq Y\setminus Z$, and $\mu_{d}(Y_{1})\subseteq X\setminus Z$;
consequently $|\mu_{d}(Y_{1})|\leq(1-\epsilon)\mu_{d}(Y)$. Let $D(a)$ be the
component of $G^{\prime}\setminus Y_{1}$ such that $a\in D(a)$. Let
$Y_{2}=N_{G^{\prime}}(D(a))$. Then $Y_{2}\subseteq Y_{1}$, and therefore
$|\mu_{d}(Y_{2})|\leq(1-\epsilon)|\mu_{d}(Y)|$. Let $G^{\prime\prime}=D(a)\cup
D(b)\cup Y_{2}$. Then $Y_{2}$ is a minimal separator in $G^{\prime\prime}$
where $D(a)$ and $D(b)$ are full components for $Y_{2}$. If $|Y_{2}|\leq 1$,
let $Y^{\prime\prime}=Y_{2}$. Now assume that $|Y_{2}|>1$. Inductively, there
is a set $Y^{\prime\prime}\subseteq V(G^{\prime\prime})\setminus\\{a,b\\}$
such that

  * •

$Y^{\prime\prime}$ separates $a$ from $b$;

  * •

$|\kappa(Y^{\prime\prime}\setminus Y_{2})|\leq D(D\log
n+d)\log|\mu_{d}(Y_{2})|$; and

  * •

$|\mu_{d}(Y^{\prime\prime})|\leq D(D\log n+d)\log|\mu_{d}(Y_{2})|$

In both cases, let $Y^{\prime}=Y^{\prime\prime}\cup Z$. Then
$Y^{\prime}\setminus Y\subseteq(Y^{\prime\prime}\setminus Y_{2})\cup Z$ and
$\mu_{d}(Y^{\prime})\subseteq\mu_{d}(Y^{\prime\prime})\cup Z$. Since
$|\mu_{d}(Y_{2})|\leq(1-\epsilon)|\mu_{d}(Y)|$ and $\kappa(Z)\leq D\log n+d$,
it follows that $|Y^{\prime}|$ satisfies the conclusion of the theorem. ∎

##  13 Separating a pair of vertices: a bound using clique size

We can now prove our first main result. We follow the outline of the proof of
Theorem 1.3 from [3], using bounds from earlier sections of the present paper.
As in the earlier sections, let $\epsilon=\frac{1}{4\times 17^{6}\times
48\times 192}$, $\gamma=\frac{\epsilon(1-4\epsilon)}{2}$ and $C=96^{2}\times
4\times 17^{6}+4$, and let $D=-C\frac{1}{\log(1-\gamma)}$.

######  Theorem 13.1.

Let $t$ be an integer. Let $G$ be an even-hole-free graph with $|V(G)|=n$ and
with no clique of size $t+1$, and let $a,b\in V(G)$ be non-adjacent. Then
there is a set $Z\subseteq V(G)\setminus\\{a,b\\}$ with

$\kappa(Z)\leq D\log n+2D(D\log n+8t)^{2}2t\log^{2}n$

and such that every component of $G\setminus Z$ contains at most one of $a,b$.

We will need the main result of [17].

######  Theorem 13.2 (Chudnovsky, Seymour [17]).

Every even-hole-free graph has a vertex $v$ such that $\kappa(N(v))\leq 2$.

Following the proof of Theorem 7.1 of [6], using Theorem 13.2 we deduce:

######  Theorem 13.3.

Let $t\in\mathbb{N}$, and let $G$ be an even-hole-free graph with no clique of
size $t+1$ and with $|V(G)|=n$. There exist a partition $(S_{1},\dots,S_{k})$
of $V(G)$ with the following properties:

  1. 1.

$k\leq 2t\log n$.

  2. 2.

$S_{i}$ is a stable set for every $i\in\\{1,\dots,k\\}$.

  3. 3.

For every $i\in\\{1,\dots,k\\}$ and $v\in S_{i}$ we have
$\deg_{G\setminus\bigcup_{j<i}S_{j}}(v)\leq 8t$.

For the remainder of this section, let us fix $t\in\mathbb{N}$. Let $G$ an
even-hole-free graph with no clique of size $t+1$, and let $a,b\in V(G)$. A
hub-partition with respect to $ab$ of $G$ is a partition $S_{1},\dots,S_{k}$
of $\operatorname{Hub}(G)\setminus\\{a,b\\}$ as in Theorem 13.3; we call $k$
the order of the partition. We call the hub-dimension of $(G,ab)$ (denoting it
by $\operatorname{hdim}(G,ab)$) the smallest $k$ such that $G$ has a hub-
partition of order $k$ with respect to $ab$.

Since, in view of Theorem 13.3, we have $\operatorname{hdim}(G,ab)\leq 2t\log
n$ for every $a,b\in V(G)$, Theorem 13.1 follows immediately from the next
result:

######  Theorem 13.4.

Let $G$ be an even-hole-free graph with $|V(G)|=n$ and with no clique of size
$t+1$, and let $a,b\in V(G)$ be non-adjacent. Then there is a set $Z\subseteq
V(G)\setminus\\{a,b\\}$ with

$\kappa(Z)\leq D\log n+2D(D\log n+8t)^{2}\operatorname{hdim}(G,ab)\log n$

and such that every component of $G\setminus Z$ contains at most one of $a,b$.

###### Proof.

Let $a,b\in G$ be non-adjacent and suppose that no such set $Z$ exists. We
will get a contradiction by induction on $\operatorname{hdim}(G,ab)$. Suppose
that $\operatorname{hdim}(G,ab)=0$. Then
$\operatorname{Hub}(G)\subseteq\\{a,b\\}$ and by Theorem 10.1, there is a set
$Z\subseteq V(G)\setminus\\{a,b\\}$ with $\kappa(Z)\leq D\log n$ and such that
every component of $G\setminus Z$ contains at most one of $a,b$. Thus we may
assume $\operatorname{hdim}(G,ab)>0$.

Let $S_{1},\dots,S_{k}$ be a hub-partition of $G$ with respect to $ab$ and
with $k=\operatorname{hdim}(G,ab)$. We now use notation and terminology from
Section 11. Write $d=8t$. It follows from the definition of $S_{1}$ that every
vertex in $S_{1}$ is $d$-safe. Let $\beta^{A}(S_{1})$ be as in Section 11;
then $a,b\in\beta^{A}(S_{1})$. By Theorem 11.5(3), we have that
$S_{1}\cap\operatorname{Hub}(\beta^{A}(S_{1}))=\emptyset$ and
$S_{2}\cap\operatorname{Hub}(\beta^{A}(S_{1})),\dots,S_{k}\cap\operatorname{Hub}(\beta^{A}(S_{1}))$
is a hub-partition of $\beta^{A}(S_{1})$ with respect to $ab$. It follows that
$\operatorname{hdim}(\beta^{A}(S_{1}),ab)\leq k-1$. Inductively there exists a
set $Y_{1}\subseteq\beta^{A}(S_{1})\setminus\\{a,b\\}$ with

$\kappa(Y_{1})\leq D\log n+2D(D\log n+d)^{2}(k-1)\log n$

and such that every component of $\beta^{A}(S_{1})\setminus Y_{1}$ contains at
most one of $a,b$. Let $D(b)$ be the component of $G\setminus Y_{1}$ such that
$b\in D$, and let $D(a)$ be the component of $\beta^{A}(S_{1})\setminus
N(D(b))$ with $a\in D(a)$. Write $N_{\beta^{A}(S_{1})}(D(a))=Y_{2}$. Then
$Y_{2}\subseteq Y_{1}$ and $Y_{2}$ is a minimal separator in
$\beta^{A}(S_{1})$ where $D(a)$ and the component of
$\beta^{A}(S_{1})\setminus Y_{2}$ containing $D(b)$ are two distinct full
components for $Y_{2}$. By Theorem 12.1 applied in $\beta^{A}(S_{1})$ and
using $S_{1}$ to define $\mu_{d}(Y_{2})$, there exists a set
$Y\subseteq\beta^{A}(S_{1})\setminus\\{a,b\\}$ such that

  * •

$Y$ separates $a$ from $b$ in $\beta^{A}(S_{1})$, and

  * •

$|\kappa(Y\setminus Y_{2})|\leq D(D\log n+d)\log n$, and

  * •

$|\mu_{d}(Y)|\leq D(D\log n+d)\log n$.

It follows that

$\displaystyle\kappa(Y)$ $\displaystyle\leq D\log n+2D(D\log n+d)^{2}(k-1)\log
n+D(D\log n+d)\log n$ $\displaystyle\leq D(\log n)(1+2(D\log
n+d)^{2}(k-1)+D\log n+d).$

Since $\operatorname{Core}(S_{1})\cap Y\subseteq\mu_{d}(Y)$, we deduce that
$|\operatorname{Core}(S_{1})\cap Y|\leq D(D\log n+d)\log n$. Now applying
Theorem 11.6 to $Y$ we obtain a set $Y^{\prime}$ such that

  * •

$Y^{\prime}$ separates $a$ from $b$ in $G$; and

  * •

$\kappa(Y^{\prime})\leq\kappa(Y)+|Y\cap\operatorname{Core}(S^{\prime})|(D\log
n+d)+1$.

Consequently,

$\displaystyle\kappa(Y^{\prime})$
$\displaystyle\leq\kappa(Y)+|Y\cap\operatorname{Core}(S^{\prime})|(D\log
n+d)+1$ $\displaystyle\leq D(\log n)(1+2(D\log n+d)^{2}(k-1)+D\log
n+d)+|Y\cap\operatorname{Core}(S^{\prime})|(D\log n+d)+1$ $\displaystyle\leq
D(\log n)(1+2(D\log n+d)^{2}(k-1/2)+D\log n+d)+1$ $\displaystyle\leq D(\log
n)(1+2(D\log n+d)^{2}k).$

as required. ∎

##  14 The proof of Theorem 3.1

We can finally prove Theorem 3.1. We will need a theorem from [37].

######  Theorem 14.1 (Korchemna, Lokshtanov, Saurabh, Surianarayanan, Xue
[37]).

Let $G$ be a graph with $|V(G)|=n$, $A,B\subseteq V(G)$, $\mathcal{F}$ a
family of cliques of $G$, and $f$ an integer. Then one of the following holds:

  * •

There exists $S\subseteq V(G)$ such that $S$ separates $A$ from $B$ and
$\kappa(S)\leq f\log^{2}n$.

  * •

There exist an integer $t\leq 2\log(|\mathcal{F}|)$ and $t\times f$ paths
$P_{1},\dots,P_{t\times f}$ from $A$ to $B$ such that for every
$K\in\mathcal{F}$, $K\cap P_{i}\neq\emptyset$ for fewer than $4t$ values of
$i$.

We also need the following result of [9] and [30]:

######  Theorem 14.2 (Alekseev [9], Farber [30]).

An $n$-vertex $C_{4}$-free graphs has at most $n^{2}$ maximal cliques.

We now prove Theorem 3.1.

###### Proof.

Let $D$ be as in Section 12 and let $c=16\times 256D^{3}$. Let $a,b\in G$ and
let $G^{\prime}=G\setminus\\{a,b\\}$. Let $A=N_{G}(a)$ and $B=N_{G}(b)$. Let
$\mathcal{F}$ be the set of all maximal cliques in $G^{\prime}$. By Theorem
14.2, we have $|\mathcal{F}|\leq n^{2}$. Let $f=c\log^{6}n$. We apply Theorem
14.1 to $G^{\prime},A,B,\mathcal{F}$ and $f$. We may assume that the statement
of the first bullet does not hold, and so there exists an integer $t\leq
2\log(|\mathcal{F}|)$ and $t\times f$ paths $P_{1},\dots,P_{t\times f}$ from
$A$ to $B$ such that for every $K\in\mathcal{F}$, $K\cap P_{i}\neq\emptyset$
for at most $4t$ values of $i$. We may assume that the paths
$P_{1},\dots,P_{t\times f}$ are induced. Let
$G^{\prime\prime}=\bigcup_{i=1}^{t\times f}P_{i}\cup\\{a,b\\}$. Since every
clique of $G^{\prime\prime}\setminus\\{a,b\\}$ is contained in an element of
$\mathcal{F}$, we deduce that $G^{\prime\prime}$ does not have a clique of
size $8t+1\leq 1+16\log n$. By Theorem 13.1 there exists a set $Z\subseteq
V(G^{\prime\prime})\setminus\\{a,b\\}$ with

$\displaystyle\kappa(Z)$ $\displaystyle\leq D\log n+2D(D\log n+8\times 16\log
n)^{2}2\times 16\log n\log^{2}n$ $\displaystyle<256D^{3}\log^{5}n.$

and such that every component of $G\setminus Z$ contains at most one of $a,b$.
Since for every $K\in\mathcal{F}$, $K\cap P_{i}\neq\emptyset$ for at most $4t$
values of $i$, it follows that the number of values of $i$ for which $K\cap
P_{i}\neq\emptyset$ is less than $4t\kappa(Z)\leq c\log^{6}n$. But this
contradicts the fact that $Z$ separates $a$ from $b$ in $G^{\prime\prime}$. ∎

##  15 From pairs of vertices to tree decompositions.

In this section we prove our main result, following the outline of the last
few sections of [14]. We need a theorem from [13]:

######  Theorem 15.1 (Chudnovsky, Gartland, Hajebi, Lokshtanov, Spirkl [13]).

There is an integer $d$ with the following property. Let $G\in\mathcal{C}$ and
let $w$ be a normal weight function on $G$. Then there exists $Y\subseteq
V(G)$ such that

  * •

$|Y|\leq d$, and

  * •

$N[Y]$ is a $w$-balanced separator in $G$.

We also need some terminology and two results from [14]. Let $L,d,r$ be
integers. We say that an $n$-vertex graph $G$ is $(L,d,r)$-breakable if

  1. 1.

for every two disjoint and anticomplete cliques $H_{1},H_{2}$ of $G$ with
$|H_{1}|\leq r$ and $|H_{2}|\leq r$, there is a set $X\subseteq
G\setminus(H_{1}\cup H_{2})$ with $\alpha(X)\leq L$ separating $H_{1}$ from
$H_{2}$, and

  2. 2.

for every normal weight function $w$ on $G$ and for every induced subgraph
$G^{\prime}$ of $G$ there exists a set $Y\subseteq V(G^{\prime})$ with
$|Y|\leq d$ such that for every component $D$ of $G^{\prime}\setminus N[Y]$,
$w(D)\leq\frac{1}{2}$.

######  Theorem 15.2 (Chudnovsky, Hajebi, Lokshtanov, Spirkl [14]).

For every integer $d>0$ there is an integer $C(d)$ with the following
property. Let $L,n,r>0$ be integers such that $r\leq d(2+\log n)$ and let $G$
be an $n$-vertex $(L,d,r)$-breakable theta-free graph. Then there exists a
$w$-balanced separator $Y$ in $G$ such that $\alpha(Y)\leq
C(d)\lceil\frac{d(2+\log n)}{r}\rceil(2+\log n)L$.

######  Lemma 15.3 (Chudnovsky, Hajebi, Lokshtanov, Spirkl [14]).

Let $G$ be a graph, let $c\in[\frac{1}{2},1)$, and let $d$ be a positive
integer. If for every normal weight function $w$ on $G$, there is a
$(c,w)$-balanced separator $X_{w}$ with $\alpha(X_{w})\leq d$, then the tree
independence number of $G$ is at most $\frac{3-c}{1-c}d$.

We now prove:

######  Theorem 15.4.

There exists an integer $M$ with the following property. Let $G$ be an even-
hole-free graph with $n$ vertices and let $w$ be a normal function on $G$.
Then there exists a $w$-balanced separator $Y$ in $G$ such that $\alpha(Y)\leq
M\log^{10}n$.

###### Proof.

Let $d$ be as in Theorem 15.1 and let $c$ be as in Theorem 3.1. By Theorem
15.1 and Theorem 3.1, it follows that $G$ is $(c\log^{8}n,d,1)$-breakable. Now
the result follows from Theorem 15.2. ∎

Theorem 1.1 now follows immediately from Theorem 15.4 and Lemma 15.3.

## References

  * [1] P. Aboulker, I. Adler, E. J. Kim, N. L. D. Sintiari, and N. Trotignon. “On the tree-width of even-hole-free graphs.” https://arxiv.org/abs/2008.05504
  * [2] I. Adler, N. K. Le, H. Müller, M. Radovanović, N. Trotignon and K. Vušković. “On rank-width of even-hole-free graphs.” Discrete Mathematics & Theoretical Computer Science 19(1) (2017) https://doi.org/10.23638/DMTCS-19-1-24
  * [3] T. Abrishami, B. Alecu, M. Chudnovsky, S. Hajebi and S. Spirkl. “Induced subgraphs and tree decompositions X. Towards logarithmic treewidth in even hole free graphs.” https://arxiv.org/abs/2307.13684
  * [4] T. Abrishami, M. Chudnovsky, C. Dibek, S. Hajebi, P. Rzążewski, S. Spirkl, and K. Vušković. “Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree.” J. Comb. Theory Ser. B, 124(1) (2024), 371–403.
  * [5] T. Abrishami, M. Chudnovsky, C. Dibek and K. Vušković, “Submodular functions and perfect graphs”, to appear in Mathematics of Operations Research.
  * [6] T. Abrishami, M. Chudnovsky, S. Hajebi and S. Spirkl “Induced subgraphs and tree decompositions III. Three paths configurations and logarithmic tree-width”. Advances in Combinatorics (2022).
  * [7] T. Abrishami, M. Chudnovsky, and K. Vušković. “Induced subgraphs and tree decompositions I. Even-hole-free graphs of bounded degree.” J. Comb. Theory Ser. B, 157 (2022), 144–175.
  * [8] L. Addario-Berry, M. Chudnovsky, F. Havet, B. Reed, and P. Seymour. “Bisimplicial vertices in even-hole-free graphs.” J. Comb. Theory Ser. B, 98(6) (2008), 1119–1164.
  * [9] V.E. Alekseev. “On the number of maximal independent sets in graphs from hereditary classes” Combinatorial-Algebraic Methods in Discrete Optimization, University of Nizhny Novgorod, 1991, 5–8 (in Russian).
  * [10] H. L. Bodlaender. “Dynamic programming on graphs with bounded treewidth.” Springer, Berlin, Heidelberg, (1988), 105–118.
  * [11] R. B. Borie, R. G. Parker and C. A. Tovey. “Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families.” Algorithmica 7, (1992), 555-–581.
  * [12] K. Cameron, M. V. G. da Silva, S. Huang, and K. Vušković. “Structure and algorithms for (cap, even hole)-free graphs.” Discrete Mathematics 341 (2018), 463–473.
  * [13] M. Chudnovsky, P. Gartland, S. Hajebi, D. Lokshtanov and S. Spirkl. “Induced subgraphs and tree decompositions XV. Even-hole-free graphs have logarithmic treewidth.” https://arxiv.org/abs/2402.14211
  * [14] M. Chudnovsky, S. Hajebi, D. Lokshtanov and S. Spirkl. “Tree independence number II. Three-path-configurations.” https://arxiv.org/abs/2405.00265
  * [15] M. Chudnovsky, M. Pilipczuk, M. Pilipczuk and Stéphan Thomassé. “Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in $\\{H\\}$-Free Graphs.” SIAM Journal on Computing 53(1) (2024), 47–86.
  * [16] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas. T “The strong perfect graph theorem.” Annals of mathematics (2006), 51–229.
  * [17] M. Chudnovsky and P. Seymour. “Even-hole-free graphs still have bisimiplicial vertices.” J. of Comb. Theory Ser. B 161 (2023), 331–381.
  * [18] M. Chudnovsky, S. Thomassé, N. Trotignon, K. Vuskovic. “Maximum independent sets in (pyramid, even hole)-free graphs.” https://arxiv.org/abs/1912.11246
  * [19] M. Conforti, B. Gerards and K. Pashkovich. “Stable sets and graphs with no even holes.” Mathematical Programming: Series A and B, 153 (2015), 13–39.
  * [20] M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković “Even-hole-free graphs part I: Decomposition theorem.” Journal of Graph Theory, 39(1) (2002), 6–49.
  * [21] M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer-Verlag (2015)
  * [22] C. Dallard, F. Fomin, P. Golovach, T. Korhonen and M. Milanič. “Computing Tree Decompositions with Small Independence Number.” https://arxiv.org/abs/2207.09993
  * [23] C. Dallard, M. Krnc, O. Kwon, M. Milanič, A. Munaro, K. Štorgel and S. Wiederrecht. “Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star” https://arxiv.org/abs/2402.11222
  * [24] C. Dallard, M. Milanič and K. Štorgel. “Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure”. SIAM Journal on Discrete Mathematics 35(4) (2021), 2618–2646.
  * [25] C. Dallard, M. Milanič and K. Štorgel. “Treewidth versus clique number. II. Tree-independence number.” https://arxiv.org/abs/2111.04543
  * [26] C. Dallard, M. Milanič and K. Štorgel. “Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure.” https://arxiv.org/abs/2206.15092
  * [27] R. Diestel. Graph Theory. Springer-Verlag, Electronic Edition, (2005).
  * [28] R. G. Downey, and M. R. Fellows. Fundamentals of parameterized complexity. Springer-Verlag, (2013)
  * [29] P. Erdős and G. Szekeres. “A combinatorial problem in geometry.” Compositio Math 2 (1935), 463–470.
  * [30] M. Farber. “On diameters and radii of bridged graphs.” Discrete Math. 73 (1989) 249–260.
  * [31] J. Flum and M. Grohe . Parameterized Complexity Theory. Springer-Verlag (2006)
  * [32] M. R. Garey and D. S. Johnson. Computers and intractability. Freeman (1979)
  * [33] F. Gavril. “The intersection graphs of subtrees in trees are exactly the chordal graphs.” _J. Comb. Theory Ser. B_ 16 (1) (1974), 47–56.
  * [34] M. Grötschel, L. Lovász, A. Schrijver , “The ellipsoid method and its consequences in combinatorial optimization.” _Combinatorica_ , (1981), 169–-197.
  * [35] E. Husic, S. Thomassé, N. Trotignon. “The Independent Set Problem Is FPT for Even-Hole-Free Graphs.” _Proceedings of IPEC_ (2019) 21:1–21:12
  * [36] R. M. Karp. “Reducibility Among Combinatorial Problems” _Complexity of Computer Computations_ , (1972), 85–103.
  * [37] V. Korchemna, D. Lokshtanov, S. Saurabh, V. Surianarayanan, J. Xue, “ Efficient Approximation of Hypertree Width”, manuscript to appear in Proceedings of FOCS (2024)
  * [38] N.K. Le. “Coloring even-hole-free graphs with no star cutset.” https://arxiv.org/abs/1805.01948
  * [39] P. T. Lima, M. Milanič, P. Muršič, K. Okrasa, P. Rzążewski and K. Štorgel. “Tree decompositions meet induced matchings: beyond Max Weight Independent Set.” https://arxiv.org/abs/2402.15834.
  * [40] N. Robertson and P.D. Seymour. “Graph minors. V. Excluding a planar graph.” J. Comb. Theory Ser. B, 41 (1) (1996), 92-–114.
  * [41] N. Robertson and P.D. Seymour. “Graph minors. XVI. Excluding a non-planar graph.” J. Combin. Theory, Ser. B, 89 (2003), 43–76.
  * [42] M.V.G. da Silva and and K. Vušković. “Decomposition of even-hole-free graphs with star cutsets and 2-joins”, J. Comb. Theory Ser. B, 103 (2013), 144–183.
  * [43] M.V.G. da Silva and and K. Vušković. “Triangulated neighborhoods in even-hole-free graphs”, Discrete Math. 307 (2007), 1065–1073.
  * [44] N.L.D. Sintiari and N. Trotignon. “(Theta, triangle)-free and (even-hole, $K_{4}$)-free graphs. Part 1: Layered wheels”, J. Graph Theory 97 (4) (2021), 475-509.
  * [45] Y. Tamura, T. Ito, and X. Zhou “Deterministic Algorithms for the Independent Feedback Vertex Set Problem.” Proceedings of IWOCA (2014), 351–363.
  * [46] K. Vušković. “Even-hole-free graphs: A survey.” Applicable Analysis and Discrete Mathematics, (2010), 219–240.
  * [47] S. Wagon. “A bound on the chromatic number of graphs without certain induced subgraphs.” J. Combin. Theory Ser. B 29(3) (1980), 345–346.


# A Social structure description of epidemics propagation with the mean field
game paradigm

Louis Bremaud  Denis Ullmo  Université Paris-Saclay, CNRS, LPTMS, 91405,
Orsay, France

###### Abstract

We consider the spread of infectious diseases through a Mean Field Game
version of a SIR compartmental model with social structure, in which
individuals are grouped by their age class and interact together in different
settings. In our game theoretical approach, individuals can choose to limit
their contacts if the epidemic is too virulent, but this effort comes with a
social cost. We further compare the Nash equilibrium obtained in this way with
the societal optimum that would be obtained if a benevolent central planner
could decide of the strategy of each individual, as well as to the more
realistic situation where an approximation of this optimum is reached through
social policies such as lockdown.

As the Covid-19 has made rather explicit in the last few years, possessing
good prediction tools for the dynamics of virus infections is mandatory if one
wishes to design public policies making it possible to mitigate effectively
the negative impact of an epidemic. Since the early twentieth century, many
models have been proposed to address this issue, one of the simplest being the
SIR (Susceptible-Infected-Recovered) compartment model [13] and its variations
[11], which has been recently refined to take into account the structure of
social contacts [8], [19] or spatial/geographic aspects of the dynamics [18],
[6].

For virus epidemics like the Covid-19, with a very fast dynamics, one
important difficulty met by epidemiologists can be illustrated already on the
SIR model. Noting $S$, $I$ and $R$ the relative proportion of agents in the
three possible states (respectively “Susceptible”, “Infected” and
“Recovered”), the time dependence of these “state variables” follow the set of
equations

$\begin{cases}\displaystyle{\dot{S}=-\chi S(t)I(t)}\\\
\displaystyle{\dot{I}=(\chi S(t)-\xi)I(t)}\;,\\\ \displaystyle{\dot{R}=\xi
I(t)}\\\ \end{cases}$ (1)

which are characterized by two “extrinsic” parameters, the recovery rate $\xi$
and the contact rate $\chi$.

Given the height of the stakes posed by the control of the Covid-19 epidemics
in the last couple of years, both from a public health and economic point of
view, major efforts have been invested by the epidemiologist community to
extract these parameters, or their counterpart in more complex models, from
the actual data observed on the field. However, if $\xi$ is mainly fixed by
biological considerations, and thus can be considered as essentially constant
in time, the contact rate $\chi$ on the other hand depends a lot on the
agent’s behavior (ie whether they actually meet or not) which has a dynamics
on its own. This dynamics is furthermore coupled to the dynamics of the
epidemic itself since people will limit or increase their contacts depending
on whether or not they feel at risk from the epidemic. This implies that it is
essentially impossible to fit the time dependence of $\chi$ on past data. In
models used to advise public policies, this time dependence is thus either
simply ignored, or involves a lot of guesswork, leading to predictions that
can be trusted only for a rather short amount of time (see nevertheless [21,
7]). To avoid such a situation, it is necessary to introduce models whose
“extrinsic” parameters have no time dependence (on the time scale of the
epidemic), and which can therefore be fitted in a reliable way on field data.
In other words, it is necessary to make “intrinsic” the dynamics of parameters
such as $\chi$. To achieve this, a game theoretical approach is required, and
the one that we will follow here is provided by Mean Field Game (MFG) theory.

Introduced by Lasry and Lions a decade ago [17, 16, 15] and independently by
M.Huang, R.P. Malhamé and P. E. Caines [12], Mean Field Games (MFG) focus on
the derivation of a Nash equilibrium within a population containing a larger
number of individuals. Reader can look at [2, 9, 3] for a complete
mathematical description, and to [23, 22] for an introduction designed for
physicists. Applications of MFG, include finance [10], economics [4] and
opinion dynamics [1] among others. The introduction of MFG models to describe
epidemics dynamics has been pioneered by Turinici and al. to describe
vaccination strategies [14] or the dynamics of the parameter $\chi(t)$ in the
simple SIR model [5].

The simple toy models addressed in [5] are however presumably still too
schematic to be relevant from a practical, public policy point of view. The
goals of this letter are to show that a good degree of complexity can be
included in these MFG models, and in particular that we can implement a
description of the social structure of society in which the epidemics develop.
Furthermore we shall see that with our Mean Field Game approach, question of
direct practical importance, such as defining the best government strategy
with respect to confinement and deconfinement policies, can be addressed.

We therefore consider a SIR model with a structure of social contacts proposed
in [8] and [19] to get a more detailed description of the society, at a
mesoscopic scale. Following [8], we make a differentiation between individuals
according to their age. Here we choose to introduce three age classes :
“young”, “adult” and “retired” people but a more refined description could
easily be implemented. Furthermore, we split the society in four main settings
where individuals have contacts with other : the schools, the households, the
community and the workplaces. Thus the dynamics of the epidemic may differ for
different age class and the interactions between individuals (of the same
class or not) may differ in different setting.

To model the interactions, following [8], we introduce the parameters
$M^{\gamma}_{\alpha\beta}$ which measure the average frequency of contacts
with someone of age class $\beta$ for an individual of age class $\alpha$ in
the setting $\gamma$. To enforce the sum rule imposed by the fact that a
contact between two agents involves both of them in a symmetric way, we make a
slight variation here with respect to [8] and set
$M^{\gamma}_{\alpha\beta}=W^{\gamma}_{\alpha\beta}\cdot K_{\beta}$ where
$W^{\gamma}_{\alpha\beta}$ is a symmetric matrix and $K_{\beta}$ is the
proportion of individuals of age class $\beta$ in the population. Physically,
$W^{\gamma}_{\alpha\beta}$ can be seen as the “willingness of contacts”
between an individual of age class $\alpha$ and another of age class $\beta$
in the setting $\gamma$. We assume here that this symmetric matrix is built as
$W^{\gamma}_{\alpha\beta}=w^{\gamma}_{\alpha\beta}\cdot
w^{\gamma}_{\beta\alpha}$ where $w^{\gamma}_{\alpha\beta}$ is the
“willingness” of an individual of age class $\alpha$ to have contact with
someone of age class $\beta$ (in the setting $\gamma$).

In our game theoretical approach, we assume that individuals of age class
$\alpha$ control their “willingness of contacts” with other individuals in
each setting. We therefore write
$w^{\gamma}_{\alpha\beta}=w^{\gamma(0)}_{\alpha\beta}n^{\gamma}_{\alpha}(t)$,
where $w^{\gamma(0)}_{\alpha\beta}$ denotes this “willingness” in the absence
of epidemic (similarly for $W^{\gamma(0)}_{\alpha\beta}$ and
$M^{\gamma(0)}_{\alpha\beta}$), and
$n^{\gamma}_{\alpha}(t)\in[{n^{\gamma}_{\alpha,\rm min}},1]$ is a time
dependent coefficient measuring the effort made by the individual to limit
contacts because of the epidemic situation, and which is assumed to vary
between a value ${n^{\gamma}_{\alpha,\rm min}}$ representing the maximum
effort that can be expected from the agent and 1 corresponding to the base
willingness in the absence of effort. Notice that for simplicity, we use
$n^{\gamma}_{\alpha}$ instead of $n^{\gamma}_{\alpha\beta}$, that is
individuals do not change their behavior according to the age class of the
contact $\beta$ but only according to the setting $\gamma$ (a $\beta$
dependence of $n$ could easily be implemented to this model and change only
slightly the equations).

Indexing by $\alpha$ the proportion of Susceptible/ Infected/ Recovered people
of age class $\alpha$, and denoting by $q$ the probability of transmission (of
the virus) per effective contact (between a susceptible and an infected), the
SIR equations (with $n=3$ age classes) read [8]

$\displaystyle\dot{S}_{\alpha}$
$\displaystyle=-\bar{\lambda}_{\alpha}(t)S_{\alpha}(t)\;$ (2)
$\displaystyle\dot{I}_{\alpha}$
$\displaystyle=+\bar{\lambda}_{\alpha}(t)S_{\alpha}(t)-\xi I_{\alpha}(t)\;,$
$\displaystyle\dot{R}_{\alpha}$ $\displaystyle=\xi I_{\alpha}(t)$

where the “force of infection” $\bar{\lambda}_{\alpha}(t)$ corresponds to $q$
time the average number of infected people met by a susceptible agent of age
class $\alpha$ during $dt$, and is written as

$\bar{\lambda}_{\alpha}(t)\equiv q\left[\sum_{\beta=1}^{n}\sum_{\gamma}\
{\bar{n}}^{\gamma}_{\alpha}(t)\ {\bar{n}}^{\gamma}_{\beta}(t)\
M^{\gamma(0)}_{\alpha\beta}\ I_{\beta}(t)\right]\;,$ (3)

with $\bar{n}^{\gamma}_{\alpha}$ the average value of ${n^{\gamma}_{\alpha}}$
over agents in the age class $\alpha$. In the following, we will denote
$\lambda$ (without bar above) when we focus on the force of infection seen by
a reference individual, $\lambda_{\alpha}(t)\equiv
q\left[\sum_{\beta=1}^{n}\sum_{\gamma}{n}^{\gamma}_{\alpha}(t){\bar{n}}^{\gamma}_{\beta}(t)M^{\gamma(0)}_{\alpha\beta}I_{\beta}(t)\right]$.

In our Mean Field Game version of this model, the state variable of an agent
$k_{\alpha}$ of age class $\alpha$ is her status
$x_{k_{\alpha}}\in\\{s_{\alpha}\\!=\\!{\rm susceptible},i_{\alpha}\\!=\\!{\rm
infected},r_{\alpha}\\!=\\!{\rm recovered}\\}$. The control parameters of
individuals of age class $\alpha$ are the contact willingness
$n^{\gamma}_{\alpha}(t)$, and each individual ${k_{\alpha}}$ which is
susceptible at time $t$ (ie $x_{k_{\alpha}}=s_{\alpha}$) will adjust these
contact willingness to minimize an inter-temporal cost that we take of the
form

$\displaystyle
C_{\alpha}\left(\\{n^{\gamma}_{\alpha}(\cdot)\\},t\right)\equiv$ (4)
$\displaystyle\int_{t}^{T}\left[\lambda_{\alpha}(s){\tilde{r}}_{I,\alpha}(I(s))+f_{\alpha}\left(\\{n^{\gamma}_{\alpha}(s)\\}\right)\right](1-\phi_{\alpha}^{I}(s))ds\;.$

In this equation

${\tilde{r}}_{I,\alpha}(I(s))=r_{I,\alpha}+g_{\alpha}(I(s))$ (5)

is the total cost of infection, which includes a base cost $r_{I,\alpha}$
(which we assume increasing with the age class $\alpha$, modeling that we
suffer more from infection when we are older), and an additional cost
$g_{\alpha}(I(s))$ which model the saturation of the sanitary system.
$f_{\alpha}\left(\\{n^{\gamma}_{\alpha}(s)\\}\right)$ measure the cost (both
psychological and financial) associated with the limitation of social contacts
(we assume this cost to be decreasing, with a positive second derivative), and
$\phi_{\alpha}^{I}(t)$ is the probability for an individual of age class
$\alpha$ to be infected before $t$, so that an infection for this individual
happens between $t$ and $t+dt$ with a probability
$(1-\phi_{\alpha}^{I}(t))\lambda_{\alpha}(t)dt$. Note that in principle one
should also model specifically the behavior of infected people, as this could
vary from a completely egoistic approach where they stop doing any effort to a
very altruistic one where infected people completely isolate from the rest of
population. In epidemics like covid-19, however, most of the transmission is
due to a small part of the infected people not aware of their infectious
status. Our model correspond to the limit where this proportion is extremely
small, and for which $q$, the probability of transmission of the virus,
integrate this probability.

To solve this optimization problem, we follow a standard approach in this
context [9], and introduce the value function

$U_{\alpha}(t)=\underset{\\{n^{\gamma}_{\alpha}(\cdot)\\}}{\min}C_{\alpha}\left(\\{n^{\gamma}_{\alpha}(\cdot)\\},t\right)$
(6)

which is thus the minimal price (in stochastic average) that a susceptible
agent (at $t$) can pay between $t$ and the end of the game. Using the Bellman
equation, which states that, for any intermediate time $t_{i}$, the optimal
path between $t$ and $T$ can be constructed as the concatenation of optimal
paths between $t$ and $t_{i}$ and between $t_{i}$ and $T$ followed by an
optimization of the control parameters at $t_{i}$ we get the Hamilton-Jacobi-
Bellman equation of our Mean Field Game

$-\frac{dU_{\alpha}(t)}{dt}=\\\
\underset{\\{n^{\gamma}_{\alpha}(t)\\}}{\min}\left[\lambda_{\alpha}(t)\left({\tilde{r}}_{I,\alpha}(I(t))-U_{\alpha}(t)\right)+f_{\alpha}\left(\\{n^{\gamma}_{\alpha}(t)\\}\right)\right]\;.$
(7)

Then, the optimal strategy $n^{\gamma*}_{\alpha}(t)$ is expressed as

$\\{n^{\gamma*}_{\alpha}(t)\\}=\\\
\underset{\\{n^{\gamma}_{\alpha}(t)\\}}{\text{argmin}}\left[\lambda_{\alpha}(t)\left({\tilde{r}}_{I,\alpha}(I(t))-U_{\alpha}(t)\right)+f_{\alpha}\left(\\{n^{\gamma}_{\alpha}(t)\\}\right)\right]\;.$
(8)

We stress, however, that in Eq. (4), the dynamic of the infection Eqs. (2)-(3)
at time $t$, is fixed by the strategies $\bar{n}^{\gamma}_{\alpha}(s<t)$,
followed (on average) by the total population of agents, which is a priory
distinct from the one $n^{\gamma*}_{\alpha}$ followed by the individual
optimizing the cost Eq. (4). In all rigor this cost should be written as
$C_{\alpha}\left(\\{\bar{n}^{\gamma}_{\alpha}\\},\\{n^{\gamma}_{\alpha}\\},t\right)$,
and the situation for which for all setting $\gamma$ and all age class
$\alpha$ one has

$n^{\gamma*}_{\alpha}=\bar{n}^{\gamma}_{\alpha}$ (9)

corresponds to a Nash equilibrium, in the sens that an individual agent has no
interest in deviating to another strategy if this strategy is followed by the
rest of the agents. “Solving” our Mean Field Game therefore amounts to : i)
Solve the rate equations (2) assuming the general population strategy
$\\{\bar{n}^{\gamma}_{\alpha}\\}$ given. This in particular will determine the
function $\phi_{\alpha}^{I}(t)$ for $t\in[0,T]$; ii) Solve the optimization
problem defined by the cost Eq. (4) and deduce from it
$\\{n^{\gamma*}_{\alpha}\\}$, the optimal $\\{n^{\gamma}_{\alpha}\\}$ for a
given individual; and iii) Impose the self consistent equation (9) that
defines the Nash equilibrium of our MFG.

Since the time dependence of the $\\{n^{\gamma}_{\alpha}\\}$ is now an outcome
of the description, our MFG model defined by the dynamics Eqs. (2)-(3) and the
cost function Eq. (4) clearly meet the criterion that all the extrinsic
parameters characterizing it are time independent, and could in principle be
fitted on field data. The actual extraction of these parameters is of course
well beyond the scope of this work, and in the following, we illustrate the
behavior of our MFG for a “reasonable choice” of this parametrization (these
quantities are rather generic, and the observed behaviors are a priori
typical, which was checked by running many simulations with different
parameters).

As mentioned above, we consider four settings ($S$=schools, $W$=workplaces,
$C$=community and $H$=households) and three age classes ($y$=youth,
$a$=adults, $r$=retired). For the cost of infection Eq. (5) we take

${\tilde{r}}_{I,\alpha}\left(I(t)\right)=\kappa_{\alpha}\left[r_{I}\left(\exp\left[\alpha_{\rm
sat}\frac{I(t)-I_{\rm sat}}{I_{\rm sat}}\right]-1\right)\right]\;,$ (10)

where the factors $\kappa_{\alpha}$ accounts for the fact that older agents
are more impacted by the infection, while $r_{I}$ and $\alpha_{\rm sat}$ are
both constant modeling respectively the usual cost of infection and the impact
of saturation on the cost. The additional cost is exponential with a threshold
when we reach the saturation at $I=I_{\rm sat}$. Finally for the cost of the
contact willingness reduction $f_{\alpha}(\\{n^{\gamma}_{\alpha}\\})$ we take
a form inspired from [5]

$f_{\alpha}(\\{n^{\gamma}_{\alpha}(t)\\})=\sum_{\gamma}\left[\left(\frac{1}{n^{\gamma}_{\alpha}(t)}\right)^{\mu_{\gamma}}-1\right]\;,$
(11)

where $\mu_{\gamma}$ models= the variability of the “attachment” to the
setting $\gamma$, as it is for example easier to reduce contacts at work
rather than inside families.

$M^{S}$ | $M^{W}$ | $M^{C}$ | $M^{H}$ | $\kappa_{\alpha}$ | $K_{\alpha}$ | $n^{\gamma}_{min}$ | $\mu_{\gamma}$
---|---|---|---|---|---|---|---
$\begin{pmatrix}100&0&0\\\ 0&0&0\\\ 0&0&0\end{pmatrix}$ | $\begin{pmatrix}0&0&0\\\ 0&75&0\\\ 0&0&0\end{pmatrix}$ | $\begin{pmatrix}12.5&25&12.5\\\ 12.5&25&12.5\\\ 12.5&25&12.5\end{pmatrix}$ | $\begin{pmatrix}15&25&10\\\ 12.5&32.5&5\\\ 10&10&30\end{pmatrix}$ | $(1,10,1000)$ | $(0.25,0.5,0.25)$ | $(\frac{1}{3},\frac{1}{5},\frac{1}{5},\frac{1}{2})$ | $(2,2,1,3)$
$S_{\alpha}(0)$ | $I_{\alpha}(0)$ | $(I_{sat},\alpha_{sat})$ | $\gamma$ | $q$ | $I_{l}$ | $I_{d}$ | $\sigma$
$(0.99,0.99,0.99)$ | $(0.01,0.01,0.01)$ | (0.01,0.01) | 1.2 | 0.02 | 0.1 | $4.10^{-4}$ | 0.39
Table 1: Table of parameters used in our simulations (proportion in % for
epidemics quantities, the time unit is assumed to be a week, matrices and
rates have the corresponding units)

Fig. 1 shows the dynamics of the epidemic together with the choices made by
individuals for their contact willingness for both a relatively moderate cost
for the infection ($r_{I}=1$) and a much stronger one ($r_{I}=5$), with the
choice of parameters given in table 1. The simulations have been obtained
using a gradient descent on the variable $\\{n_{\alpha}^{\gamma}\\}$ of the
cost $C$ to reach the Nash equilibrium. In the case $r_{I}=1$, we see in this
figure that there are significant efforts made by individuals when $I(t)$
exceed the threshold $I_{\rm sat}$. More precisely, retired people
significantly reduce their contacts because the cost associated with the
infection is for them very high and this reduction is done in particular in
the community setting because this is the easiest place to reduce once
contacts. On the other hand, young people, who take no significant risk with
the disease, barely modify their behavior, while the adults are in an
intermediate situation. For $r_{I}=5$, the cost of infection is sufficiently
high so that one does not reach the saturation $I_{\rm sat}$, the epidemic is
lower and slower.

Figure 1: Evolution of the epidemic quantities and contact willingness with
$r_{I}=1$ (solid line) and $r_{I}=5$ (dashed line). Upper panel : evolution of
proportion of infected by age class. Lower panel (left to right) : evolution
of contact willingness of individuals according to their age class in
community, households, schools (for the young) and workplaces (for the adults)

In the previous equilibrium analysis, each agent performs a personal,
eventually egoistic, optimization. A “benevolent global planner”, ie a well
meaning government with full empowerment, would, on the other hand, attempt to
reach a “societal optimum” [24, 20, 5], i.e. to optimize the global cost of
the entire society, which would amount to solve :

$\underset{\\{\bar{n}^{\gamma}\\}}{\min}\;C_{\rm
glob}\left(\\{\bar{n}^{\gamma}_{\alpha}\\}\right)\;\equiv\;\underset{\\{\bar{n}^{\gamma}\\}}{\min}\;\sum_{\alpha}\left[K_{\alpha}\times
C_{\alpha}\left(\\{\bar{n}^{\gamma}_{\alpha}\\},\\{\bar{n}^{\gamma}_{\alpha}\\}\right)\right]\;\;.$
(12)

The difference between this new minimization and the Nash equilibrium
discussed above is referred to as “the cost of anarchy”, because there is no
cooperation between individuals in the Nash equilibrium contrary to the
societal optimum case. We compute it with a gradient descent on the cost
$C_{glob}$, and we plot the dynamics on figure 2.

In practice however, it is largely impossible for a government to control the
detailed behavior of each individual, especially in democratic countries, and
even if this was technically feasible, it would involve an important
coordination cost that would have to be included in the epidemic cost Eq. (4).
Government will therefore use median mode of actions, such as lockdown, to
approach the societal optimum at a reasonable coordination (and democratic)
cost. We address now the question of how the lockdown policy can be used to
approach as well as possible the societal optimum.

We therefore assume that above a certain threshold of infection, $I_{l}$, a
global planner impose a reduction of the maximum contact willingness
$n^{\gamma}_{\alpha l}$, that we assume of the form $n^{\gamma}_{\alpha
l}=\sigma n^{\gamma}_{\alpha,{\rm min}}+(1-\sigma)$, ($\sigma\in[0,1]$) in
each setting for each individual. Once the “lockdown” is imposed, one returns
to the original situation (without lockdown) at different threshold $I_{d}$
with $I_{d}$ < $I_{l}$. For a given value of the thresholds and of the
$n^{\gamma}_{\alpha l}$ we can compute the Nash equilibrium as in our original
approach, and we can then perform a gradient descent on these parameters to
reach their optimal value, i.e. the optimal lockdown policy.

We show on figure 2 the numerical simulation for the societal optimum and for
the optimal lockdown policy, with the same parameters as Fig. 1 and $r_{I}=1$,
giving for the optimal lockdown policy $I_{l}=0.1=I_{sat}$, $I_{d}=4.10^{-4}$,
and $\sigma=0.39$. For the societal optimum the cooperation appears clearly :
at the epidemic peak there is a mutual action of all individuals to limit
simultaneously their contacts, especially in community and households where
adults and young people make efforts in order to limit the number of infected
retired people, even if the efforts in households are costly. On the other
hand, less efforts are made in schools or in workplaces because this affect
less the retired people. These combination of efforts leads to a very low cost
for the entire society.

Figure 2: Evolution of the epidemic quantities and contact willingness for the
societal optimum (dashed line) and the optimal lockdown policy (solid line).
Upper panel : evolution of proportion of infected by age class (main panel)
and on average (inset). Lower panel (left to right) : evolution of contacts
willingness of individuals according to their age class in community,
households, schools, and workplaces.

For the Nash equilibrium under optimal constraints we see on figure 2 that
since the lockdown is imposed in all settings, we obtain a situation where
adults and young people make almost the same efforts everywhere while retired
people go beyond the lockdown level to achieve further protection. This
lockdown has a strong effect on the epidemic but lack the coordination of the
optimum societal case. This leads to a number of infected adults and young
which is lower than the “societal optimum” while it is higher for retired
people.

To conclude it might be useful to introduce a “figure of merite” of a given
policy $\mathcal{P}$

$M(\mathcal{P})=\frac{C_{\rm glob}(\mathcal{P})-C_{\rm glob}(\mbox{societal
optima})}{C_{\rm glob}(\mbox{business as usual})-C_{\rm glob}(\mbox{societal
optima})}\;,$ (13)

which is thus such that $M(\mathcal{P})$ is 0 if $\mathcal{P}$ is the societal
optima and 1 if $\mathcal{P}$ is the “business as usual” strategy for which no
adjustment is made to the contacts between agents. On that scale, we see that
$M(\mathcal{P})=0.12$ for the unconstrained Nash equilibrium and 0.06 for the
optimal lockdown policy, but non-optimal lockdown policies are most of the
time less effective than the unconstrained Nash, and can have typically a $M$
of order $0.5$.

Although these numbers apply obviously only to the specific model and to the
specific set of parameters we have used as an illustration here, there is no
doubt that the qualitative features observed are very general in nature.
Namely, the Nash equilibrium is already a very significant improvement with
respect to the “business as usual approach”, and if on the one hand an
optimized lockdown strategy can close further the gap toward the societal,
sub-optimal lockdown strategies can actually “degrade” the situation with
respect to the basic Nash equilibrium.

As a final remark, we stress that it should not be assumed, and we certainly
do not imply here, that the Nash equilibrium is the “natural outcome” of the
epidemic process that would be reached in the absence of any public policy.
Indeed, our model assumes that the agents possess both perfect information and
the technical resources to compute the Nash equilibrium, which we cannot
expect them to have in practice. On the other hand gathering this information
and developing the technical tools to compute the Nash equilibrium appears
like a reachable goal for a centralized public agency. If enough trust is
build between the government and the individual agents, making public that
information can be enough to coordinate the ensemble of agents around the Nash
equilibrium. This, as well as the optimization of lockdown or similar policies
improving on the basic Nash equilibrium requires to develop the necessary
conceptual tools. We hope this work provides a useful step in that direction.

## References

  * [1] Dario Bauso, Raffaele Pesenti, and Marco Tolotti.  Opinion dynamics and stubbornness via multi-population mean-field games.  Journal of optimization theory and applications, 170(1):266–293, July 2016.
  * [2] Peter E. Caines, Minyi Huang, and Roland P. Malhame.  Mean Field Games, pages 1–28.  Springer International Publishing, Cham, 2017.
  * [3] Rene Carmona and François Delarue.  Probabilistic Theory of Mean Field Games with Applications I.  Springer, 2018.
  * [4] Patrick. Chan and Ronnie. Sircar.  Bertrand and cournot mean field games.  Applied Mathematics and Optimization, 71(3):533–569, June 2015\.
  * [5] R. Elie, E. Hubert, and G. Turnici.  Contact rate epidemic control of covid-19 : An equilibrium view.  Mathematical Modelling of Natural Phenomena, 15, June 2020.
  * [6] S. Eubank, H. Guclu, Anil Kumar, V., and al.  Modelling disease outbreaks in realistic urban social networks.  Nature, 429:180–184, 04 2004.
  * [7] Neil M Ferguson, Daniel Laydon, Gemma Nedjati-Gilani, and al.  Impact of non-pharmaceutical interventions (NPIs) to reduce covid-19 mortality and healthcare demand.  Faculty of Medicine, 03 2020.
  * [8] L. Fumanelli, M. Ajelli, P. Manfredi, A. Vespignani, and S. Merler.  Inferring the structure of social contacts from demographic data in the analysis of infectious diseases spread.  PLOS Computational Biology, 8, September 2012.
  * [9] Diogo A. Gomes, Joana Mohr, and Rafael Rigão Souza.  Continuous time finite state mean field games.  Applied Mathematics & Optimization, 68(1):99–143, Apr 2013.
  * [10] Olivier Gueant, Jean-Michel Lasry, and Pierre-Louis Lions.  Mean Field Games and Applications, pages 205–266.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2011.
  * [11] Herbert W. Hethcote.  The mathematics of infectious diseases.  Society for Industrial and Applied Mathematics, 42(4):599–653, October 2000.
  * [12] Minyi Huang, Roland Malhame, and Peter Caines.  Large population stochastic dynamic games: Closed-loop mckean-vlasov systems and the nash certainty equivalence principle.  Commun. Inf. Syst., 6, 01 2006.
  * [13] William Ogilvy Kermack, A. G. McKendrick, and Gilbert Thomas Walker.  A contribution to the mathematical theory of epidemics.  Proceedings of the Royal Society of London. Series A, Containing Papers of a Mathematical and Physical Character, 115(772):700–721, 1927.
  * [14] Laetitia Laguzet, Gabriel Turinici, and Ghozlane Yahiaoui.  Equilibrium in an individual - societal SIR vaccination model in presence of discounting and finite vaccination capacity.  In Viorel Barbu, Catalin Lefter, and Ioan I. Vrabie, editors, New Trends in Differential Equations, Control Theory and Optimization, pages 201 – 214. World Scientific Publishing Co, August 2016.
  * [15] J-M. Lasry and P-L. Lions.  Mean field games. 1 – the stationary case.  C. R.Acad. Sci. Paris, Ser. I, 343(9):619 – 625, March 2006.
  * [16] J-M. Lasry and P-L. Lions.  Mean field games. 2 – finite horizon and optimal control.  C.R. Acad. Sci. Paris, Ser. I, 343(10):679 – 684, July 2006.
  * [17] J-M. Lasry and P-L. Lions.  Mean Field Games.  Jpn J. Math., 2(1):229–260, October 2007.
  * [18] Stefano Merler, Marco Ajelli, Andrea Pugliese, and Neil M. Ferguson.  Determinants of the spatiotemporal dynamics of the 2009 h1n1 pandemic in europe: Implications for real-time modelling.  PLOS Computational Biology, 7:1–13, 09 2011.
  * [19] Dina Mistry, Maria Litvinova, Ana Pastore y Piontti, Matteo Chinazzi, Laura Fumanelli, Marcelo F. C. Gomes, Syed A. Haque, Quan-Hui Liu, Kunpeng Mu, Xinyue Xiong, M. Elizabeth Halloran, Ira M. Longini Jr. au2, Stefano Merler, Marco Ajelli, and Alessandro Vespignani.  Inferring high-resolution human mixing patterns for disease modeling, 2020\.
  * [20] R. Morton and K. H. Wickwire.  On the optimal control of a deterministic epidemic.  Advances in Applied Probability, 6(4):622–635, 1974.
  * [21] Dutta R, Gomes SN, Kalise D, and Pacchiardi L.  Using mobility data in the design of optimal lockdown strategies for the covid-19 pandemic.  PLoS Comput Biol, 17(8), August 2021.
  * [22] Igor Swiecicki, Thierry Gobron, and Denis Ullmo.  Schrödinger approach to mean field games.  Phys. Rev. Lett., 116:128701, Mar 2016.
  * [23] Denis Ullmo, Igor Swiecicki, and Thierry Gobron.  Quadratic mean field games.  Physics Reports, 799:1–35, 2019.  Quadratic mean field games.
  * [24] K.H. Wickwire.  Optimal isolation policies for deterministic and stochastic epidemics.  Mathematical Biosciences, 26(3):325–346, 1975.