# Clique Is Hard on Average for Sherali-Adams
with Bounded Coefficients††thanks: This is the full-length version of a paper
with the title _“Clique Is Hard on Average for Unary Sherali-Adams”_ that
appeared in the _Proceedings of the 64th Annual IEEE Symposium on Foundations
of Computer Science (FOCS ’23)_.

Susanna F. de Rezende
Lund University Aaron Potechin
University of Chicago Kilian Risse
EPFL

###### Abstract

We prove that Sherali-Adams with polynomially bounded coefficients requires
proofs of size $n^{\Omega(d)}$ to rule out the existence of an
$n^{\Theta(1)}$-clique in Erdős-Rényi random graphs whose maximum clique is of
size $d\leq 2\log n$. This lower bound is tight up to the multiplicative
constant in the exponent. We obtain this result by introducing a technique
inspired by pseudo-calibration which may be of independent interest. The
technique involves defining a measure on monomials that precisely captures the
contribution of a monomial to a refutation. This measure intuitively captures
progress and should have further applications in proof complexity.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Result
    2. 1.2 Organization
  2. 2 Preliminaries
    1. 2.1 Semantic Sherali-Adams
    2. 2.2 Graph Theory
    3. 2.3 Clique Formula
  3. 3 Main Theorem and Proof Overview
    1. 3.1 Our Pseudo-Measure
    2. 3.2 Expected Behavior of Our Pseudo-Measure
    3. 3.3 Edge Axioms Should Have Small Measure
    4. 3.4 Rectangles Should Be Approximately Non-Negative
  4. 4 Cores
    1. 4.1 Cores and Boundaries
    2. 4.2 Proof of Theorem 4.4
  5. 5 Well-Behaved Graphs
  6. 6 Clique Is Hard on Well-Behaved Graphs
    1. 6.1 Axioms Have Small Measure
    2. 6.2 All Rectangles Are Approximately Non-Negative
  7. 7 The Measure Is Concentrated on Good Rectangles
    1. 7.1 Concentration of the Main Sum and Bounding the Boundary Sums
    2. 7.2 Bounds for All Good Rectangles
  8. 8 Random Graphs Are Well-Behaved
    1. 8.1 Random Graphs Have Bounded Common Neighborhoods
    2. 8.2 Random Graphs Have Bounded Character Sums
    3. 8.3 Probabilistic Bound on Sums of Fourier Characters
  9. 9 Concluding Remarks
  10. A Explicit Characterization of $E^{\star}_{F}$

##  1 Introduction

The problem of identifying a maximum clique in a given graph, that is, finding
a fully connected subgraph of maximum size, is one of the fundamental problems
of theoretical computer science. Already mentioned by Cook [Coo71] in his
seminal paper introducing the theory of NP-complete problems, it was one of
the first combinatorial problems proven NP-hard by Karp [Kar72]. Building on
the PCP theorem this result was later strengthened to even rule out polynomial
time algorithms that approximate the maximum clique size within a factor of
$n^{1-\varepsilon}$ [Hås99, Zuc07], unless $\textbf{P}=\textbf{NP}$.

A related problem is $k$-clique: given an $n$-vertex graph, determine whether
it contains a clique of size $k$. This problem can be solved in time
$O(n^{k})$ by iterating over all subsets of vertices of size $k$ and checking
whether one of them is a clique. This naïve algorithm is essentially the
fastest known; a clever use of fast matrix multiplication [NP85] allows a
slight improvement upon the constant in the exponent but no algorithms with a
sublinear dependence on $k$ in the exponent are known.

If we only assume $\textbf{P}\neq\textbf{NP}$, it is unknown whether there are
faster algorithms for $k$-clique. However, improving upon the linear
dependence on $k$ in the exponent would disprove the exponential time
hypothesis [CHKX04] and getting rid of the dependence on $k$ altogether would
imply that the class of fixed parameter tractable problems collapses to
$\textbf{W}[1]$ [DF95]. Hence, if one is willing to make the strong assumption
that the exponential time hypothesis holds, then the naïve algorithm has
essentially optimal running time in the worst-case.

Besides studying $k$-clique in the worst-case, one may consider it in the
average-case setting. Suppose the given graph is an Erdős-Rényi graph with
edge probability around the threshold of containing a $k$-clique. Does
$k$-clique require time $n^{\Omega(k)}$ on such graphs? Or, even less
ambitiously, is there an algorithm running in time $n^{o(k)}$ that decides the
$n^{\varepsilon}$-clique problem on such graphs? It is unlikely that the
hardness of such average-case questions can be based on worst-case hardness
assumptions such as $\textbf{P}\neq\textbf{NP}$ or the exponential time
hypothesis [BT06]. They are, in fact, being used as hardness assumptions
themselves: the _planted clique conjecture_ states that
$n^{1/2-\varepsilon}$-clique requires time $n^{\Omega(\log n)}$ on Erdős-Rényi
graphs with edge probability $1/2$.

In order to obtain _unconditional_ lower bounds – that do not rely on hardness
assumptions – for such average-case questions, we focus on limited models of
computation. This approach has turned out to be quite fruitful and several
results of this form have emerged over the past few decades. For Boolean
circuits, Rossman [Ros08, Ros10] proved two remarkable results: he showed that
monotone circuits, i.e., circuits consisting of $\vee$ and $\wedge$ gates
only, as well as circuits of constant depth require size $\Omega(n^{k/4})$ to
refute the existence of a $k$-clique in the average-case setting.

Instead of studying circuits, it is also possible to approach this problem
through the lens of proof complexity. Very broadly, proof complexity studies
certificates of unsatisfiability of propositional formulas. As we cannot argue
about certificates of unsatisfiability in general we consider certificates of
a certain form, or in terms of proof complexity, refutations in a given proof
system. For instance, if we prove that any certificate in a proof system $P$
that witnesses that a given $n$-vertex graph contains no $k$-clique requires
length $n^{\Omega(k)}$ on average, then we immediately obtain average-case
$n^{\Omega(k)}$ running time lower bounds for any algorithm whose trace can be
interpreted as a proof in the system $P$. It is often the case that state-of-
the-art algorithms can be captured by seemingly simple proof systems, as was
shown to be the case for clique algorithms [ABdR+21].

It is often the case that weak proof systems are sensitive to the precise
encoding of combinatorial principles. The $k$-clique formula is no exception:
it is somewhat straightforward to prove almost optimal $n^{\Omega(k)}$
resolution size lower bounds for the less usual binary encoding of the
$k$-clique formula [LPRT17] and these lower bounds can even be extended to an
$n^{\Omega(k)}$ lower bound for the Res($s$) proof system for constant $s$
[DGGM20]. For the more natural unary encoding not much is known. There are
essentially optimal $n^{\Omega(k)}$ average-case size lower bounds for regular
resolution [ABdR+21, Pan21a] and tree-like resolution [BGLR12, Lau18]. For
resolution, there are two average-case lower bounds that hold in different
regimes: for $n^{5/6}\ll k\leq n/3$, Beame et al. [BIS07] proved an average-
case $\exp(n^{\Omega(1)})$ size lower bound and for $k\leq n^{1/3}$, Pang
[Pan21a] proved a $2^{k^{1-o(1)}}$ lower bound. It is a long standing open
problem, mentioned, e.g., in [BGLR12], to prove an unconditional
$n^{\Omega(k)}$ resolution size lower bound for the unary encoding – even in
the worst case.

Little is known about the average-case hardness of the $k$-clique formula in
the semi-algebraic setting. There are optimal degree lower bounds for $k\leq
n^{1/2-\varepsilon}$ for the Sum-of-Squares proof system [MPW15, BHK+19,
Pan21b], but there are no non-trivial lower bounds on size. For
Nullstellensatz, however, if restricted to not use dual variables, then size
lower bounds follow by a simple syntactic argument [Mar08]. Prior to our work
no other size lower bounds were known for algebraic or semi-algebraic proof
systems.

###  1.1 Our Result

In this work we establish that Sherali-Adams [SA94, DM13] with polynomially
bounded coefficients requires size $n^{\Omega(D)}$ to refute the
$n^{1/100}$-clique formula on random graphs whose maximum clique size is of
size $D\leq 2\log n$. Qualitatively this establishes the planted clique
conjecture for Sherali-Adams with polynomially bounded coefficients. This is
the first size lower bound on the clique formula for a semi-algebraic proof
system.

######  Theorem 1.1 (Informal).

For all integers $n\in\mathbb{N}^{+}$ and $D\leq 2\log n$, if
$G\sim\mathcal{G}(n,n^{-2/D})$ is an Erdős-Rényi random graph, then it holds
asymptotically almost surely that Sherali-Adams with polynomially bounded
coefficients requires size at least $n^{\Omega(D)}$ to refute the claim that
$G$ contains a clique of size $k$, for any $k\leq n^{1/67}$.

Note that Sherali-Adams with polynomially bounded coefficients is stronger
than unary Sherali-Adams and is incomparable to resolution [GHJ+22]. Our
result further applies to the SubCubeSums proof system [FMSV23] as our proof
strategy gives a lower bound on the sum of the magnitude of the coefficients
of a Sherali-Adams refutation, ignoring Boolean axioms.

Let us stress that the size lower bound holds regardless of the degree of the
refutation. This is a somewhat unique feature of our technique – all other
lower bound strategies for Sherali-Adams and Sum-of-Squares are tailored to
proving degree lower bounds, which, if strong enough, imply size lower bounds
by the size-degree relation [AH19]. Since the clique formula has refutations
of degree $D$ we cannot expect to obtain size lower bounds through this
connection for $D\leq\sqrt{n}$. We therefore introduce a new technique,
inspired by pseudo-calibration [BHK+19], that is more refined – for any
monomial $m$, of arbitrary degree, we determine a lower bound on the size of
the smallest bounded-coefficient Sherali-Adams derivation of $m$.

###  1.2 Organization

The rest of this paper is organized as follows. In Section 2 we introduce some
basic terminology to then outline our proof strategy in Section 3 where we
also attempt to convey some intuition. With the motivation at hand from
Section 3 we then go on to define the central combinatorial concept of a
_core_ of a graph in Section 4 and a notion of pseudorandomness in Section 5.
We proceed in Section 6 to prove the main theorem for any graph satisfying our
notion of pseudorandomness, but postpone the proof of one of the main lemmas
to Section 7. Finally, in Section 8, we show that a random graph satisfies our
pseudorandomness property and conclude with some open problems in Section 9.

##  2 Preliminaries

Natural logarithms (base $\mathrm{e}$) are denoted by $\ln$, whereas base $2$
logarithms are denoted by $\log$. For integers $n\geq 1$ we introduce the
shorthand $[n]=\\{1,2,\ldots,n\\}$ and sometimes identify singletons $\\{u\\}$
with the element $u$. Let $\binom{S}{\ell}$ denote the set of subsets of $S$
of size $\ell$ and, for a given a random variable $X$ and an event $P$, we
denote by $\mathbbm{1}_{P}(X)$ the indicator random variable that is $1$ if
$P$ holds and $0$ otherwise.

###  2.1 Semantic Sherali-Adams

Let $\mathcal{P}=\\{p_{1}=0,\ldots,p_{m}=0\\}$ be a polynomial system of
equations over Boolean variables $x_{1},\ldots,x_{n}$ and their twin variables
$\bar{x}_{1},\ldots,\bar{x}_{n}$. Denote by

$\displaystyle B_{n}=\\{x_{i}(1-x_{i})\mid
i\in[n]\\}\cup\\{\bar{x}_{i}(1-\bar{x}_{i})\mid
i\in[n]\\}\cup\\{1-\bar{x}_{i}-{x}_{i}\mid i\in[n]\\}$ (2.1)

the corresponding Boolean axioms and negation axioms and let $I_{B_{n}}$
denote the ideal generated by $B_{n}$, that is, $I_{B_{n}}$ consists of all
polynomials of the form $\sum_{j}r_{j}q_{j}$ where the $r_{j}$ are arbitrary
polynomials and $q_{j}\in B_{n}$. For an ideal $I$ and polynomials $p$ and $q$
we write $p\equiv q\mod I$ if $p-q\in I$.

A _semantic Sherali-Adams refutation of $\mathcal{P}$_ is a sequence of
polynomials $(g_{1},\ldots,g_{m},f_{0})$ such that $f_{0}$ is of the form

$f_{0}=\sum_{\begin{subarray}{c}A,B\subseteq[n]\\\ \alpha_{A,B}\geq
0\end{subarray}}\alpha_{A,B}\prod_{i\in A}x_{i}\prod_{i\in B}\bar{x}_{i}$
(2.2)

and it holds that

$\sum_{j\in[m]}g_{j}p_{j}+f_{0}\equiv-1\mod I_{B_{n}}\enspace.$ (2.3)

The _size_ of a refutation $\pi$, denoted by $\operatorname{Size}(\pi)$, is
the sum of the size of the binary encodings of the non-zero coefficients on
the left hand side of (2.3) when all polynomials are expanded as a sum of
monomials (without cancellations), while the _coefficient size_ of $\pi$ is
the sum of the magnitudes of the coefficients of the aforementioned monomials.

We note that this definition differs from that of the usual Sherali-Adams
proof system [SA94, DM13] where Boolean axioms and negation axioms are written
out explicitly and the size is measured taking also these axioms into account.
We are not the first to disregard the size contribution of these axioms: most
size lower bounds for Sherali-Adams also apply in this setting. The question
of whether these two size measures are polynomially related was raised
explicitly in [FHR+24], where the above system is referred to as _succinct_
Sherali-Adams, and remains open.

To verify that semantic Sherali-Adams is a Cook-Reckhow proof system, we need
to check that a semantic Sherali-Adams refutation is verifiable in time
polynomial in the size of the refutation. This was originally shown in
[FHR+24], but we provide a simpler and more direct proof of this fact.

######  Proposition 2.1.

Let $\mathcal{P}$ be a polynomial system of equations over $n$ Boolean
variables and their twin variables. A semantic Sherali-Adams refutation $\pi$
of $\mathcal{P}$ can be verified in time
$O\bigl{(}\operatorname{Size}(\pi)^{2}\cdot\operatorname{poly}(n)\bigr{)}$.

###### Proof.

Denote the coefficient of a monomial $m$ in a polynomial $p\in\mathcal{P}$ by
$\gamma_{p}(m)$. Further, given a monomial $m$, let $\mathbbm{1}_{m}$ be the
vector of length $2^{n}$, indexed by assignments $\rho\in\\{0,1\\}^{n}$, that
corresponds to the truth table of $m$: the entry with index $\rho$ is $1$ if
the monomial $m$ evaluates to $1$ under $\rho$ and $0$ otherwise. We denote
the all-ones vector $\mathbbm{1}_{1}$ by $\mathbbm{1}$, and the all-zero
vector $\mathbbm{1}_{0}$ by $\varmathbb{0}$.

With this notation at hand we may equivalently define a semantic Sherali-Adams
refutation of $\mathcal{P}$ as a sequence of rational vectors
$(\beta_{1},\ldots,\beta_{|\mathcal{P}|},\alpha)$ indexed by multilinear
monomials with $\alpha\geq 0$ and

$\displaystyle\sum_{p\in\mathcal{P}}\sum_{m_{1},m_{2}}\beta_{p}(m_{1})\cdot\gamma_{p}(m_{2})\cdot\mathbbm{1}_{m_{1}\cdot
m_{2}}-$
$\displaystyle\sum_{m}\alpha(m)\cdot\mathbbm{1}_{m}-\mathbbm{1}=\varmathbb{0}\enspace.$
(2.4)

View the left hand side as a vector $\pi$ indexed by assignments
$\rho\in\\{0,1\\}^{n}$. Since the vector $\pi$ is rational, we have that $\pi$
is the $0$-vector if and only if the inner product is $0$, that is,
$\langle\pi,\pi\rangle=0$. This can be efficiently checked by expanding the
inner product

$\displaystyle\begin{split}\langle\pi,\pi\rangle&=\Big{(}\sum_{p\in\mathcal{P}}\sum_{\begin{subarray}{c}m_{1},m_{2}\end{subarray}}\beta_{p}(m_{1})\cdot\gamma_{p}(m_{2})\cdot\mathbbm{1}_{m_{1}\cdot
m_{2}}\Big{)}^{2}+\Big{(}\sum_{m}\alpha(m)\cdot\mathbbm{1}_{m}\Big{)}^{2}+\langle\mathbbm{1},\mathbbm{1}\rangle\\\
&\quad{}-2\sum_{p\in\mathcal{P}}\sum_{m_{1},m_{2}}\sum_{m}\alpha(m)\cdot\beta_{p}(m_{1})\cdot\gamma_{p}(m_{2})\cdot\langle\mathbbm{1}_{m_{1}\cdot
m_{2}},\mathbbm{1}_{m}\rangle\\\
&\quad{}-2\sum_{p\in\mathcal{P}}\sum_{m_{1},m_{2}}\beta_{p}(m_{1})\cdot\gamma_{p}(m_{2})\cdot\langle\mathbbm{1}_{m_{1}\cdot
m_{2}},\mathbbm{1}\rangle+2\sum_{m}\alpha(m)\cdot\langle\mathbbm{1}_{m},\mathbbm{1}\rangle\enspace.\end{split}$
(2.5)

Observe that in the above expression all the inner products can be efficiently
computed. Hence checking whether $\pi$ is indeed a valid semantic Sherali-
Adams refutation boils down to verifying that the above sum of bounded
rationals is equal to $0$. ∎

As the distinction between semantic Sherali-Adams and Sherali-Adams is not
essential for what follows, we refer to semantic Sherali-Adams simply as
Sherali-Adams going forward. A Sherali-Adams refutation $\pi$ of $\mathcal{P}$
is a _Sherali-Adams refutation with $f(n)$-bounded-coefficients_ if the
magnitude of all coefficients is bounded by $f(n)$ and we call $\pi$ a
_Sherali-Adams refutation with $\operatorname{poly}$-bounded-coefficients_ if
for some constant $c>0$ it holds that $\pi$ is a Sherali-Adams refutation with
$n^{c}$-bounded-coefficients. Let us record the following observation.

######  Proposition 2.2.

If Sherali-Adams requires coefficient size $s$ to refute $\mathcal{P}$, then
Sherali-Adams with $f(n)$-bounded-coefficients requires size $s/f(n)$ to
refute $\mathcal{P}$.

###### Proof.

As every coefficient in an $f(n)$-bounded-coefficient refutation is bounded by
$f(n)$, there need to be at least $s/f(n)$ monomials with a non-zero
coefficient. ∎

_Unary Sherali-Adams_ is a subsystem of Sherali-Adams where all coefficients
of monomials are either $+1$ or $-1$ and the right-hand-side of Equation 2.3
is any negative integer

$\sum_{j\in[m]}g_{j}p_{j}+f_{0}\equiv-M\mod I_{B_{n}}\enspace,$ (2.6)

where $f_{0}$ is again a non-negative sum of monomials.

######  Proposition 2.3.

If Sherali-Adams requires coefficient size $s$ to refute $\mathcal{P}$, then
unary Sherali-Adams requires size at least $s$ to refute $\mathcal{P}$.

###### Proof.

We can transform any unary Sherali-Adams refutation of size $s$, summing to an
integer $-M$, to a Sherali-Adams refutation of coefficient size at most $s$ by
dividing the left hand side by $M\geq 1$. ∎

###  2.2 Graph Theory

Before defining the $k$-clique formula, we introduce some terminology and
notation that we use throughout the paper.

Unless stated otherwise, $G$ denotes a $k$-partite graph with partitions
$V_{1},\ldots,V_{k}$ of size $n$ each. We call a partition $V_{i}$ a _block_
and, for $S\subseteq[k]$, denote by $V_{S}$ the vertices in blocks in $S$,
that is, $V_{S}=\bigcup_{i\in S}V_{i}$. For disjoint sets $W_{1},\ldots,W_{s}$
we let a _tuple_ $t=(w_{1},\ldots,w_{s})$ be a sequence of vertices satisfying
$w_{i}\in W_{i}$ for all $i\in[s]$. All tuples we consider are defined with
respect to the partition $V_{1},\ldots,V_{k}$, though, at times, may only be
defined over a subset of the blocks, that is, not all tuples are of size $k$.
For a tuple $t=(v_{1},\ldots,v_{k})$ and a set $S\subseteq[k]$ we denote the
projection of $t$ onto $S$ by $t_{S}=(v_{i}\,\mid\,i\in S)$. An _$s$ -tuple_
is a tuple of size $s$ and sometimes it is convenient for us to think of a
tuple as a set of vertices. We take the liberty to interchangeably identify a
tuple as a sequence as well as a set and hope that this causes no confusion.

A set $Q$ of tuples is a _rectangle_ if for some $S\subseteq[k]$ the set $Q$
can be written as the Cartesian product of sets $U_{i}\subseteq V_{i}$ for
$i\in S$, i.e., $Q=\bigtimes_{i\in S}U_{i}$; in other words, $Q$ contains all
tuples $t=(u_{i}\,\mid\,i\in S)$ satisfying $u_{i}\in U_{i}$ for all $i\in S$.
Rectangles, unless explicitly stated, consist of $k$-tuples only, that is,
$Q=\bigtimes_{i\in[k]}U_{i}$. Given a rectangle $Q$ and a set $S\subseteq[k]$
we let $Q_{S}$ be the projection of $Q$ onto the blocks in $S$: if
$Q=\bigtimes_{i\in[k]}U_{i}$, then $Q_{S}=\bigtimes_{i\in S}U_{i}$ and, in
particular, we have $Q_{i}=U_{i}$ for $i\in[k]$.

While $G$ always denotes a large graph, the graphs $H$ and $F$ denote small
graphs: throughout the paper $H$ and $F$ are graphs on $k$ labeled vertices.
Usually these graphs have a small vertex cover and graphs denoted by $F$
furthermore have many isolated vertices. For a graph $H$ we denote the minimum
vertex cover by $\operatorname*{vc}(H)$ and sometimes refer to $H$ as a
_pattern graph_ , whereas $F$ is usually a _core graph_ (see Section 4). We
denote by $\mathcal{H}$ the set of graphs on $k$ labeled vertices and for a
parameter $i\in\mathbb{N}^{+}$ let $\mathcal{H}_{i}\subseteq\mathcal{H}$ be
the family of graphs with a minimum vertex cover of size at most $i$, that is,
all graphs $H\in\mathcal{H}_{i}$ satisfy $\operatorname*{vc}(H)\leq i$.

We record here two simple lemmas about graphs that will come in handy
throughout the paper.

######  Lemma 2.4.

There are at most $2^{c\log k+b(c-(b+1)/2)}\leq 2^{c(b+\log k)}$ graphs $H$
over $k$ vertices with a vertex cover of size $b$ and
$\bigl{\lvert}V\bigl{(}E(H)\bigr{)}\bigr{\rvert}\leq c$.

###### Proof.

We first choose the $b$ vertices from the $k$ vertices that form the vertex
cover. Then, from the remaining $k-b$ vertices, we choose $c-b$ vertices that
may be incident to an edge. We can add edges that are incident to the vertex
cover and the other $c-b$ vertices and thus get that there are at most

$\displaystyle\binom{k}{b}\binom{k-b}{c-b}2^{\binom{b}{2}}2^{b(c-b)}\leq
2^{c\log k+b(c-(b+1)/2)}$ (2.7)

many such graphs. ∎

Recall that a maximal matching of $H$ is a matching that cannot be extended in
$H$.

######  Proposition 2.5.

Any maximal matching in a graph $H$ is of size at least
$\lceil\operatorname*{vc}(H)/2\rceil$.

###### Proof.

Since $M$ is maximal, all edges of $H$ are incident to $V(M)$. Thus the set
$V(M)$ is a vertex cover of $H$. ∎

The distribution of random graphs we consider in this paper is a $k$-partite
version of the Erdős-Rényi distribution. For a fixed set $V$ of $n$ vertices
and a real number $0\leq p\leq 1$, the Erdős-Rényi distribution
$\mathcal{G}(n,p)$ is the distribution of random graphs on vertex set $V$
where every potential edge $e=\\{u,v\\}$, for vertices $u\neq v$, is sampled
independently with probability $p$. As was done in [BIS07, ABdR+21], we work
with the block model, which is defined as follows. Given $k$ blocks
$V_{1},\ldots,V_{k}$ of size $n$ and a real number $0\leq p\leq 1$, we denote
by $\mathcal{G}(n,k,p)$ the distribution over graphs on the vertex set
$V_{[k]}$ defined by sampling each edge $e=\\{u,v\\}$ independently with
probability $p$ if $u$ and $v$ are in distinct blocks. We sometimes refer to
such pairs of vertices $\\{u,v\\}$ as _potential edges_. Edges within the same
block are never included and hence $\mathcal{G}(n,k,p)$ is a distribution over
$k$-partite graphs.

###  2.3 Clique Formula

Below we present an encoding of the $k$-clique formula on $k$-partite graphs
as a system of polynomial equations.

Given a $k$-partite graph $G$ with blocks $V_{1},\ldots,V_{k}$ of size $n$ we
define the _$k$ -clique formula over $G$_ stating that $G$ has a $k$-clique
(with one vertex per block) as follows. The formula is defined over $2kn$
variables: each vertex $v\in V_{[k]}$ is associated with two variables $x_{v}$
and $\bar{x}_{v}$. The intended meaning is that $x_{v}$ is $1$ if $v$ is in
the identified $k$-clique and $0$ otherwise, and $\bar{x}_{v}=1-x_{v}$. Since
we define the Sherali-Adams proof system (see Section 2.1) to operate modulo
the ideal generated by the Boolean axioms $y(1-y)$ and the negation axioms
$1-\bar{x}_{v}-x_{v}$, we do not need to explicitly include such axioms in the
formula.

For each block $V_{i}$ we introduce the _block axiom_ $\sum_{v\in
V_{i}}x_{v}-1=0$ stating that precisely one vertex from each block is chosen
and for each pair of vertices $\\{u,v\\}\not\in E(G)$ in distinct blocks we
introduce the _edge axiom_ $x_{u}x_{v}=0$ that ensures that non-neighbors are
not simultaneously selected. We note that we could also include edge axioms
for pairs of vertices in the same block but we choose not to since these are
easily derivable from the block axioms.

It should be evident that this formula is satisfiable modulo the Boolean and
the negation axioms if and only if there is a $k$-tuple $t$ such that the
vertex induced subgraph $G[t]$ is a clique.

We make two remarks about this choice of encoding. The first is that our lower
bound strategy is completely agnostic to the encoding of the block axioms. We
could equally well have considered the polynomial translation of the CNF
encoding, or the binary encoding, or any encoding of the constraints that one
vertex of each block should be chosen to be part of the clique.

The second remark is that, as argued in Beame, Impagliazzo and Sabharwal
[BIS07], the reason for choosing to define the formula over $k$-partite graphs
is that proving a lower bound for this encoding implies a lower bound for
other natural encodings. In particular, if we consider the $k$-clique formula
defined over a (not necessarily $k$-partite) graph $G=(V,E)$ on $kn$ vertices,
as the formula containing the axiom $\sum_{v\in V}x_{v}=k$ and edge axioms
$x_{u}x_{v}=0$ for each pair of vertices $\\{u,v\\}\not\in E$, then for any
equal-sized $k$-partition $V=V_{1}\,\dot{\cup}\,\cdots\,\dot{\cup}\,V_{k}$ it
holds that a lower bound for the $k$-clique formula on $G$ with this partition
implies the same lower bound for the non-$k$-partite formula.

######  Proposition 2.6 ([BIS07]).

Let $k,n\in\mathbb{N}^{+}$ be integer and let $G$ be a graph on $kn$ vertices.
Then the minimum Sherali-Adams coefficient size to refute the $k$-clique
formula over $G$ is bounded from below by the coefficient size required to
refute the $k$-clique formula defined with respect to any equal-sized
$k$-partition of $G$.

This proposition was proven in [BIS07] for resolution size, and it is
straightforward to see that it holds for Sherali-Adams coefficient size.
Indeed, it is enough to observe that the non-$k$-partite $k$-clique formula
can be easily derived from the $k$-partite $k$-clique formula.

##  3 Main Theorem and Proof Overview

The main result of this paper is a tight, up to constants in the exponent,
Sherali-Adams coefficient size lower bound for $k$-clique formulas over Erdős-
Rényi random graphs.

######  Theorem 3.1 (Main theorem).

Let $k$ and $D$ be functions of $n$ such that $D\leq 2\log n$ and $k\leq
n^{1/66}$. If ${G\sim\mathcal{G}(n,k,n^{-2/D})}$, then asymptotically almost
surely Sherali-Adams requires coefficient size $n^{\Omega(D)}$ to refute the
$k$-clique formula over $G$.

Note that Theorem 1.1 follows directly from Theorem 3.1 along with
Propositions 2.6 and 2.2, where we assume that the coefficient size is bounded
by a polynomial $n^{c}$ where $c$ is a constant independent of $D$. The main
result of the conference version of this paper [DRPR23] follows from Theorem
3.1 and Propositions 2.6 and 2.3.

In the rest of this section we outline our proof strategy. We intend to come
up with a so-called _pseudo-measure_ which lower bounds the coefficient size
of a Sherali-Adams refutation. Before we get ahead of ourselves let us define
what a pseudo-measure is.

######  Definition 3.2 (Pseudo-measure).

Let $\delta>0$ and $\mathcal{P}$ be a set of polynomials over the polynomial
ring $\mathbb{R}[x_{1},\ldots,x_{n},\bar{x}_{1},\ldots,\bar{x}_{n}]$. A linear
function
$\mu\colon\mathbb{R}[x_{1},\ldots,x_{n},\bar{x}_{1},\ldots,\bar{x}_{n}]\rightarrow\mathbb{R}$,
mapping polynomials to reals, is a _$\delta$ -pseudo-measure for
$\mathcal{P}$_ if for all monomials $m$ and all polynomials $p\in\mathcal{P}$
it holds that

  1. 1.

$\mu(1)=1$,

  2. 2.

$|\mu(m\cdot p)|\leq\delta$, and

  3. 3.

$\mu(m)\geq-\delta$.

A concept related to the notion of a pseudo-measure has previously appeared in
[PZ22] for the Nullstellensatz proof system over the reals. We also note that
in a recent work Hubáček, Khaniki and Thapen [HKT24] defined a similar notion
for Sherali-Adams with bounded degree. We have the following simple
proposition.

######  Proposition 3.3.

There is a $\delta$-pseudo-measure for $\mathcal{P}$ if and only if any
Sherali-Adams refutation of $\mathcal{P}$ requires coefficient size
$1/\delta$.

###### Proof.

Given a monomial $m$, let $\mathbbm{1}_{m}$ be the vector of length $2^{n}$,
indexed by assignments $\rho\in\\{0,1\\}^{n}$, that corresponds to the truth
table of $m$, that is, on index $\rho$ the vector $\mathbbm{1}_{m}$ is $1$ if
the monomial $m$ evaluates to $1$ on assignment $\rho$ and $0$ otherwise. We
denote the all-ones vector $\mathbbm{1}_{1}$ by $\mathbbm{1}$.

Let $\mathcal{P}$ be a polynomial system of equations over Boolean variables
$x_{1},\ldots,x_{n}$ and their twin variables
$\bar{x}_{1},\ldots,\bar{x}_{n}$. We denote the coefficient of a monomial $m$
in a polynomial $p\in\mathcal{P}$ by $\gamma_{p}(m)$. We may write a linear
program that searches for a Sherali-Adams refutation of $\mathcal{P}$ of
minimum coefficient size as

$\begin{array}[]{ll@{}ll}\text{minimize}&\displaystyle\sum_{m}\alpha({m})\hskip
5.0pt+\sum_{\begin{subarray}{c}p\in\mathcal{P}\end{subarray}}\sum_{\begin{subarray}{c}m\end{subarray}}\big{(}\beta^{+}_{p}(m)+\beta^{-}_{p}(m)\big{)}\\\
\text{subject
to}&\displaystyle\sum_{p\in\mathcal{P}}\sum_{\begin{subarray}{c}m_{1},m_{2}\end{subarray}}\big{(}\beta^{+}_{p}(m_{1})-\beta^{-}_{p}(m_{1})\big{)}\cdot\gamma_{p}(m_{2})\cdot\mathbbm{1}_{m_{1}\cdot
m_{2}}-&\displaystyle\sum_{m}\alpha(m)\cdot\mathbbm{1}_{m}=\mathbbm{1}\\\
&\displaystyle\alpha,\displaystyle\beta^{+},\displaystyle\beta^{-}\geq
0\enspace.\end{array}$ (3.1)

We appeal to duality to obtain the following dual program to the above. Denote
by $\mu$ the vector of dual variables of dimension $2^{n}$ and introduce for a
monomial $m$ the shorthand $\mu(m)=\mu^{T}\mathbbm{1}_{m}$ and for a
polynomial $q=\sum_{m}\gamma(m)\cdot m$ let
$\mu(q)=\sum_{m}\gamma(m)\cdot\mu(m)$. The dual to the above linear program
may be expressed as

$\begin{array}[]{ll@{}ll}\text{maximize}&\displaystyle\mu(1)\\\\[10.0pt]
\text{subject to}&\displaystyle\mu(m)\geq-1&\forall m\\\\[7.0pt]
&\displaystyle\left|\mu(m\cdot p)\right|\leq 1&\forall m,\forall
p\in\mathcal{P}\enspace.\end{array}$ (3.2)

Thus the notion of a pseudo-measure for $\mathcal{P}$ is indeed the dual
object of a Sherali-Adams refutation of $\mathcal{P}$ with small coefficient
size. By appealing to strong duality and normalizing by $\mu(1)$ the claim
follows. ∎

###  3.1 Our Pseudo-Measure

In what follows we define our pseudo-measure $\mu$ for the $k$-clique formula.
We may think of $\mu$ as a progress measure: it assigns to each monomial a
real value which can be thought of as the contribution of this monomial
towards the refutation of the $k$-clique formula. Thus, intuitively, we would
like to associate each monomial with the fraction of potentially satisfying
assignments that it rules out. In order to define this a bit more formally,
let us introduce the set of potentially satisfying assignments.

We say that an assignment $\alpha$ is _potentially satisfying_ for the
$k$-clique formula if there is a graph $G$ such that the $k$-clique formula
defined over $G$ is satisfied by $\alpha$. This set of assignments can be
easily characterized: if we associate each $k$-tuple $t$ with the assignment
$\rho_{t}$ that sets all variables $x_{u}$ to $1$ if $u\in t$ and to $0$
otherwise, then the set of potentially satisfying assignments of the
$k$-clique formula is

$\displaystyle\\{\rho_{t}\mid t\in V_{1}\times V_{2}\times\cdots\times
V_{k}\\}\enspace.$ (3.3)

We say that a monomial $m$ _rules out_ an assignment $\rho$ if $\rho(m)=1$. As
there is a one-to-one correspondence between potentially satisfying
assignments and tuples, it is convenient to think of the tuples that a
monomial rules out. We thus associate each monomial $m$ with the set

$\displaystyle Q(m)=\\{t\mid\rho_{t}(m)=1\\}$ (3.4)

of ruled out $k$-tuples. Note that $Q(1)$ is the set of all tuples, that is,
$Q(1)=V_{1}\times V_{2}\times\cdots\times V_{k}$ and the set $Q(x_{u}x_{v})$
associated with an edge axiom $x_{u}x_{v}$ consists of all $k$-tuples that
contain the vertices $u$ and $v$.

More generally, it is not too hard to see that the set of ruled out tuples of
a monomial is a rectangle and that for each rectangle $Q$ there is at least
one monomial $m$ such that $Q$ is the set of tuples ruled out by $m$. We thus
often discuss rectangles and it is implicitly understood that if a statement
holds for all rectangles, then it also holds for all monomials. Finally,
observe that if a monomial $m$ satisfies $m=m_{1}\cdot m_{2}$, then
$Q(m)\subseteq Q(m_{1})$.

For intuition we will now discuss two naïve, and fatally flawed, attempts to
define a pseudo-measure. For our first attempt, we simply associate each
monomial with the fraction of ruled out tuples, that is we map a monomial $m$
to

$\displaystyle\frac{|Q(m)|}{|Q(1)|}=n^{-k}\cdot|Q(m)|\enspace.$ (3.5)

This measure maps the monomial $1$ to $1$ and is clearly non-negative and
hence satisfies Items 1 and 3 of Definition 3.2 for any $\delta>0$.
Furthermore, again for any $\delta>0$, it satisfies Item 2 of Definition 3.2
for the block axioms. Only the edge axioms cause trouble: the rectangle
$Q(x_{u}x_{v})$ associated with the edge axiom $x_{u}x_{v}$ is a $n^{-2}$
fraction of all tuples. As such, according to Proposition 3.3, this pseudo-
measure may only gives us an $n^{2}$ coefficient size lower bound—not quite
what we are after.

We may try to remedy this by not associating a monomial $m$ with _all_ tuples
in $Q(m)$ but rather only with a subset of $Q(m)$ that depends on the graph
$G$. One very naïve attempt would be to associate $m$ with the number of
$k$-cliques that it rules out, that is, we may associate a monomial $m$ with
the normalized measure

$\displaystyle\tilde{\mu}(m)=n^{-k}\sum_{t\in
Q(m)}2^{\binom{k}{2}}\mathbbm{1}_{\\{t\text{ is a clique}\\}}(G)\enspace.$
(3.6)

This definition, at least _in expectation_ over $G\sim\mathcal{G}(n,k,1/2)$,
satisfies all properties of a pseudo-measure: the monomial $1$ is mapped to
$1$, the axioms are all mapped to $0$ and the measure is non-negative.

The obvious problem is that all graphs we consider do _not_ contain a
$k$-clique and hence everything (including the monomial $1$) is mapped to $0$.
Put differently, the main problem is that the random variable $\tilde{\mu}(1)$
over $G\sim\mathcal{G}(n,k,1/2)$ has too large variance. We reduce this
variance as pioneered by Barak et al. [BHK+19]: we expand Equation 3.6 in the
Fourier basis and truncate the resulting expression. A careful choice of the
truncation, along with some significant effort, allows us to argue that, on
the one hand, the measure associated with $1$ is large (i.e., the variance is
reduced) while, on the other hand, the measure associated with edge axioms is
still tightly concentrated around $0$ and that the measure is essentially non-
negative (i.e., the variance did not increase significantly). This measure
thus constitutes a valid pseudo-measure as defined in Definition 3.2 up to
normalization. In order to state the precise definition of our pseudo-measure
$\mu$ we need some notation.

If $p$ denotes the probability that a potential edge $e$ is present in the
graph, then the character $\chi_{e}(G)$ is defined by

$\displaystyle\chi_{e}(G)=\begin{cases}\frac{1-p}{p}&\text{if }e\in E(G)\\\
-1&\text{otherwise;}\end{cases}$ (3.7)

and for a set of potential edges $E$ we let $\chi_{E}(G)=\prod_{e\in
E}\chi_{e}(G)$. It is convenient for us to work with the above (non-standard)
basis as it allows us to easily cancel characters in case an edge is missing.
Observe that for $p=1/2$ this is the usual $\pm 1$ Fourier basis. First time
readers are advised to keep this case in mind for the remainder of the
article. Let us record some useful facts.

######  Proposition 3.4.

Let $k,\ell,n\in\mathbb{N}^{+}$, let $p>0$ and $G\sim\mathcal{G}(n,k,p)$. For
any potential edge $e$, sampled with probability $p$, it holds that
$\operatorname*{\mathbb{E}}_{G}[\chi_{e}(G)]=0$ and
$\operatorname*{\mathbb{E}}_{G}[\chi^{2\ell}_{e}(G)]=(1-p)(1+(\frac{1-p}{p})^{2\ell-1})$.
In particular, for $\ell=1$, we have
$\operatorname*{\mathbb{E}}_{G}[\chi^{2}_{e}(G)]=(1-p)/p$. A useful bound is
$\operatorname*{\mathbb{E}}_{G}[\chi^{2\ell}_{e}(G)]\leq p^{-2\ell}$. Finally,
observe that for any tuple $t$ we have that
$\sum_{E\subseteq\binom{t}{2}}\chi_{E}(G)$ is $p^{-\binom{k}{2}}$ if $t$ is a
clique and $0$ otherwise.

To concisely state our pseudo-measure we need some further notation. We
consider sums of tuples and want to treat edge sets that are equal up to the
mapping onto a $k$-tuple as the same. More precisely, if we have two
$k$-tuples
$t=(v_{1},\ldots,v_{k}),t^{\prime}=(v_{1}^{\prime},\ldots,v_{k}^{\prime})$ and
edge sets $E\subseteq\binom{t}{2}$ and
$E^{\prime}\subseteq\binom{t^{\prime}}{2}$ such that $\\{v_{i},v_{j}\\}\in E$
if and only if $\\{v_{i}^{\prime},v_{j}^{\prime}\\}\in E^{\prime}$, then we
want to identify $E$ and $E^{\prime}$ as the same edge set. To this end we
consider _pattern graphs $H$_ (similar to the _shape graphs_ in the
terminology of [BHK+19]) over the vertex set $[k]$. For a tuple
$t=(v_{1},\ldots,v_{k})$ and a pattern graph $H$ we let $H(t)$ be the edge set
that contains the edge $\\{v_{i},v_{j}\\}$ if and only if the edge $\\{i,j\\}$
is present in $H$. See Figure 1 for an illustration.

Figure 1: A pattern graph $H$ mapped onto a tuple $t=(v_{1},\ldots,v_{k})$

With this notation at hand we define our pseudo-measure as

$\displaystyle\mu(m)=\mu_{d}\bigl{(}Q(m)\bigr{)}=n^{-k}\sum_{t\in
Q(m)}\sum_{\begin{subarray}{c}H\\\ \operatorname*{vc}(H)\leq
d\end{subarray}}\chi_{H(t)}(G)\enspace,$ (3.8)

where the second sum is over all graphs $H$ over $[k]$ vertices with vertex
cover at most $d$, and $d=\eta D$ is a small constant $\eta>0$ times the
maximum clique size of $G$.

Observe that Boolean axioms, the negation axioms and the block axioms
multiplied by an arbitrary monomial are all mapped to $0$ by $\mu$. Hence it
remains to prove that the measure $\mu$ maps the constant $1$ monomial to a
large value, that $\mu$ is small on subrectangles of edge axioms, i.e., any
edge axiom multiplied by a monomial is mapped to a small value, and that all
monomials are mapped to an approximately non-negative value.

By inspecting the second moment of $\mu(1)$ it is not too hard to see that
there is quite a bit of freedom on how to choose the truncation in the
definition of $\mu$ while maintaining the property that $\mu(1)=1\pm
n^{-\Omega(1)}$ asymptotically almost surely. However, ensuring that the edge
axioms are associated with small measure is more delicate. Here we heavily
rely on our choice to truncate according to the minimum vertex cover. More
specifically we rely on two crucial properties of graphs $H$ satisfying
$\operatorname*{vc}(H)=d$: firstly, we use the fact that such graphs contain a
matching of size $\lceil d/2\rceil$ (see Proposition 2.5) and, secondly, that
the family of these graphs satisfies a monotonicity property which leads to a
useful partition of this family. For more details about this partition we
refer to Section 4. Let us mention that it is conceivable that one could
increase the bound on $k$ for which our results hold by truncating according
to the size of the maximum matching. As we do not know how to define the above
mentioned partition with respect to the maximum matching we truncate according
to the minimum vertex cover.

In the following sections we try to present some intuition as to why $\mu_{d}$
is a pseudo-measure up to normalization, that is, why it satisfies Definition
3.2 where Item 1 is relaxed to approximately $1$. In Section 3.2 we verify
that $G$ sampled from $\mathcal{G}(n,k,1/2)$ asymptotically almost surely
satisfies $\mu(1)=\mu_{d}(\bigtimes_{i\in[k]}V_{i})=1\pm n^{-\Omega(1)}$. As
mentioned, this follows by a straightforward second moment argument. In
Section 3.3 we outline why any subrectangle $Q$ of an edge axiom satisfies
$|\mu_{d}(Q)|\leq n^{-\Omega(d)}$. This proof motivates the definitions in
Sections 4 and 5. Finally, in Section 3.4, we provide some high-level overview
of how to prove that any rectangle $Q$ is mapped to an approximately non-
negative value, that is, it holds that $\mu_{d}(Q)\geq-n^{-\Omega(d)}$. This
is the most technically challenging part of the paper.

###  3.2 Expected Behavior of Our Pseudo-Measure

The measure $\mu_{d}(Q)$ of any rectangle $Q$ satisfies

$\displaystyle\operatorname*{\mathbb{E}}_{G}[\mu_{d}(Q)]=n^{-k}\sum_{t\in
Q}\sum_{H\in\mathcal{H}_{d}}\operatorname*{\mathbb{E}}_{G}[\chi_{H(t)}(G)]=n^{-k}\sum_{t\in
Q}\operatorname*{\mathbb{E}}_{G}[\chi_{\emptyset(t)}(G)]=n^{-k}|Q|\enspace.$
(3.9)

In particular, as $Q(1)=\bigtimes_{i\in[k]}V_{i}$, it holds that
$\operatorname*{\mathbb{E}}_{G}[\mu(1)]=1$. In what follows we show that, for
$p=1/2$, the measure is somewhat concentrated around the expected value. The
concentration, though, is far from enough to perform a union bound over all
rectangles to argue that the measure behaves as expected on all rectangles
simultaneously.

We show that the measure concentrates by an application of Chebyshev’s
inequality. To this end we analyze the second moment: for $p=1/2$ we have

$\displaystyle\operatorname*{\mathbb{E}}_{G}[\mu_{d}^{2}(Q)]$
$\displaystyle=n^{-2k}\cdot\sum_{H\in\mathcal{H}_{d}}\sum_{t,t^{\prime}\in
Q}\operatorname*{\mathbb{E}}_{G}[\chi_{H(t)}(G)\chi_{H(t^{\prime})}(G)]$
(3.10)
$\displaystyle=n^{-2k}\cdot\sum_{H\in\mathcal{H}_{d}}\sum_{\begin{subarray}{c}t,t^{\prime}\in
Q:\\\
t_{V(E(H))}=t^{\prime}_{V(E(H))}\end{subarray}}\operatorname*{\mathbb{E}}_{G}[\chi_{H(t)}(G)\chi_{H(t^{\prime})}(G)]$
(3.11)
$\displaystyle=n^{-2k}\cdot\sum_{H\in\mathcal{H}_{d}}\big{|}\bigl{\\{}(t,t^{\prime})\colon
t,t^{\prime}\in Q\text{ and
}t_{V(E(H))}=t^{\prime}_{V(E(H))}\bigr{\\}}\big{|}$ (3.12)
$\displaystyle=n^{-2k}\cdot\sum_{H\in\mathcal{H}_{d}}|Q_{V(E(H))}|\cdot|Q_{[k]\setminus
V(E(H))}|^{2}$ (3.13) $\displaystyle\leq
n^{-k}|Q|\cdot\Big{(}1+\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}\\\
H\neq\emptyset\end{subarray}}n^{-|V(E(H))|}\Big{)}\enspace.$ (3.14)

A careful application of Lemma 2.4 allows us to bound the number of pattern
graphs $H$ we sum over in (3.14) to conclude that
$\operatorname*{\mathbb{E}}[\mu_{d}^{2}(Q)]=|Q|n^{-k}\big{(}1\pm
n^{-\Omega(1)}\big{)}$, as long as $k$ and $d$ are small. By virtue of
Chebyshev’s inequality we then conclude that $\mu(1)=1\pm n^{-\Omega(1)}$
asymptotically almost surely.

A natural attempt to prove that the measure is mostly non-negative is to
analyze higher moments in the hope that these are closely concentrated around
the (positive) expected value. The fundamental difficulty in analyzing the
pseudo-measure $\mu_{d}$ is that we have to analyze exponentially many
rectangles simultaneously. Since there is such a large number of rectangles,
for each input graph $G$, there will be some rectangles where the value of
$\mu_{d}$ differs considerably from the expected value.

For example, the measure on a rectangle $Q$ with only a few vertices $Q_{i}$
in some block $V_{i}$ heavily depends on the behavior of the edges incident to
the vertices in $Q_{i}$. Hence, if $Q_{i}$ is small enough, we expect large
deviations from the expected value. A slightly simplified, though more
concrete, example of this phenomenon goes as follows: let $v_{1}\in V_{1}$ and
$v_{2}\in V_{2}$, let $Q$ be the rectangle that consists of all tuples that
contain $v_{1}$ as well as $v_{2}$, and let $H$ be the graph with the single
edge $\\{1,2\\}$. In this setting the sum $\sum_{t\in Q}{\chi_{H(t)}(G)}$
heavily depends on whether the edge $\\{v_{1},v_{2}\\}$ is present in $G$: if
the edge is present, then the sum is equal to $n^{k-2}\frac{1-p}{p}$ and, if
the edge is not present, then it is equal to $-n^{k-2}$. This indicates that
on some rectangles the measure heavily depends on a few edges and we can thus
not hope to naïvely prove concentration of the measure over all rectangles.

This slightly simplified example can be generalized to show that for a fixed
$H$ there is always a small number of rectangles where the value contributed
by $H$ is much larger than expected. Part of the technical challenge of the
proof is to identify these bad rectangles and to handle them separately.

###  3.3 Edge Axioms Should Have Small Measure

We now explain the main ideas for bounding the magnitude of the measure of
edge axioms. Recall that all other axioms are mapped to $0$ by $\mu$ and we
are thus just left to show that the value of the edge axioms is closely
concentrated around $0$.

For every pair of vertices $\\{u,v\\}\notin E(G)$ in distinct blocks we have
an edge axiom $p_{uv}=x_{u}x_{v}$ stating that at least one of $x_{u}$ and
$x_{v}$ are set to $0$. Let $Q$ be a subrectangle of $Q(p_{uv})$. Note that
for every such rectangle $Q$ there is a monomial $m$ such that $Q=Q(m\cdot
p_{uv})$ and hence these are the correct rectangles to consider if we want to
prove Item 2 of Definition 3.2. In other words, if we manage to show for all
such $Q$ that $|\mu_{d}(Q)|\leq n^{-\Omega(d)}$, then it follows that for all
monomials $m$ it holds that $|\mu_{d}(m\cdot p_{uv})|\leq n^{-\Omega(d)}$, as
needed.

We first show that for a fixed pair of vertices $\\{u,v\\}\not\in E(G)$, with
good probability, all such subrectangles $Q$ have small absolute measure. By a
union bound over all missing edges we then conclude that all subrectangles $Q$
of an edge axiom satisfy $|\mu_{d}(Q)|\leq n^{-\Omega(d)}$. Let us fix an edge
$\\{u,v\\}\notin E(G)$.

If $Q$ is empty, then there is nothing to prove as $\mu_{d}(Q)$ is trivially
$0$. Hence we may assume that $Q$ is non-empty, that is, $Q$ has at least one
vertex per block and hence each tuple in $Q$ contains both $u$ and $v$. Let
$i\neq j\in[k]$ such that $u\in V_{i}$ and $v\in V_{j}$. For $e=\\{i,j\\}$ we
may write

$\displaystyle\mu_{d}(Q)$ $\displaystyle=n^{-k}\sum_{t\in
Q}\sum_{H\in\mathcal{H}_{d}}\chi_{H(t)}(G)$ (3.15)
$\displaystyle=n^{-k}\sum_{t\in
Q}\Big{(}\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}\\\ e\notin
H\end{subarray}}\chi_{H(t)}(G)+\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}\\\
e\in H\end{subarray}}\chi_{H(t)}(G)\Big{)}$ (3.16)
$\displaystyle=n^{-k}\sum_{t\in
Q}\sum_{\begin{subarray}{c}H:\,\operatorname*{vc}(H)=d,\\\
\operatorname*{vc}(H\cup\\{e\\})=d+1\end{subarray}}\chi_{H(t)}(G)\enspace,$
(3.17)

where the last equality follows from the fact that every tuple $t\in Q$
contains $u$ and $v$ and thus, if $e\notin H$, then
$\chi_{H(t)}(G)=-\chi_{H(t)}(G)\cdot\chi_{\\{u,v\\}}(G)=-\chi_{(H\cup\\{e\\})(t)}(G)$
as $\\{u,v\\}\not\in E(G)$.

The naïve approach to bounding $|\mu_{d}(Q)|$ is to try to bound the magnitude
of $\sum_{t\in Q}\chi_{H(t)}(G)$ for each $H$ separately and to then multiply
this bound by the number of graphs $H$ we sum over. Recall from Lemma 2.4 that
there are about $2^{dk}$ graphs with a minimum vertex cover of size $d$. As
the magnitude of $\sum_{t\in Q}\chi_{H(t)}(G)$ typically has value
$\Omega(n^{-d}|Q|)$, for large rectangles $Q$, even with the optimal bound
$|\sum_{t\in Q}\chi_{H(t)}(G)|\leq O(n^{-d}|Q|)$, we can only show a bound of

$\displaystyle|\mu_{d}(Q)|\leq
n^{-k}\sum_{\begin{subarray}{c}H:\,\operatorname*{vc}(H)=d,\\\
\operatorname*{vc}(H\cup\\{e\\})=d+1\end{subarray}}O\big{(}|Q|n^{-d}\big{)}\leq
O\big{(}2^{dk}n^{-d}\big{)}=O\big{(}\exp(d(k-\log n))\big{)}\enspace.$ (3.18)

Note that for $k=\operatorname{poly}(n)$ much larger than both $d$ and $\log
n$ the bound is at best $\exp\bigl{(}O(k)\bigr{)}$. We require a bound of the
form $|\mu_{d}(Q)|\leq n^{-\Omega(d)}$, which is much smaller than
$\exp\bigl{(}O(k)\bigr{)}$.

Instead of bounding the magnitude of $\sum_{t\in Q}\chi_{H(t)}(G)$ for each
$H$ separately, we partition the relevant set of graphs into different
families and proceed to bound the magnitude of
$\sum_{H\in\mathcal{H}(F,E^{\star}_{F})}\sum_{t\in Q}\chi_{H(t)}(G)$ for each
such family $\mathcal{H}(F,E^{\star}_{F})$. More precisely, we have families
of graphs indexed by graphs $F$ with at most $3d$ non-isolated vertices of the
form

$\displaystyle\mathcal{H}(F,E^{\star}_{F})=\\{H\mid E(H)=E(F)\cup
E,\leavevmode\nobreak\ \text{where}\leavevmode\nobreak\ E\subseteq
E^{\star}_{F}\\}\enspace,$ (3.19)

that partition the set of graphs $H$ satisfying $\operatorname*{vc}(H)=d$ and
$\operatorname*{vc}(H\cup\\{e\\})=d+1$. Using these families we can bound the
magnitude of $\mu_{d}(Q)$ by

$\displaystyle|\mu_{d}(Q)|$ $\displaystyle=n^{-k}\Big{|}\sum_{t\in
Q}\sum_{\begin{subarray}{c}H:\,\operatorname*{vc}(H)=d,\\\
\operatorname*{vc}(H\cup\\{e\\})=d+1\end{subarray}}\chi_{H(t)}(G)\Big{|}$
(3.20) $\displaystyle\leq n^{-k}\sum_{F}\Big{|}\sum_{t\in
Q}\sum_{H\in\mathcal{H}(F,E^{\star}_{F})}\chi_{H(t)}(G)\Big{|}$ (3.21)
$\displaystyle=n^{-k}\sum_{F}\Big{|}\sum_{t\in
Q}\chi_{F(t)}(G)\sum_{E\subseteq E^{\star}_{F}}\chi_{E(t)}(G)\Big{|}\enspace.$
(3.22)

Observe that the innermost sum is, up to normalization, the indicator function
of whether the edge set $E^{\star}_{F}(t)$ is present in $G$. In fact the
innermost sum, with the appropriate definition of $E^{\star}_{F}$, is simply a
statement about the common neighborhood sizes of different subsets of $t$ in
$G$. We will need to argue that for random graphs, with high probability, all
such sets behave as expected and the innermost sums are therefore bounded.

Furthermore, since each graph $F$ has at most $3d$ with incident edges, there
are fewer such graphs: according to Lemma 2.4 at most $2^{3d(d+\log k)}$.
Since $k\leq n^{1/66}$ and $d\leq 2\eta\log n$, for some small constant
$\eta$, it holds that there are at most $2^{d(d+\log k)}\lesssim n^{d/50}$
many such graphs $F$. Thus, an upper bound of $n^{k-\Omega(d)}$ on the
absolute value of two innermost sums in Equation 3.22 can now be used to
obtain the claimed bound $|\mu_{d}(Q)|\leq n^{-\Omega(d)}$. This completes the
proof sketch for bounding the measure on edge axioms.

In Section 4 we formally define these _core_ graphs $F$ and the families
$\mathcal{H}(F,E^{\star}_{F})$. In Section 5 we introduce the pseudorandomness
property of graphs we rely on in order to bound the two innermost sums in
Equation 3.22. In Section 6.1 we formally prove that the measure on
subrectangles of axioms is bounded in absolute value and lastly, in Section 8,
we verify that random graphs indeed satisfy the necessary pseudorandomness
properties.

###  3.4 Rectangles Should Be Approximately Non-Negative

To show that all rectangles $Q$ have essentially non-negative measure, the
main idea is to decompose $Q$ into a collection $\mathcal{Q}$ of rectangles
satisfying the following properties.

  1. 1.

The collection $\mathcal{Q}$ is small, that is, $|\mathcal{Q}|\leq n^{O(d)}$.

  2. 2.

Each rectangle $Q\in\mathcal{Q}$ is either

    1. (a)

very small: $|Q|\leq n^{(1-\varepsilon)k}$ and hence $|\mu_{d}(Q)|$ is
negligible,

    2. (b)

a subrectangle of an axiom and thus, as argued in Section 3.3, $|\mu_{d}(Q)|$
is bounded, or

    3. (c)

all common neighborhoods in $Q$ are of expected size and therefore

$\displaystyle\mu_{d}(Q)\approx|Q|/n^{k}>0\enspace.$ (3.23)

In other words, $\mathcal{Q}$ contains some rectangles that have negligible
measure and a collection of larger rectangles on which the measure behaves as
expected. As the latter rectangles have strictly positive measure we may
conclude that our pseudo-measure is essentially non-negative on all
rectangles.

We bound the measure on small rectangles by summing the maximum possible
magnitude of any character appearing in the definition of our pseudo measure.

######  Lemma 3.5.

Any rectangle $Q$ satisfies $|\mu_{d}(Q)|\leq
O\big{(}|Q|n^{-k}k^{d}p^{-dk}\big{)}$.

###### Proof.

We bound $\mu_{d}(Q)$ by counting the number of pattern graphs $H$ we sum over
multiplied by the maximum magnitude of each such character. We have that

$\displaystyle|\mu_{d}(Q)|$ $\displaystyle\leq
n^{-k}\sum_{i=0}^{d}\sum_{j=i}^{ik}\Big{|}\sum_{t\in
Q}\sum_{\begin{subarray}{c}H:\\\ \operatorname*{vc}(H)=i\\\
|E(H)|=j\end{subarray}}\chi_{H(t)}(G)\Big{|}$ (3.24)
$\displaystyle\leq|Q|\cdot
n^{-k}\sum_{i=0}^{d}\binom{k}{i}\sum_{j=0}^{ik}\binom{ik}{j}\Big{(}\frac{1-p}{p}\Big{)}^{j}$
(3.25) $\displaystyle=|Q|\cdot n^{-k}\sum_{i=0}^{d}\binom{k}{i}p^{-ik}\leq
O\big{(}|Q|n^{-k}k^{d}p^{-dk}\big{)}\enspace,$ (3.26)

as claimed. ∎

We implement the above proof outline in Section 6.2. Proving that our pseudo-
measure concentrates around a positive value on rectangles as described in
Item 2c is the most delicate part of our proof. In fact, the above proof
outline is somewhat inaccurate in that the value the pseudo-expectation
concentrates around is not simply $|Q|/n^{k}$ but further depends on the
number of small blocks in the rectangle $Q$. We refer to Definition 6.6 for
the precise definition of these rectangles and to 6.7 for the claimed
concentration inequality. Section 7 is dedicated to the proof of 6.7.

##  4 Cores

In this section we introduce the notion of a core of a pattern graph, which
will be used extensively throughout the rest of the paper. Our notion of a
core seems to be loosely connected to the notion of a _vertex cover kernel_ as
used in parameterized complexity (see, e.g., the survey by Fellows et al.
[FJK+18]).

###  4.1 Cores and Boundaries

Recall that when bounding the measure of subrectangles of axioms $A_{e}$, we
were left with sums over graphs $H$ such that $\operatorname*{vc}(H)=d$ and
$\operatorname*{vc}(H\cup\\{e\\})=d+1$ (see Equation 3.17). Such graphs
motivate the following definition of sets of graphs in the _boundary_ of an
edge.

######  Definition 4.1 (Boundary).

Let $i\in\mathbb{N}$, $H$ be a graph and $e\in\binom{V(H)}{2}$ be an edge. The
graph $H$ is in the _$(i,e)$ -boundary_, denoted by $\mathcal{H}_{i}(e)$, if
and only if $\operatorname*{vc}(H)=i$ and
$\operatorname*{vc}(H\cup\\{e\\})=i+1$. Furthermore, we say that $H$ is in the
_$e$ -boundary_ if and only if $H$ is in an $(i,e)$-boundary for some
$i\in\mathbb{N}$.

As mentioned in the proof sketch bounding the edge axioms, we cannot bound
each $H$ in the $e$-boundary separately (there are too many pattern graphs
$H$) so we partition such graphs according to _cores_ as explained below.

######  Definition 4.2 (Core).

A vertex induced subgraph $F$ of $H$ is a _core_ if any minimum vertex cover
of $F$ is also a vertex cover of $H$.

Ultimately we are interested in cores that are induced by small vertex sets.
It turns out that, in general, we cannot hope for cores of a graph $H$ that
are induced by fewer than $3\cdot\operatorname*{vc}(H)$ many vertices: as the
graph $H$ that consists of $\operatorname*{vc}(H)$ vertex disjoint paths of
length $2$ has only a single core $F=H$, the best we can hope for are cores of
size $3\cdot\operatorname*{vc}(H)$.

The notions of cores and $(i,e)$-boundaries interact nicely in the following
sense.

######  Proposition 4.3.

A core of a graph $H$ is in the $(i,e)$-boundary if and only if $H$ is.

###### Proof.

Let $F$ be a core of $H$. We first argue that if a core $F$ of the graph $H$
is in the $(i,e)$-boundary, then so is $H$. Indeed, by definition it holds
that $\operatorname*{vc}(F)=\operatorname*{vc}(H)=i$. Moreover, $F$ being in
the $(i,e)$-boundary implies that the minimum vertex cover of $F\cup\\{e\\}$
has size $i+1$, and therefore the minimum vertex cover of $H\cup\\{e\\}$ must
also be $i+1$ since $F$ is a subgraph of $H$.

It remains to argue that if $H$ is in the $(i,e)$-boundary, then so is the
core $F$. By definition of core,
$\operatorname*{vc}(F)=\operatorname*{vc}(H)=i$. Suppose, for the sake of
contradiction, that $F$ is not in the $(i,e)$-boundary and thus
$\operatorname*{vc}(F\cup\\{e\\})=i$. Let $W$ be a minimum-sized vertex cover
of $F\cup\\{e\\}$. Since $|W|=i$, it holds that $W$ is also a minimum-sized
vertex cover of $F$ and thus, by definition of core, $W$ is also a vertex
cover of $H$. But this contradicts the assumption that $H$ is in the
$(i,e)$-boundary since $W$ also covers the edge $e$ and hence is a vertex
cover of size $i$ of $H\cup\\{e\\}$. ∎

Recall that $\mathcal{H}$ is the set of graphs on $k$ labeled vertices. We
consider a map $\operatorname{core}$ from $\mathcal{H}$ to small cores that
satisfies certain properties as described below.

######  Theorem 4.4.

There is a map $\operatorname{core}$ that maps graphs $H\in\mathcal{H}$ to a
core of $H$ with the following properties. For every graph $F$ in the image of
$\operatorname{core}$ we have that $|V(E(F))|\leq 3\cdot\operatorname*{vc}(F)$
and that there exists an edge set $E^{\star}_{F}\subseteq
V\bigl{(}E(F)\bigr{)}\times\big{(}[k]\setminus V\bigl{(}E(F)\bigr{)}\big{)}$
such that $\operatorname{core}(H)=F$ if and only if $E(H)=E(F)\cup E$ for
$E\subseteq E^{\star}_{F}$.

We prove Theorem 4.4 in Section 4.2 below. From now on we only consider the
cores given by the map $\operatorname{core}$ as in Theorem 4.4. With a slight
abuse of nomenclature we say that $\operatorname{core}(H)$ is _the core_ of
$H$. Note that for a graph $F$ in the image of $\operatorname{core}$ we have
that $\operatorname{core}^{-1}(F)=\mathcal{H}(F,E^{\star}_{F})=\\{H\mid
E(H)=E(F)\cup E,\leavevmode\nobreak\ \text{for}\leavevmode\nobreak\ E\subseteq
E^{\star}_{F}\\}$, as introduced in Section 3.3.

###  4.2 Proof of Theorem 4.4

We first explain how to construct a map $\operatorname{core}$ and then prove
that it satisfies the required properties. In order to construct the mapping
we require an order on subsets of vertices of $H$: consider every subset of
vertices as a sequence of vertices sorted in ascending order and say that a
set $U$ is lexicographically smaller than a set $V$ if the ascending sequence
$(u_{1},\ldots,u_{s})$ of $U$ is lexicographically smaller than the sequence
$(v_{1},\ldots,v_{t})$ of $V$, that is, for $i=1,\ldots,\min\\{s,t\\}$ compare
$u_{i}$ with $v_{i}$: if $u_{i}<v_{i}$ (respectively $u_{i}>v_{i}$), then $U$
is lexicographically smaller (respectively larger) than $V$; if $u_{i}=v_{i}$
continue with $i=i+1$; if the prefix of length $\min\\{s,t\\}$ is equal, then
$U$ is lexicographically smaller (larger) than $V$ if $s<t$ (respectively
$s>t$).

Equivalently $U$ is lexicographically smaller than $V$ if the smallest element
in the symmetric difference of $U$ and $V$ is contained in $U$. From this
alternate definition we immediately obtain the following property of the
order.

######  Fact 4.5.

Let $W$ and $V$ be sets such that $W$ is lexicographically smaller than $V$
and $W\not\subset V$. Then, for any element $w$, the set $W\cup\\{w\\}$ is
lexicographically smaller than $V$.

We extend this notion in the natural manner to vertex covers and say that a
minimum vertex cover $W$ is the _lexicographically first minimum vertex cover
of $H$_ if $W$ is the lexicographically smallest minimum vertex cover of $H$.

Algorithm 1 Computes the core of $H$

1:procedure Core($H$)

2: $W\leftarrow$ lex first minimum vertex cover of $H$

3: $U_{1}\leftarrow$ lex first maximal set in $[k]\setminus W$ with matching
$M_{1}\subseteq H$ from $U_{1}$ to $W$ of size $|U_{1}|$

4: $U_{2}\leftarrow$ lex first maximal set in $[k]\setminus(W\cup U_{1})$ with
matching $M_{2}\subseteq H$ from $U_{2}$ to $W$ of size $|U_{2}|$

5: return $H[W\cup U_{1}\cup U_{2}]$

The map $\operatorname{core}$ is constructed as follows (see Algorithm 1 for
an algorithmic description). Given a graph $H$ with lexicographically first
minimum vertex cover $W$ define the following two sets $U_{1}$ and $U_{2}$ of
vertices. Let $U_{1}\subseteq[k]\setminus W$ be the lexicographically first
maximal (with respect to set inclusion) set of vertices with a matching
$M_{1}\subseteq H$ from $U_{1}$ to $W$ that covers all of $U_{1}$, that is,
$U_{1}\subseteq V(M_{1})$ and $M_{1}\subseteq U_{1}\times W$. Similarly let
$U_{2}\subseteq[k]\setminus(W\cup U_{1})$ be the lexicographically first
maximal set of vertices with a matching $M_{2}$ from $U_{2}$ to $W$ of size
$|U_{2}|$. The core of $H$ is defined to be $\operatorname{core}(H)=H[W\cup
U_{1}\cup U_{2}]$. An illustration is provided in Figure 2.

Let us record some simple observations

######  Claim 4.6.

For $H$, $W,U_{1},U_{2}$ and matchings $M_{1},M_{2}$ defined as above, it
holds that

  1. 1.

$W\cap V(M_{1})\supseteq W\cap V(M_{2})$,

  2. 2.

any edge $e\in H\setminus H[W\cup U_{1}]$ is incident to $W\cap V(M_{1})$, and

  3. 3.

any edge $e\in H\setminus H[W\cup U_{1}\cup U_{2}]$ is incident to $W\cap
V(M_{2})$.

###### Proof.

Item 1 follows by maximality of $U_{1}$. For Item 2, let $e=\\{v,w\\}\in
H\setminus H[W\cup U_{1}]$. As $W$ is a vertex cover of $H$ we may assume that
$w\in W$ and hence, as $e\not\in H[W\cup U_{1}]$, the vertex $v$ is not in
$W\cup U_{1}$. Hence by maximality of $U_{1}$ it holds that $w\in W\cap
V(M_{1})$. The same argument establishes Item 3. ∎

Since $|U_{2}|\leq|U_{1}|\leq|W|$, it follows that
$\bigl{|}V\bigl{(}E(F)\bigr{)}\bigr{|}\leq 3\,|W|\leq 3\operatorname*{vc}(H)$.
To argue that this map satisfies the other required properties, we first prove
that the size of the minimum vertex cover of $H[W\cup U_{1}]$ is the same as
that of $H$. Clearly
$\operatorname*{vc}(H)\geq\operatorname*{vc}\bigl{(}H[W\cup U_{1}]\bigr{)}$ so
it remains to prove the opposite inequality.

Figure 2: A core with edges in $M_{1}$ and $M_{2}$ highlighted

######  Lemma 4.7.

For $H$, $W$ and $U_{1}$ defined as above, it holds that
$\operatorname*{vc}(H)\leq\operatorname*{vc}\bigl{(}H[W\cup U_{1}]\bigr{)}$.

###### Proof.

Let $M_{1}$ be the matching from $U_{1}$ to $W$ that covers $U_{1}$ and let
$R$ be the vertices in $W$ that are not matched by $M_{1}$, that is,
$R=W\setminus V(M_{1})$. Towards contradiction suppose that the graph $H[W\cup
U_{1}]$ has a vertex cover of size $\operatorname*{vc}(H)-1$.

By 4.6, Item 2, the only edges in $H$ which do not appear in the graph
$H[W\cup U_{1}]$ are edges between a vertex in $W\cap V(M_{1})$ and a vertex
outside of $W\cup U_{1}$.

Let $W^{\prime}$ be a vertex cover of $H[W\cup U_{1}]$ of size
$\operatorname*{vc}(H)-1$ that maximizes $|W^{\prime}\cap V(M_{1})|$. If
$W^{\prime}$ is a vertex cover of $H$ we have reached a contradiction.
Otherwise, there exists a vertex $u\in W\cap V(M_{1})$ that is not contained
in $W^{\prime}$ and an edge $e_{0}=\\{u,w\\}\in E(H)$ for
$w\in[k]\setminus(W\cup U_{1})$.

We now want to argue that either we can construct a vertex cover of $H[W\cup
U_{1}]$ of size $\operatorname*{vc}(H)-1$ that contradicts the fact that
$W^{\prime}$ maximized $|W^{\prime}\cap V(M_{1})|$, or we can construct a
strict superset of $U_{1}$ with a matching to $W$, contradicting the
maximality of $U_{1}$.

We iteratively construct two sets, $A\subseteq W\setminus W^{\prime}$ and
$B\subseteq W^{\prime}\cap U_{1}$ as follows. We start by including $u$ in
$A$. We then iteratively include in $B$ all vertices $v$ in $U_{1}$ that are
matched by $M_{1}$ to some vertex in $A$, that is, vertices $v$ such that
$\\{v,v^{\prime}\\}\in M_{1}$ for some $v^{\prime}\in A$; and include in $A$
all vertices of $W$ not covered by $W^{\prime}\setminus B$. Note that
$|A|\geq|B|$ and that we keep the invariant that $B\subseteq W^{\prime}$ since
the edges in $M_{1}$ must be covered by some vertex. We consider two cases.

Case $|A|=|B|$:

In this case, $\big{(}W^{\prime}\cup A\big{)}\setminus B$ is a vertex cover of
$H[W\cup U_{1}]$ of size $\operatorname*{vc}(H)-1$ contradicting the fact that
$W^{\prime}$ maximized $|W^{\prime}\cap V(M_{1})|$.

Case $|A|>|B|$:

This can only happen if there is a vertex $v$ in $R\cap A$. In this case, we
can define an augmenting path from $v$ to $w$, alternating between edges not
in $M_{1}$ and edges in $M_{1}$. This implies we can define a matching that
matches all of $U_{1}$ to vertices in $W$ as well as the vertex $w$. This is
in contradiction with the maximality of $U_{1}$.∎

To prove that $H[W\cup U_{1}\cup U_{2}]$ is a core of $H$ we must show that
any minimum vertex cover of $H[W\cup U_{1}\cup U_{2}]$ is a vertex cover of
$H$.

######  Corollary 4.8.

Any minimum vertex cover of $H[W\cup U_{1}\cup U_{2}]$ is also a vertex cover
of $H$.

###### Proof.

By Lemma 4.7 we have that

$\displaystyle\operatorname*{vc}(H)=\operatorname*{vc}\bigl{(}H[W\cup
U_{1}]\bigr{)}=\operatorname*{vc}\bigl{(}H[W\cup U_{1}\cup
U_{2}]\bigr{)}\enspace.$ (4.1)

Therefore, any minimum vertex cover $W^{\prime}$ of $H[W\cup U_{1}\cup U_{2}]$
has no vertex in $U_{2}$ (otherwise, $W^{\prime}\setminus U_{2}$ would be a
smaller vertex cover of $H[W\cup U_{1}]$). As $W^{\prime}$ needs to cover the
edges of the matching $M_{2}$ from $U_{2}$ to $W$, the vertex cover
$W^{\prime}$ contains all vertices in $V(M_{2})\cap W$.

According to 4.6, Item 3, only vertices in $V(M_{2})\cap W$ may have edges
incident in $H$ that are not present in $H[W\cup U_{1}\cup U_{2}]$. Hence
$W^{\prime}$ is a vertex cover of $H$; the statement follows. ∎

It remains to argue that for every
$F\in\operatorname*{img}(\operatorname{core})$ there is a set $E^{\star}_{F}$
such that $\operatorname{core}(H)=F$ if and only if $H=F\cup E$ for
$E\subseteq E^{\star}_{F}$. Let
$E^{\star}_{F}=\bigcup_{H\in\operatorname{core}^{-1}(F)}H\setminus F$. By
definition, if $\operatorname{core}(H)=F$, then there is an $E\subseteq
E^{\star}_{F}$ such that $H=F\cup E$. We establish the reverse direction by
the following two claims.

In Appendix A we provide an alternate proof that characterizes the set
$E^{\star}_{F}$ explicitly.

######  Claim 4.9.

Let $\operatorname{core}(H)=F$ and let $W,U_{1},U_{2}$ (respectively
$W^{\prime},U_{1}^{\prime},U_{2}^{\prime}$) denote the sets as in Algorithm 1
when run on $H$ (respectively on $F$). It holds that $W=W^{\prime}$,
$U_{1}=U_{1}^{\prime}$ and $U_{2}=U_{2}^{\prime}$.

###### Proof.

By definition of the map $\operatorname{core}$ given by Algorithm 1, we have
that $F=H[W\cup U_{1}\cup U_{2}]$. Corollary 4.8 implies that $W$ is the
lexicographically first minimum vertex cover of $F$ (otherwise $W$ would not
be the lexicographically first minimum vertex cover of $H$) and hence
$W=W^{\prime}$.

Clearly any matching $M_{1}$ in $H$ from $W$ to $U_{1}$ is also in $F=H[W\cup
U_{1}\cup U_{2}]$, and any matching $M_{1}^{\prime}$ in $F$ from $W$ to
$U_{1}^{\prime}$ is also in $H\supseteq F$, and thus it must hold
$U_{1}=U_{1}^{\prime}$. Similarly, any matching $M_{2}$ in $H[[k]\setminus
U_{1}]$ from $W$ to $U_{2}$ is also in $F[[k]\setminus U_{1}]=H[W\cup U_{2}]$,
and any matching $M_{2}^{\prime}$ in $F[[k]\setminus U_{1}]$ from $W$ to
$U_{2}^{\prime}$ is also in $H[[k]\setminus U_{1}]\supseteq F[[k]\setminus
U_{1}]$, and thus it must hold $U_{2}=U_{2}^{\prime}$. ∎

Note that 4.9 implies that $\operatorname{core}(F)=F$ and that the sets
$W,U_{1}$ and $U_{2}$ as in Algorithm 1 run on any two graphs $H$ and
$H^{\prime}$ such that
$\operatorname{core}(H)=\operatorname{core}(H^{\prime})$ are identical.

######  Lemma 4.10.

For $F\in\operatorname*{img}(\operatorname{core})$ and for all $E\subseteq
E^{\star}_{F}$ it holds that $\operatorname{core}(F\cup E)=F$.

###### Proof.

Let $E^{\prime},E^{\prime\prime}$ be subsets of $E^{\star}_{F}$ such that
$\operatorname{core}(F\cup E^{\prime})=\operatorname{core}(F\cup
E^{\prime\prime})=F$. It suffices to show that if $E\subseteq E^{\prime}\cup
E^{\prime\prime}$, then it holds that $\operatorname{core}(F\cup E)=F$. Let
$W,U_{1},U_{2}$ ($W^{\prime},U_{1}^{\prime},U_{2}^{\prime}$) be the sets as in
Algorithm 1 when run on $F\cup E$ (respectively on $F\cup E^{\prime}$). By 4.9
the sets $W^{\prime},U_{1}^{\prime}$ and $U_{2}^{\prime}$ could be
equivalently defined as the sets from Algorithm 1 when run on $F$ or $F\cup
E^{\prime\prime}$.

We first show that $W=W^{\prime}$. By 4.9 we have that $W^{\prime}$ is the
lexicographically first minimum vertex cover of $F$. It suffices to argue that
$W^{\prime}$ is a vertex cover of $F\cup E$ since any vertex cover of $F\cup
E$ is a vertex cover of $F$. But this is easy to see since $W^{\prime}$ is a
vertex cover of $F\cup E^{\prime}$ and of $F\cup E^{\prime\prime}$ and thus it
is a vertex cover of $F\cup E^{\prime}\cup E^{\prime\prime}$, and hence also
of $F\cup E\subseteq F\cup E^{\prime}\cup E^{\prime\prime}$.

Suppose for the sake of contradiction that $U_{1}\neq U_{1}^{\prime}$ and let
$u$ be the smallest vertex in the symmetric difference of $U_{1}$ and
$U_{1}^{\prime}$. Note that any matching $M_{1}^{\prime}$ in $F\cup
E^{\prime}$ from $W$ to $U_{1}^{\prime}$ is also in $F$. Hence either
$U_{1}^{\prime}\subseteq U_{1}$ (since $U_{1}$ is a maximal set with a
matching $M_{1}\subseteq F\cup E$ into $W$) or $U_{1}^{\prime}$ is
lexicographically larger than $U_{1}$ (as $U_{1}$ is the lexicographically
first such set). In both cases it holds that $u\in U_{1}$.

Let ${U}=(U_{1}\cap U_{1}^{\prime})\cup\\{u\\}$ and observe that since
$u\not\in U_{1}^{\prime}$, it holds that either $U_{1}^{\prime}\subsetneq U$
or $U_{1}^{\prime}$ is lexicographically larger than $U$. Let $M$ be a
matching in $F\cup E$ from $U$ to $W$ that covers $U$ (which exists as
${U}\subseteq U_{1}$) and denote by $e$ the edge in $M$ adjacent to $u$. Since
$e\in F\cup E\subseteq F\cup E^{\prime}\cup E^{\prime\prime}$ it must be the
case that $e\in F\cup E^{\prime}$ or $e\in F\cup E^{\prime\prime}$. Without
loss of generality suppose that $e\in F\cup E^{\prime}$ and thus $M\subseteq
F\cup E^{\prime}$. Note that this contradicts the choice of $U_{1}^{\prime}$:
if $U_{1}^{\prime}\subsetneq U$, then $U_{1}^{\prime}$ is not maximal and, if
$U_{1}^{\prime}$ is lexicographically larger than $U$, then by 4.5, it is not
the lexicographically first maximal set that can be matched to $W$. We
conclude that $U_{1}=U_{1}^{\prime}$.

A similar argument can be used to show that $U_{2}=U_{2}^{\prime}$ and thus
$\operatorname{core}(F\cup E)=F$ as claimed. ∎

##  5 Well-Behaved Graphs

In this section, we define the notion of _well-behaved_ graphs, which is based
on two combinatorial properties of graphs related to common neighborhoods of
small tuples, and two analytic properties that bound certain character sums.
In Section 8 we then show that random graphs are asymptotically almost surely
well-behaved. In the following sections we prove that our measure satisfies
the required conditions to obtain our Sherali-Adams coefficient size lower
bound for any well-behaved graph.

Let us start by introducing the concepts needed to define well-behaved graphs.
We say a rectangle $Q$ is _$s$ -small_ if $|Q_{i}|\leq s$ for all $i\in[k]$
and, given a set $A\subseteq[k]$, a rectangle $Q$ is said to be _$(s,A)$
-large_ if $|Q_{i}|>s$ for all $i\in A$. For any set $\mathcal{D}$ we say that
a function $f:\mathcal{D}\rightarrow\mathbb{R}^{+}$ is _$r$ -bounded_ if
$f(x)\leq r$ for all $x\in\mathcal{D}$.

We require some terminology and notation from graph theory. The neighborhood
of a vertex $v\in V$ in a graph $G=(V,E)$ is
$N(v)=N_{G}(v)=\\{u\mid\\{u,v\\}\in E\\}$ and the neighborhood of a set of
vertices $U\subseteq V$ is $N(U)=N_{G}(U)=\\{v\not\in U\mid\exists u\in
U:\\{u,v\\}\in E\\}$. For a set $W\subseteq V$ the neighborhood of a vertex
$v$ in $W$ is $N(v,W)=N(v)\cap W$ and similarly for a set $U$ we let the
neighborhood of $U$ in $W$ be $N(U,W)=N(U)\cap W$. The common neighborhood of
$U$ is $N^{\cap}(U)=\bigcap_{u\in U}N(u)$ and the common neighborhood of $U$
in $W$ is $N^{\cap}(U,W)=N^{\cap}(U)\cap W$. This notation is naturally
extended to a tuple $t$ by considering $t$ as a set of vertices.

The next two definitions are purely combinatorial. They are similar to
definitions that have appeared in previous papers on $k$-clique [BIS07,
BGLR12, ABdR+21]. Recall that throughout the paper graphs denoted by $G$ are
$k$-partite with partitions $V_{1},\ldots,V_{k}$ of size $n$ each.

######  Definition 5.1 (Bounded common neighborhoods).

A graph $G$ has _$(\beta,p)$ -bounded common neighborhoods from
$Q=\bigtimes_{i\in A}Q_{i}$ to $R\subseteq V(G)$_ if it holds that for all
$B\subseteq A$ and all $t\in Q_{B}$

$\displaystyle|N^{\cap}(t,R)|\in(1\pm\beta)p^{|t|}|R|\enspace.$

A graph $G$ has _$(\beta,p,d)$ -bounded common neighborhoods in every block_
if for all $A\subseteq[k]$ of size at most $d$ and all $i\in[k]\setminus A$,
$G$ has $(\beta,p)$-bounded common neighborhoods from $V_{A}$ to $V_{i}$.

While it turns out that random graphs do have bounded common neighborhoods,
the graph induced by a rectangle may certainly have tuples with ill-behaved
common neighborhoods: we may for example have an isolated vertex in a
rectangle. The following definition roughly states that, while there may be
tuples with ill-behaved neighborhoods in a rectangle, there is a large sub-
rectangle which has bounded common neighborhoods.

######  Definition 5.2 (Bounded error sets).

A graph $G$ has $(s,w,\beta,p,d)$-_bounded error sets_ if for all rectangles
$Q=\bigtimes_{i\in[k]}Q_{i}$ satisfying $|Q_{i}|\geq s$ or $|Q_{i}|=0$ it
holds that there exists a small set of vertices $W\subseteq V(G)$, $|W|\leq
w$, such that for all $S\subseteq[k]$ of size at most $d$ it holds that all
tuples $t\in\bigtimes_{i\in S}(Q_{i}\setminus W)$ satisfy

$\displaystyle\bigl{|}N^{\cap}(t,Q_{j}\setminus
W)\bigr{|}\in(1\pm\beta)p^{|t|}\bigl{|}Q_{j}\setminus W\bigr{|}$

for all $j\in[k]\setminus S$. We refer to $W$ as the _error set of $Q$_.

Recall from the edge axiom proof sketch in Section 3.3 that we require bounds
of the form $n^{k-\Omega(\operatorname*{vc}(F))}$ on the absolute value of
certain character sums. It turns out that, in order to prove that monomials
are mapped to an essentially non-negative value, we need tighter (depending on
$|Q|$) as well as “localized” versions of these bounds. For conciseness we
introduce the following terminology.

######  Definition 5.3 (Bounded character sums).

Let $s\in\mathbb{N}^{+}$, $B\subseteq[k]$, $Q_{B}=\bigtimes_{i\in B}Q_{i}$ and
$F$ be a core graph. A graph $G$ has _$s$ -bounded character sums over $Q_{B}$
for $F$_ if it holds that

$\displaystyle\Big{|}\sum_{t\in
Q_{B}}\sum_{H\in\mathcal{H}(F,E^{\star}_{F}[B])}\chi_{H[B](t)}(G)\Big{|}\leq
s\enspace.$

We are now ready to state the pseudorandomness property of graphs that allows
us to prove average-case Sherali-Adams coefficient size lower bounds for the
$k$-clique formula. As Items 3 and 4 are somewhat difficult to parse we give
an informal description upfront.

Item 3 states that all character sums over the families
$\mathcal{H}(F,E^{\star}_{F})$ are of bounded magnitude if the rectangle
considered has large minimum block size. Smaller rectangles are unfortunately
not as well-behaved. However, for certain rectangles, we can guarantee
something similar: Item 4 states that if the common neighborhood of small
tuples in a rectangle are bounded, then the mentioned character sums can still
be bounded.

First time readers may, for now, choose to skip the formal definition of Item
4. It might be more insightful to first read Sections 6 and 7 and return to
Item 4 once it is used.

######  Definition 5.4 (Well-behaved graphs).

We say that a $k$-partite graph $G$ with partitions of size $n$ is _$D$ -well-
behaved_ if, for $p=n^{-2/D}$, the following properties hold:

  1. 1.

$G$ has $(1/k,p,D/4)$-bounded common neighborhoods in every block.

  2. 2.

There exists a constant $C\in\mathbb{R}^{+}$ such that $G$ has
$(2s,s,1/k,p,\ell)$-bounded error sets for all $\ell\leq D/4$ and $s\geq
Ck^{4}\ell\ln n/p^{2\ell}$.

  3. 3.

For any core $F$ satisfying $\operatorname*{vc}(F)\leq D/4$, and any
$\big{(}n/2,V\bigl{(}E(F)\bigr{)}\big{)}$-large rectangle $Q$ it holds that
$G$ has $s$-bounded character sums over $Q_{[n]}$ for $F$, where

$\displaystyle s=6\cdot p^{-{|E(F)|}}\cdot
n^{k-\lambda\operatorname*{vc}(F)/4}\enspace,$

for any $\lambda<1-\log(k)/\log(n)$.

  4. 4.

Let $F$ be a core satisfying $\operatorname*{vc}(F)\leq D/4$, let $\Lambda\geq
20\,k\log n$, denote by $B\subseteq[k]$ a set of vertices and let
$A=V\bigl{(}E(F)\bigr{)}\cap B$. Then for any rectangle $Q$ which is
$(4\Lambda)$-small and $(\Lambda,B)$-large the following holds. If $G$ has
$(3/k,p)$-bounded common neighborhoods from $Q_{A}$ to $Q_{i}$ for every $i\in
B\setminus A$, then $G$ has $s$-bounded character sums over $Q_{B}$ for $F$,
where

$\displaystyle s=O\big{(}p^{-{|E(F[B])|}}\cdot\left({\Lambda}/{10\,k\log
n}\right)^{-\operatorname*{vc}(F[B])/4}\cdot|Q_{B}|\big{)}\enspace.$

In what follows we often state that a graph $G$ is $D$-well-behaved in which
case it is implicitly understood that $G$ is $k$-partite with partitions of
size $n$. In Section 8 we prove that a graph $G$ sampled from the distribution
$\mathcal{G}(n,k,n^{-2/D})$ is asymptotically almost surely $D$-well-behaved.

######  Theorem 5.5.

If $n$ is a large enough integer, $k\in\mathbb{N}^{+}$ and
$D\in\mathbb{R}^{+}$ satisfy $4\leq D\leq 2\log n$ and $k\leq n^{1/5}$, then
$G\sim\mathcal{G}(n,k,n^{-2/D})$ is asymptotically almost surely $D$-well-
behaved.

##  6 Clique Is Hard on Well-Behaved Graphs

In this section we prove that our measure $\mu_{d}$ is an
$n^{-\Omega(D)}$-pseudo-measure for the $k$-clique formula, if the formula is
defined over a $D$-well-behaved graph $G$.

######  Theorem 6.1.

There are constants $\eta,c>0$ and $D_{0}\in\mathbb{N}$ such that the
following holds for large enough $n\in\mathbb{N}$ and all $D$ satisfying
$D_{0}<D\leq 2\log n$. If $D\leq k\leq n^{1/66}$, $d=\eta D$ and $G$ is a
$D$-well-behaved $k$-partite graph with $n$ vertices per block, then the
normalized measure $\mu(m)=\mu_{d}(m)/\mu_{d}(1)$ is an $n^{-cD}$-pseudo-
measure for the $k$-clique formula over $G$.

From Theorem 6.1 along with 5.5 and Proposition 3.3 we obtain Theorem 3.1.

In order to prove that the measure $\mu$ satisfies the properties of a pseudo-
measure as listed in Definition 3.2, we show that $\mu_{d}$ maps any axiom
multiplied by a monomial to approximately $0$ and that all monomials are
associated with an essentially non-negative value. Finally, we argue that
$\mu_{d}(1)\geq 1-n^{-\Omega(1)}$.

Recall that the clique formula consists of block axioms $\sum_{v\in
V_{i}}x_{v}-1=0$ for each block $V_{i}$ and edge axioms $x_{u}x_{v}=0$ for
every non-edge in the graph. By linearity of $\mu_{d}$ over the tuples it
holds for any monomial $m$ that $\mu_{d}\big{(}m(\sum_{v\in
V_{i}}x_{v}-1)\big{)}=0$. The lemma below implies that for edge axioms
$p_{uv}=x_{u}x_{v}$ it holds that $|\mu_{d}(mp_{uv})|\leq n^{-cD}$, for any
monomial $m$. As mentioned in Section 3.4, we also rely on this lemma to prove
that the measure is essentially non-negative. Since that proof requires a
careful choice of parameters we need to state the lemma with some precision.

######  Lemma 6.2.

Let $G$ be a $D$-well-behaved graph, let $n$ be a large enough integer and let
$d=\eta D\leq 2\eta\log n$ for some constant $\eta>0$. It holds that all edge
axioms $p_{uv}$ and all rectangles $Q\subseteq Q({p_{uv}})$ satisfy
$|\mu_{d}(Q)|\leq
O\big{(}\big{(}n^{\lambda/4-12\eta}/(2k)^{3}\big{)}^{-d}\big{)}$ for any
$\lambda<1-\log(k)/\log(n)$.

Note that by choosing $\lambda=1/2$, and considering $k\leq n^{1/66}$ and
$\eta>0$ small enough, 6.2 implies that any subrectangle of an edge axiom
satisfies $|\mu_{d}(Q)|\leq n^{-cD}$ for some small enough constant $c$. We
postpone the proof of 6.2 to Section 6.1.

In addition to the bound on the magnitude of the measure on the axioms we also
need to prove that the measure is essentially non-negative. We state this
formally below and defer the proof to Section 6.2.

######  Lemma 6.3.

There are constants $\eta,c>0$ such that if $G$ is a $D$-well-behaved graph,
$n$ is large enough, $d=\eta D\leq 2\eta\log n$ and $D\leq k\leq n^{1/66}$,
then any rectangle $Q$ satisfies $\mu_{d}(Q)\geq-n^{-cD}$.

In Section 3.2 we argued that with high probability $\mu_{d}(1)$ is
approximately $1$ if $G$ is a random graph and $p=1/2$. We now show that this
holds for any $D$-well-behaved graph.

######  Lemma 6.4.

There are constants $\eta,c>0$ such that for $n$ large enough, $k\leq
n^{1/20}$, $D\leq 2\log n$ and $d=\eta D$ it holds that if $G$ is a $D$-well-
behaved graph, then $\mu_{d}(1)\geq 1-n^{-c}$.

###### Proof.

This is a direct consequence of the definition of a $D$-well-behaved graph and
Theorem 4.4. Recall the map $\operatorname{core}$ as defined in Theorem 4.4
and the families of graphs

$\displaystyle\mathcal{H}(F,E^{\star}_{F})=\\{H\mid E(H)=E(F)\cup
E,\text{\leavevmode\nobreak\ for\leavevmode\nobreak\ }E\subseteq
E^{\star}_{F}\\}\enspace,$ (6.1)

defined for core graphs $F\in\operatorname*{img}(\operatorname{core})$ such
that $\operatorname*{vc}(F)\leq d$. Recall that each such core graph $F$
satisfies that $|V\bigl{(}E(F)\bigr{)}|\leq 3\operatorname*{vc}(F)$ and hence
$|E(F)|\leq 3\bigl{(}\operatorname*{vc}(F)\bigr{)}^{2}\leq
3d\operatorname*{vc}(F)$.

By appealing to Item 3 of a $D$-well-behaved graph, that is, Item 3 of
Definition 5.4, with $\lambda=4/5$ we can conclude that for every
$F\in\operatorname*{img}(\operatorname{core})$ it holds that

$\displaystyle n^{-k}\Big{|}\sum_{t\in
Q(1)}\sum_{H\in\mathcal{H}(F,E^{\star}_{F})}\chi_{H(t)}(G)\Big{|}\leq
6\,p^{-|E(F)|}n^{-\operatorname*{vc}(F)/5}\leq
n^{-\operatorname*{vc}(F)/6}\enspace,$ (6.2)

where we used the bound $p^{-|E(F)|}\leq p^{-3d\operatorname*{vc}(F)}\leq
n^{6\eta\operatorname*{vc}(F)}$, which holds since $p=n^{-2/D}$ and $d=\eta
D\leq 2\eta\log n$, and, furthermore, relied on the assumption that $\eta$ is
a small enough constant.

Recall that the families $\\{\mathcal{H}(F,E^{\star}_{F})\mid
F\in\operatorname*{img}(\operatorname{core})\\}$ as defined in Equation 6.1
partition the set $\mathcal{H}_{d}$ of graphs of vertex cover at most $d$. We
may hence write

$\displaystyle\mu_{d}(1)$
$\displaystyle=n^{-k}\sum_{H\in\mathcal{H}_{d}}\sum_{t\in Q(1)}\chi_{H(t)}(G)$
(6.3) $\displaystyle=1+n^{-k}\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}\\\
H\neq\emptyset\end{subarray}}\sum_{t\in Q(1)}\chi_{H(t)}(G)$ (6.4)
$\displaystyle\geq
1-n^{-k}\sum_{i=1}^{d}\sum_{\begin{subarray}{c}F\in\operatorname*{img}(\operatorname{core})\\\
\operatorname*{vc}(F)=i\end{subarray}}\Big{|}\sum_{t\in
Q(1)}\sum_{H\in\mathcal{H}(F,E^{\star}_{F})}\chi_{H(t)}(G)\Big{|}\enspace.$
(6.5)

Since each graph $F\in\operatorname*{img}(\operatorname{core})$ satisfies that
$|V\bigl{(}E(F)\bigr{)}|\leq 3\operatorname*{vc}(F)$, by appealing to Lemma
2.4, we obtain the bound
$|\\{F\in\operatorname*{img}(\operatorname{core})\mid\operatorname*{vc}(F)=i\\}|\leq
2^{3i(d+\log k)}$. Combining this bound along with the bound from Equation 6.2
we may conclude that

$\displaystyle\mu_{d}(1)$ $\displaystyle\geq
1-n^{-k}\sum_{i=1}^{d}\sum_{\begin{subarray}{c}F\in\operatorname*{img}(\operatorname{core})\\\
\operatorname*{vc}(F)=i\end{subarray}}\Big{|}\sum_{t\in
Q(1)}\sum_{H\in\mathcal{H}(F,E^{\star}_{F})}\chi_{H(t)}(G)\Big{|}$ (6.6)
$\displaystyle\geq 1-\sum_{i=1}^{d}2^{3i(d+\log k)}n^{-i/6}$ (6.7)
$\displaystyle\geq 1-n^{-c}\enspace,$ (6.8)

for some small constant $c>0$. The final inequality relies on the assumptions
$d\leq 2\eta\log n$, that $\eta$ is a small enough constant and that $k\leq
n^{1/20}$. This concludes the proof. ∎

This completes the proof of Theorem 6.1 modulo 6.2 and 6.3. In Section 6.1 we
prove 6.2 and the proof of 6.3 is provided in Section 6.2.

###  6.1 Axioms Have Small Measure

In this section we show that any subrectangle of an edge axiom has small
measure in absolute value. We rely on the following technical lemma.

######  Lemma 6.5.

If $G$ is a $D$-well-behaved graph, then for any core graph $F$ and any
rectangle $Q$ it holds that

$\displaystyle\Big{|}\sum_{t\in
Q}\sum_{H\in\mathcal{H}(F,E^{\star}_{F})}\chi_{H(t)}(G)\Big{|}\leq 6\cdot
2^{|A|}\cdot p^{-|E(F)|}\cdot n^{k-\lambda\operatorname*{vc}(F)/4}\enspace,$

where $A=V\bigl{(}E(F)\bigr{)}$ and $\lambda<1-\log(k)/\log(n)$.

###### Proof.

Let $F$ be a core graph, let $A=V\bigl{(}E(F)\bigr{)}$ and $s=6\cdot
p^{-|E(F)|}\cdot n^{k-\lambda\operatorname*{vc}(F)/4}$. By Item 3 of
Definition 5.4 we have that if $Q$ is $(n/2,A)$-large , that is, if $Q$
satisfies $|Q_{i}|\geq n/2$ for all $i\in A$, then $\big{|}\sum_{t\in
Q}\sum_{H\in\mathcal{H}(F,E^{\star}_{F})}\chi_{H(t)}(G)\big{|}\leq s$.

Given any rectangle $Q$ (not necessarily $(n/2,A)$-large), let $T\subseteq A$
be the set of blocks of $Q$ such that $|Q_{i}|<n/2$. By a simple inclusion-
exclusion argument, we obtain that

$\displaystyle Q=\sum_{S\subseteq T}(-1)^{|S|}\Big{(}\bigtimes_{i\in
S}(V_{i}\setminus Q_{i})\Big{)}\times\Big{(}\bigtimes_{i\in T\setminus
S}V_{i}\Big{)}\times\Big{(}\bigtimes_{i\in[k]\setminus
T}Q_{i}\Big{)}\enspace.$ (6.9)

For $S\subseteq T$, denote by $Q^{S}$ the rectangle $\Big{(}\bigtimes_{i\in
S}(V_{i}\setminus Q_{i})\Big{)}\times\Big{(}\bigtimes_{i\in T\setminus
S}V_{i}\Big{)}\times\Big{(}\bigtimes_{i\in[k]\setminus T}Q_{i}\Big{)}$. Note
that $Q^{S}$ is $(n/2,A)$-large and therefore by Item 3 of Definition 5.4, $G$
has $s$-bounded character sums over $Q^{S}$ for $F$. This implies that

$\displaystyle\Big{|}\sum_{t\in
Q}\sum_{H\in\mathcal{H}(F,E^{\star}_{F})}\chi_{H(t)}(G)\Big{|}\leq\sum_{S\subseteq
T}\Big{|}\sum_{t\in
Q^{S}}\sum_{H\in\mathcal{H}(F,E^{\star}_{F})}\chi_{H(t)}(G)\Big{|}\leq
2^{|A|}\cdot s\enspace,$ (6.10)

as claimed. ∎

We are now ready to prove 6.2 restated for convenience.

See 6.2

###### Proof.

Fix an edge $\\{u,v\\}\notin E(G)$, let $i,j\in[k]$ such that $u\in V_{i}$ and
$v\in V_{j}$, consider the edge axiom $p_{uv}=x_{u}x_{v}$ and let $Q\subseteq
Q({p_{uv}})$ be an arbitrary subrectangle of this edge axiom. Recall that
$\mathcal{H}_{d}$ denotes the set of graphs $H$ satisfying
$\operatorname*{vc}(H)\leq d$, and as explained in Section 3.3, recall that
every tuple $t\in Q$ contains the vertices $u$ and $v$. Thus for $e=\\{i,j\\}$
we may cancel a character $\chi_{H}$ satisfying $e\not\in H$ with the
character $\chi_{H\cup\\{e\\}}$ to obtain that

$\displaystyle\mu_{d}(Q)$ $\displaystyle=n^{-k}\sum_{t\in
Q}\sum_{H\in\mathcal{H}_{d}}\chi_{H(t)}(G)$ (6.11)
$\displaystyle=n^{-k}\sum_{t\in
Q}\sum_{H\in\mathcal{H}_{d}(e)}\chi_{H(t)}(G)\enspace,$ (6.12)

where $\mathcal{H}_{d}(e)$, as defined in Definition 4.1, denotes the set of
graphs in the $(d,e)$-boundary, that is, all graphs $H$ such that
$\operatorname*{vc}(H)=d$ and if we add the edge $e$ to $H$, then the size of
the minimum vertex cover increases. Let the map $\operatorname{core}$ be as
guaranteed by Theorem 4.4. Recall that according to Proposition 4.3 the graph
$\operatorname{core}(H)$ is in the $(d,e)$-boundary $\mathcal{H}_{d}(e)$ if
and only if $H$ is. Hence the sets

$\displaystyle\bigl{\\{}\operatorname{core}^{-1}(F)=\mathcal{H}(F,E^{\star}_{F})\mid
F\in\mathcal{H}_{d}(e)\text{\leavevmode\nobreak\ and\leavevmode\nobreak\
}F\in\operatorname*{img}(\operatorname{core})\bigr{\\}}$ (6.13)

partition the $(d,e)$-boundary and we may thus write

$\displaystyle|\mu_{d}(Q)|$ $\displaystyle=\Big{|}n^{-k}\sum_{t\in
Q}\sum_{H\in\mathcal{H}_{d}(e)}\chi_{H(t)}(G)\Big{|}$ (6.14)
$\displaystyle=\Big{|}n^{-k}\sum_{\begin{subarray}{c}F\in\mathcal{H}_{d}(e)\\\
F\in\operatorname*{img}(\operatorname{core})\end{subarray}}\sum_{t\in
Q}\sum_{H\in\mathcal{H}(F,E^{\star}_{F})}\chi_{H(t)}(G)\Big{|}$ (6.15)
$\displaystyle\leq n^{-k}\sum_{\begin{subarray}{c}F\in\mathcal{H}_{d}(e)\\\
F\in\operatorname*{img}(\operatorname{core})\end{subarray}}\Big{|}\sum_{t\in
Q}\sum_{H\in\mathcal{H}(F,E^{\star}_{F})}\chi_{H(t)}(G)\Big{|}\enspace.$
(6.16)

By Lemma 6.5 each inner part can be bounded by $6\cdot 2^{|V(E(F))|}\cdot
p^{-|E(F)|}\cdot n^{k-\lambda\operatorname*{vc}(F)/4}$. Note that
$\operatorname*{vc}(F)=d$ and, according to Theorem 4.4, it holds that
$|V\bigl{(}E(F)\bigr{)}|\leq 3d$. Hence since $d\leq 2\eta\log n$ it holds
that $p^{-|E(F)|}\leq p^{-3d^{2}}=n^{6\eta d}$ and we may thus conclude that

$\displaystyle|\mu_{d}(Q)|$
$\displaystyle\leq\sum_{\begin{subarray}{c}F\in\mathcal{H}_{d}(e)\\\
F\in\operatorname*{img}(\operatorname{core})\end{subarray}}6\cdot 2^{3d}\cdot
n^{-d(\lambda/4-6\eta)}$ (6.17) $\displaystyle\leq 2^{3d(d+\log k)}\cdot
6\cdot 2^{3d}\cdot n^{-d(\lambda/4-6\eta)}$ (6.18) $\displaystyle\leq
6\cdot\big{(}n^{\lambda/4-12\eta}/(2k)^{3}\big{)}^{-d}\enspace,$ (6.19)

where we used Lemma 2.4 to bound the number of core graphs and relied, again,
on the assumption $d\leq 2\eta\log n$. This concludes the proof of 6.2. ∎

###  6.2 All Rectangles Are Approximately Non-Negative

In this section we prove that the measure is essentially non-negative on all
monomials modulo a concentration inequality whose proof we postpone to Section
7. For convenience we restate the precise claim.

See 6.3

Recall from the proof sketch given in Section 3.4 that we intend to decompose
any given rectangle into a small family $\mathcal{Q}$ of rectangles such that
each rectangle $Q\in\mathcal{Q}$ either

  1. 1.

contains few tuples,

  2. 2.

is a subrectangle of an edge axioms, or

  3. 3.

is a so-called _good rectangle_.

Since rectangles as described in Items 1 and 2 have negligible measure (see
Lemmas 3.5 and 6.2) essentially all the measure is concentrated on these good
rectangles. Hence if we can show that the measure concentrates around a
strictly positive value on such good rectangles, then the statement follows.
Let us introduce these _good rectangles_.

Before defining these rectangles formally, let us give an informal
description. A good rectangle $Q$ consists of two parts. The first part is
very small: on a few blocks the rectangle $Q$ only consists of single
vertices. Each vertex in this small part is adjacent to _all_ other vertices
in $Q$. Equivalently, on this small part we have a clique and the remaining
vertices in $Q$ are in the common neighborhood of this clique.

On the other blocks, where $Q$ does not consist of a single vertex, we require
that these blocks are large, of size at least $s=\operatorname{poly}(n)$. In
addition we also require that all common neighborhoods are bounded on this
large part. An illustration of a good rectangle can be found in Figure 3. The
formal definition follows.

######  Definition 6.6 (Good rectangle).

Let $G$ be a $k$-partite graph and let $s,\beta,p,d\in\mathbb{R}^{+}$ and
$R\subseteq[k]$. A rectangle $Q=\bigtimes_{i\in[k]}Q_{i}$ is
_$(s,\beta,p,d,R)$ -good for $G$_ if it satisfies the following properties.

  1. 1.

If $i\in R$, then $Q_{i}=\\{v_{i}\\}$; otherwise $|Q_{i}|\geq s$.

  2. 2.

For all $i\in R$ it holds that $N(v_{i})\supseteq\bigcup_{j\neq i}Q_{j}$.

  3. 3.

For all $S\subseteq[k]\setminus R$ of size at most $d$ and for all $i\not\in
R\cup S$, $G$ has $(\beta,p)$-bounded common neighborhoods from $Q_{S}$ to
$Q_{i}$.

Figure 3: The rectangle $Q$ is a good rectangles as the vertices in $R$ have
all vertices as neighbors, the blocks outside $R$ are large and small tuples
on these blocks have common neighborhoods of expected size

On good rectangles the measure is tightly concentrated around the expected
value. In Section 7 we prove the following concentration bound.

######  Lemma 6.7.

For constants $\varepsilon>0$ and $\eta<1/50$, for $n,k,d\in\mathbb{N}$ and
$p=n^{-2/D}\leq 1/2$ satisfying $d\leq\eta D$ and $D\leq k\leq n$ the
following holds. If $s\geq k^{13}n^{48\eta+\varepsilon}\log n$ and $G$ is a
$D$-well-behaved graph, then any $(s,1/k,p,d,R)$-good rectangle $Q$ for $G$
with $|R|=\ell<d$ satisfies

$\displaystyle\mu_{d}(Q)=p^{-\ell(k-(\ell+1)/2)}\,|Q|\,n^{-k}\big{(}1\pm
O(n^{-\varepsilon/8})\big{)}\enspace.$

In the remainder of this section we prove 6.3, assuming 6.7. As outlined in
Section 3.4, we intend to decompose any rectangle $Q$ into a small family
$\mathcal{Q}$ of rectangles such that each rectangle in $\mathcal{Q}$ either
contains few tuples, is a subrectangle of an edge axiom or is a good
rectangle. The following lemma summarizes our claim.

######  Lemma 6.8.

Let $G$ be a $D$-well-behaved graph, let $p=n^{-2/D}$, $d\leq D/4$ and $s\geq
Ck^{4}d\ln n/p^{2d}$ for some large enough constant $C$. Then any rectangle
$Q_{0}$ can be partitioned into a set of rectangles $\mathcal{Q}$ of size
$|\mathcal{Q}|\leq 2kn(2s)^{d}$ such that each $Q\in\mathcal{Q}$ satisfies
that either

  1. 1.

$Q$ is small: $|Q|\leq O\big{(}(n\cdot p^{d})^{k-d}\big{)}$,

  2. 2.

$Q$ is a subrectangle of an edge axiom, or

  3. 3.

$Q$ is $(s,1/k,p,d,R)$-good for $G$, where $R\subseteq[k]$ satisfies $|R|<d$.

Before proving Lemma 6.8, let us first show how 6.3 follows. The idea of the
proof is to apply Lemma 6.8 to a given rectangle $Q_{0}$ to obtain a
collection $\mathcal{Q}$ of rectangles. It holds that
$\mu_{d}(Q_{0})=\sum_{Q\in\mathcal{Q}}\mu_{d}(Q)$. By Lemma 3.5 there is a
$\delta>0$ such that all small rectangles $Q\in\mathcal{Q}$ satisfy
$|\mu_{d}(Q)|\leq n^{-\delta D}$ and similarly by 6.2 the same holds for
$Q\in\mathcal{Q}$ that are a subrectangle of an edge axiom. Further, by our
choice of parameters, the size of $\mathcal{Q}$ is small—we may think of it as
$n^{\delta D/2}$. We can thus lower bound

$\displaystyle\mu_{d}(Q_{0})=\sum_{Q\in\mathcal{Q}}\mu_{d}(Q)\geq-n^{-\delta
D/2}+\sum_{\begin{subarray}{c}Q\in\mathcal{Q}\\\ Q\text{\leavevmode\nobreak\
is good}\end{subarray}}\mu_{d}(Q)\enspace.$ (6.20)

6.7 states that the remaining good rectangles in the above sum have strictly
positive value. Thus $\mu_{d}(Q_{0})\geq-n^{-\delta D/2}$ as claimed. In what
follows we verify that this indeed holds for our choice of parameters.

###### Proof of 6.3.

Let $Q_{0}$ be any rectangle. Our goal is to show that
$\mu_{d}(Q_{0})\geq-n^{-cD}$, for a sufficiently small constant $c$. Let
$D\leq k\leq n^{1/66}$ be as in the statement of the lemma and choose
$\lambda=1-\varepsilon-\log(k)/\log(n)$ for sufficiently small constants
$\varepsilon>0$ and $\eta>0$ such that for $s=k^{13}n^{48\eta+\varepsilon}\log
n$ it holds that $s\leq n^{\lambda/4-12\eta-\varepsilon}/k^{3}$. Let $d=\eta
D\leq 2\eta\log n$ and $p=n^{-2/D}$. Note that for our choice of parameters it
holds that $s=\omega(k^{4}n^{4\eta}\log^{2}n)$, hence $s=\omega(k^{4}d\ln
n/p^{2d})$, and we may thus apply Lemma 6.8 with $d=\eta D$ to the rectangle
$Q_{0}$ to obtain a family $\mathcal{Q}$ of size at most $|\mathcal{Q}|\leq
2kn(2s)^{d}$.

By 6.2, any subrectangle of an axiom has measure bounded by
$O\big{(}\big{(}n^{\lambda/4-12\eta}/(2k)^{3}\big{)}^{-d}\big{)}$. Moreover,
according to Lemma 3.5 each small rectangle $Q\in\mathcal{Q}$ has measure of
magnitude at most

$\displaystyle|\mu_{d}(Q)|$ $\displaystyle\leq
O\big{(}|Q|n^{-k}k^{d}p^{-dk}\big{)}=O(n^{-d/2})\enspace,$ (6.21)

which is even smaller than the bound on axioms. Since $s\leq
n^{\lambda/4-12\eta-\varepsilon}/k^{3}$, we conclude that the measure of all
small rectangles and all subrectangles of axioms in $\mathcal{Q}$ add up, in
magnitude, to at most $|\mathcal{Q}|\cdot
O\big{(}\big{(}n^{\lambda/4-12\eta}/(2k)^{3}\big{)}^{-d}\big{)}\leq n^{-cD}$,
for a small enough constant $c$.

Hence the measure of $Q_{0}$ is mostly on the good rectangles of $\mathcal{Q}$
and on these rectangles we know that it is closely concentrated around a
strictly positive value. Indeed, we can apply 6.7 to any rectangle $Q$ which
is $(s,1/k,p,d,R)$-good for $G$ to conclude that

$\mu_{d}(Q)=p^{-\ell(k-(\ell+1)/2)}\,|Q|\,n^{-k}\big{(}1\pm
O(n^{-\varepsilon/8})\big{)}>0\enspace.$

This concludes the proof of 6.3 modulo 6.7 and Lemma 6.8. ∎

Let us proceed to prove Lemma 6.8.

###### Proof of Lemma 6.8.

Let us describe a recursive decomposition procedure that can be applied to any
rectangle $Q=\bigtimes_{i\in[k]}Q_{i}$.

If either $Q$ is small, a subrectangle of an axiom or $(s,1/k,p,d,R)$-good for
some $R\subseteq[k]$, then return $Q$. Otherwise decompose in the following
recursive fashion.

  1. 1.

If there is a singleton $Q_{i}=\\{v_{i}\\}$ such that
$N(v_{i})\not\supseteq\bigcup_{j\neq i}Q_{j}$, then we decompose $Q$ into
$|Q\setminus N(v_{i})|+1$ many rectangles as follows. Denote by
$u_{1},u_{2},\ldots,u_{m}$ the vertices in $Q$ that are not a neighbor of
$v_{i}$ and assume that they are in blocks $j_{1},j_{2},\ldots,j_{m}$. For
$\nu=1,\ldots,m$ we remove all tuples that contain the vertex $u_{\nu}$: let
$R^{0}=Q$ so we can write

$\displaystyle Q^{\nu}$ $\displaystyle=\\{u_{\nu}\\}\times\bigtimes_{j\neq
j_{\nu}}R^{\nu-1}_{j}\text{\qquad and}$ $\displaystyle
R^{\nu}=\big{(}R^{\nu-1}_{j_{\nu}}\setminus
u_{\nu}\big{)}\times\bigtimes_{j\neq j_{\nu}}R^{\nu-1}_{j}\enspace.$ (6.22)

Note that the rectangles $Q^{1},\ldots,Q^{m},R^{m}$ partition $Q$. Add the
$Q^{\nu}$ to the partition as these are subrectangles of edge axioms and
recursively decompose $R^{m}$.

  2. 2.

If there is a block $i\in[k]$ of size $1<|Q_{i}|\leq 2s$, then split $Q$ into
the $|Q_{i}|$ rectangles

$\displaystyle\bigl{\\{}\\{v_{i}\\}\times\bigtimes_{j\neq i}Q_{j}:v_{i}\in
Q_{i}\bigr{\\}}$ (6.23)

and recursively decompose each of these rectangles.

  3. 3.

Let $A$ be the set of blocks of size greater than $2s$. Because $G$ is
$D$-well-behaved, by Item 2 of Definition 5.4, it holds that $G$ has
$(2s,s,1/k,p,d)$-bounded error sets. In particular $Q_{A}$ has an error set
$U=\\{u_{1},\ldots,u_{m}\\}$ of size at most $s$. Decompose $Q$ into
$Q^{1},\ldots,Q^{m}$ and $R^{m}$ as in Item 1. By definition the rectangle
$R^{m}$ is $(s,1/k,p,d,[k]\setminus A)$-good and we may thus add it to the
partition. Recursively decompose the rectangles $Q^{1},\ldots,Q^{m}$.

This completes the description of the decomposition procedure. We need to
argue that the decomposition $\mathcal{Q}$ created by above procedure is not
too large, that is, of size $|\mathcal{Q}|\leq 2kn\cdot(2s)^{d}$. Let us start
with a few observations.

Because $G$ is $D$-well-behaved it holds that $G$ has $(1/k,p,D/4)$-bounded
common neighborhoods in every block (see Item 1 of Definition 5.4). Let $Q$ be
a rectangle with $d$ blocks of size $1$ and with the remaining vertices
contained in the common neighborhood of these singletons. All such rectangles
$Q$ are small. Thus the decomposition procedure does not need to decompose
such rectangles $Q$ any further.

Whenever we decompose a rectangle in Items 2 and 3 all rectangles that we need
to recursively decompose have one more singleton. Because we can stop
decomposing after identifying $d$ singletons and in Items 2 and 3 we create at
most $2s$ many rectangles that require further decomposition we end up with at
most $2(2s)^{d}$ many rectangles. We ignored the rectangles from Item 1 so
far. But each rectangle that requires further decomposition from Items 2 and 3
results in at most another $kn$ many rectangles from Item 1. Thus the size of
the family of rectangles is bounded by $2kn\cdot(2s)^{d}$. ∎

##  7 The Measure Is Concentrated on Good Rectangles

This section is devoted to proving 6.7 that states that the measure on good
rectangles is very well concentrated. We restate it here for convenience.

See 6.7

Let us introduce some notation and state 6.7 once more in a more convenient
form for what follows. Let $S_{i}^{\leq j}$ be the star with center $i$ and
leaves $[j]\setminus i$, that is, $S_{i}^{\leq j}$ consists of the vertices
$[k]$ and edges $\bigl{\\{}\\{i,j^{\prime}\\}:j^{\prime}\in[j],j^{\prime}\neq
i\bigr{\\}}$. For simplicity we denote by $S_{i}$ the star $S_{i}^{\leq k}$
and for $I\subseteq[k]$ let $S_{I}=\cup_{i\in I}S_{i}$.

######  Lemma 7.1.

For constants $\varepsilon>0$ and $\eta<1/50$, for $n,k,d\in\mathbb{N}$ and
$p=n^{-2/D}\leq 1/2$ satisfying $d\leq\eta D$, $D\leq k\leq n$ the following
holds. If $s\geq k^{13}n^{48\eta+\varepsilon}\log n$ and $G$ is a $D$-well-
behaved graph, then any $(s,1/k,p,d,R)$-good rectangle $Q$ for $G$ with
$|R|<d$ satisfies

$\displaystyle\Big{|}p^{-|S_{R}|}\,|Q|-\sum_{t\in
Q}\sum_{H\in\mathcal{H}_{d}}\chi_{H(t)}(G)\Big{|}\leq
O\bigl{(}p^{-|S_{R}|}\,|Q|\,n^{-\varepsilon/8}\bigr{)}\enspace.$

Before proving Lemma 7.1 let us verify that 6.7 indeed follows.

###### Proof of 6.7.

Recall that we defined our measure $\mu_{d}$ for a rectangle $Q$ as

$\displaystyle\mu_{d}(Q)=n^{-k}\sum_{t\in
Q}\sum_{H\in\mathcal{H}_{d}}\chi_{H(t)}(G)\enspace.$ (7.1)

Hence Lemma 7.1 implies, for the appropriate parameters, that all
$(s,1/k,p,d,R)$-good rectangles $Q$ for $G$ satisfy

$\mu_{d}(Q)=p^{-|S_{R}|}\,|Q|\,n^{-k}\big{(}1\pm
O(n^{-\varepsilon/8})\big{)}\enspace.\qed$

Let us give some intuition for the statement of Lemma 7.1. Clearly, if
$R=\emptyset$, then we are showing that the measure of a rectangle is tightly
concentrated around the expected value. Let us explain where the
$p^{-|S_{[\ell]}|}$ factor comes from.

Consider two blocks, say blocks $1$ and $2$. For vertices $v_{1}\in V_{1}$ and
$v_{2}\in V_{2}$ let us denote by $Q_{v_{1}v_{2}}$ the rectangle consisting of
all tuples that contain $v_{1}$ as well as $v_{2}$. According to 6.2, if there
is no edge between $v_{1}$ and $v_{2}$, then $\mu_{d}(Q_{v_{1}v_{2}})\approx
0$. Recall that the measure of the whole space is roughly $1$—hence if there
is an edge between vertices $v_{1}$ and $v_{2}$ as above, we expect that
$\mu(Q_{v_{1}v_{2}})$ “compensates” for the $0$ value rectangles, that is, we
expect that
$\mu(Q_{v_{1}v_{2}})\approx(|Q_{v_{1}v_{2}}|/n^{k}))\cdot(1/p)=1/pn^{2}$ if
the edge $v_{1}v_{2}$ is present. More generally, for $R\subseteq[k]$ we
expect to pick up a factor of $1/p$ for each edge that we condition on being
present between a vertex in $R$ and another block in $Q$. Lemma 7.1
establishes that this is indeed how the measure behaves.

Let us consider an $(s,1/k,p,d,R)$-good rectangle $Q$. For ease of exposition
let us assume that $R=[\ell]$, the other cases are analogous. In other words,
we assume, for all $i\in[\ell]$, that it holds that $|Q_{i}|=1$, these $\ell$
vertices form a clique and all edges from the first $\ell$ vertices to any
other vertex in $Q$ are present.

Recall that $\mathcal{H}_{d}$ is the family of graphs on $k$ labeled vertices
with a vertex cover of size at most $d$, and that
$\mathcal{H}_{d}(e)\subseteq\mathcal{H}_{d}$ denotes the set of graphs in the
$(d,e)$-boundary, as defined in Section 4. Finally, for two graphs $H$ and
$H^{\prime}$ defined over the same vertex set $V$ we denote by $H\setminus
H^{\prime}$ the graph over $V$ containing all edges of $H$ that are not
present in $H^{\prime}$.

We prove Lemma 7.1 in three steps. First we split the sum of Fourier
characters into two parts: the _main sum_ and some _boundary sums_. In a
second step we show that the boundary sums are negligible, i.e., that they add
up to very little. In the final step we then show that the main sum is tightly
concentrated around the expected value.

The following claim splits the sum of Fourier characters into the main sum and
several boundary sums. We postpone the straightforward proof until after we
prove Lemma 7.1.

######  Claim 7.2.

For $Q$ as in Lemma 7.1 and any tuple $t\in Q$ it holds that

$\displaystyle\begin{split}\sum_{H\in\mathcal{H}_{d}}\chi_{H(t)}(G)=p^{-|S_{[\ell]}|}&\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}\\\
S_{[\ell]}\subseteq H\end{subarray}}\chi_{(H\setminus S_{[\ell]})(t)}(G)\\\
&\quad{}+\sum_{i\in[\ell]}\sum_{j=i+1}^{k}p^{-|S_{[i-1]}\cup S_{i}^{\leq
j-1}|}\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}(\\{i,j\\})\\\ S_{[i-1]}\cup
S_{i}^{\leq j-1}\subseteq H\end{subarray}}\chi_{(H\setminus(S_{[i-1]}\cup
S_{i}^{\leq j-1}))(t)}(G)\enspace.\end{split}$

The sum with the factor $p^{-|S_{[\ell]}|}$ in 7.2 is the so-called _main
sum_. Intuitively most of the measure is in the main sum and it adds up to
approximately $p^{-|S_{[\ell]}|}$ times the size of $Q$, that is,

$\displaystyle p^{-|S_{[\ell]}|}\sum_{t\in
Q}\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}\\\ S_{[\ell]}\subseteq
H\end{subarray}}\chi_{(H\setminus S_{[\ell]})(t)}(G)\approx
p^{-|S_{[\ell]}|}\cdot|Q|\enspace.$ (7.2)

The latter sums in 7.2 with coefficients $p^{-|S_{[i-1]}\cup S_{i}^{\leq
j-1}|}$ are the so-called _boundary sums_. All of these sums turn out to be
tiny, that is, for $i\in[\ell]$ and $j+1\leq i\leq k$ it holds that

$\displaystyle p^{-|S_{[i-1]}\cup S_{i}^{\leq j-1}|}\Big{|}\sum_{t\in
Q}\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}(\\{i,j\\})\\\ S_{[i-1]}\cup
S_{i}^{\leq j-1}\subseteq H\end{subarray}}\chi_{(H\setminus(S_{[i-1]}\cup
S_{i}^{\leq j-1}))(t)}(G)\Big{|}\lesssim p^{-|S_{[\ell]}|}\cdot|Q|\cdot
n^{-(d-\ell)}\enspace.$ (7.3)

Both of the bounds corresponding to (7.2) and (7.3), and stated formally
below, are proven in Section 7.1. 7.2 together with these bounds will allow us
to conclude that the measure $\mu(Q)$ is tightly concentrated around
$p^{-|S_{[\ell]}|}\cdot|Q|$.

Let us first state the bound for the main sum. Intuitively we may think of the
below lemma as a version of Lemma 6.4 that holds on a local part of the graph.

######  Lemma 7.3.

For $G$ as in Lemma 7.1 the following holds for $p=n^{-2/D}$ and
$\ell<d\leq\eta D\leq 2\eta\log n$. If $s\geq
10\,k^{13}n^{48\eta+\varepsilon}\log n$, then all $(s,1/k,p,d,[\ell])$-good
rectangles $Q$ satisfy

$\displaystyle\Big{|}|Q|-\sum_{t\in
Q}\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}\\\ S_{[\ell]}\subseteq
H\end{subarray}}\chi_{(H\setminus S_{[\ell]})(t)}(G)\Big{|}\leq
O\big{(}|Q|\,n^{-\varepsilon/4}\big{)}\enspace.$

On the other hand, reminiscent of the edge axioms, we have that the boundary
sums are quite small. Note that, in contrast to Lemma 6.5, the bound below
depends on the size of the rectangle $Q$.

######  Lemma 7.4.

For $G$ as in Lemma 7.1 the following holds for any constant $0<\eta<1/50$ and
$\varepsilon>0$, for $p=n^{-2/D}$ and $\ell<d\leq\eta D\leq 2\eta\log n$. Let
$D\leq k\leq n$, $s\geq 10\,k^{2}n^{48\eta+\varepsilon}\log n$ and
$i\in[\ell]$. Then all $(s,1/k,p,d,[\ell])$-good rectangles $Q$ satisfy that
if $j\leq d+2$, then

$\displaystyle p^{-|S_{[i-1]}\cup S_{i}^{\leq j-1}|}\cdot\Big{|}\sum_{t\in
Q}\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}(\\{i,j\\})\\\ S_{[i-1]}\cup
S_{i}^{\leq j-1}\subseteq H\end{subarray}}\chi_{(H\setminus(S_{[i-1]}\cup
S_{i}^{\leq j-1}))(t)}(G)\Big{|}\leq
O\big{(}p^{-|S_{[\ell]}|}\,|Q|\,n^{-\varepsilon(d-\ell)/4}\big{)}\enspace,$

and, on the other hand, if $j\geq d+3$, then the above sum is empty.

Assuming these statements the proof of Lemma 7.1 boils down to a sequence of
syntactic manipulations.

###### Proof of Lemma 7.1.

According to 7.2 the expression

$\displaystyle\Big{|}p^{-|S_{[\ell]}|}\cdot|Q|-\sum_{t\in
Q}\sum_{H\in\mathcal{H}_{d}}\chi_{H(t)}(G)\Big{|}$ (7.4)

is equal to

$\displaystyle\begin{split}\Big{|}p^{-|S_{[\ell]}|}\cdot|Q|&-p^{-|S_{[\ell]}|}\sum_{t\in
Q}\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}\\\ S_{[\ell]}\subseteq
H\end{subarray}}\chi_{(H\setminus S_{[\ell]})(t)}(G)\\\
&\qquad{}\quad{}\,-\sum_{i\in[\ell]}\sum_{j=i+1}^{k}p^{-|S_{[i-1]}\cup
S_{i}^{\leq j-1}|}\sum_{t\in
Q}\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}(\\{i,j\\})\\\ S_{[i-1]}\cup
S_{i}^{\leq j-1}\subseteq H\end{subarray}}\chi_{(H\setminus(S_{[i-1]}\cup
S_{i}^{\leq j-1}))(t)}(G)\Big{|}\enspace.\end{split}$ (7.5)

Appealing to the triangle inequality, 7.3 and 7.4, we may upper bound (7.5) by

$\displaystyle\begin{split}p^{-|S_{[\ell]}|}\cdot\Big{|}|Q|-\sum_{t\in
Q}&\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}\\\ S_{[\ell]}\subseteq
H\end{subarray}}\chi_{(H\setminus S_{[\ell]})(t)}(G)\Big{|}\\\
&\quad{}+\sum_{i\in[\ell]}\sum_{j=i+1}^{d+2}p^{-|S_{[i-1]}\cup S_{i}^{\leq
j-1}|}\cdot\Big{|}\sum_{t\in
Q}\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}(\\{i,j\\})\\\ S_{[i-1]}\cup
S_{i}^{\leq j-1}\subseteq H\end{subarray}}\chi_{(H\setminus(S_{[i-1]}\cup
S_{i}^{\leq j-1}))(t)}(G)\Big{|}\\\ &\leq
O\Big{(}p^{-|S_{[\ell]}|}\,|Q|\,\big{(}n^{-\varepsilon/4}+\sum_{i\in[\ell]}\sum_{j=i+1}^{d+2}n^{-\varepsilon(d-\ell)/4}\big{)}\Big{)}\end{split}$
(7.6) $\displaystyle\leq
O\big{(}p^{-|S_{[\ell]}|}\,|Q|\,n^{-\varepsilon/8}\big{)}\enspace.$ (7.7)

Putting everything together we may conclude that (7.4) is upper bounded by the
expression in (7.7), as claimed. ∎

We now proceed to prove 7.2.

###### Proof of 7.2.

Suppose $\ell\geq 1$ and let us start by considering the edge $\\{1,2\\}$. We
first observe that for any $H$ such that $\\{1,2\\}\in H$, it holds that

$\chi_{H(t)}(G)=\frac{1-p}{p}\chi_{(H\setminus\\{1,2\\})(t)}(G)$ (7.8)

by definition of a good rectangle as every tuple $t\in Q$ contains the edge
$\\{1,2\\}$. Let us write

$\displaystyle\sum_{H\in\mathcal{H}_{d}}\chi_{H(t)}(G)$
$\displaystyle=\frac{1-p}{p}\cdot\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}\\\
\\{1,2\\}\in
H\end{subarray}}\chi_{(H\setminus\\{1,2\\})(t)}(G)+\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}\\\
\\{1,2\\}\not\in H\end{subarray}}\chi_{H(t)}(G)\enspace.$ (7.9)

Note that we can partition the set $\\{H\in\mathcal{H}_{d}:\\{1,2\\}\not\in
H\\}$ into two parts: the first part contains all the graphs in the boundary
of $\\{1,2\\}$, that is, graphs $H\in\mathcal{H}_{d}(\\{1,2\\})$, and the
second set contains all the remaining graphs. Note that graphs $H$ contained
in the latter set satisfy that $H\cup\\{1,2\\}\in\mathcal{H}_{d}$. Hence, for
every $t\in Q$, it holds that

$\displaystyle\begin{split}\sum_{H\in\mathcal{H}_{d}}\chi_{H(t)}(G)&=\frac{1-p}{p}\cdot\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}\\\
\\{1,2\\}\in H\\\ \end{subarray}}\chi_{(H\setminus\\{1,2\\})(t)}(G)\\\ &\hskip
99.58464pt+\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}\\\ \\{1,2\\}\in H\\\
\end{subarray}}\chi_{(H\setminus\\{1,2\\})(t)}(G)+\sum_{H\in\mathcal{H}_{d}(\\{1,2\\})}\chi_{H(t)}(G)\end{split}$
(7.10)
$\displaystyle=\frac{1}{p}\cdot\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}\\\
\\{1,2\\}\in H\\\
\end{subarray}}\chi_{(H\setminus\\{1,2\\})(t)}(G)+\sum_{H\in\mathcal{H}_{d}(\\{1,2\\})}\chi_{H(t)}(G)\enspace.$
(7.11)

If we continue to rewrite the first sum in the above fashion for edges
$\\{1,3\\},\ldots,\\{1,k\\}$ we obtain

$\displaystyle\begin{split}\sum_{H\in\mathcal{H}_{d}}\chi_{H(t)}(G)=p^{-(k-1)}\cdot\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}\\\
S_{1}\subseteq H\end{subarray}}&\chi_{(H\setminus S_{1})(t)}(G)\\\
&\qquad+\sum_{j=2}^{k}p^{-(j-2)}\cdot\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}(\\{1,j\\})\\\
S_{1}^{\leq j-1}\subseteq H\end{subarray}}\chi_{(H\setminus S_{1}^{\leq
j-1})(t)}(G)\enspace.\end{split}$ (7.12)

By iteratively applying the above arguments to vertices $i=2,\ldots,\ell$ we
conclude that

$\displaystyle\begin{split}\sum_{H\in\mathcal{H}_{d}}\chi_{H(t)}(G)&=p^{-|S_{[\ell]}|}\cdot\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}\\\
S_{[\ell]}\subseteq H\end{subarray}}\chi_{(H\setminus S_{[\ell]})(t)}(G)\\\
&\qquad{}+\sum_{i\in[\ell]}\sum_{j=i+1}^{k}p^{-|S_{[i-1]}\cup S_{i}^{\leq
j-1}|}\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}(\\{i,j\\})\\\ S_{[i-1]}\cup
S_{i}^{\leq j-1}\subseteq H\end{subarray}}\chi_{(H\setminus(S_{[i-1]}\cup
S_{i}^{\leq j-1}))(t)}(G)\enspace,\end{split}$ (7.13)

as claimed. ∎

###  7.1 Concentration of the Main Sum and Bounding the Boundary Sums

In this section we prove 7.3 and 7.4. We rely on the following lemma which
guarantees bounded character sum on arbitrary good rectangles, regardless of
size. This is in contrast to Item 4 of Definition 5.4 which only holds for
small rectangles. The more general statement follows from the latter by
splitting any large rectangle into many small rectangles while maintaining
goodness so that Item 4 of Definition 5.4 holds for these small rectangles.

######  Lemma 7.5.

Let $n,k\in\mathbb{N}$ and $s,\eta,D,d\in\mathbb{R}^{+}$ be such that
$d\leq\eta D$, $k\leq n$ and $s\geq 9\,k^{2}n^{2\eta}d\ln n$. If $p=n^{-2/D}$,
$G$ is a $D$-well-behaved graph and $F$ is a core graph, then all
$(s,1/k,p,d,R)$-good rectangles $Q$ satisfy, for $B=[k]\setminus R$, that

$\displaystyle\Big{|}\sum_{t\in
Q}\sum_{H\in\mathcal{H}(F,E^{\star}_{F}[B])}\chi_{H[B](t)}(G)\Big{|}=O\big{(}|Q|\cdot
p^{-{|E(F[B])|}}\cdot(s/10\,k\log
n)^{-\operatorname*{vc}(F[B])/4}\big{)}\enspace.$

We defer the proof of this lemma to Section 7.2. Before we proceed to prove
7.3 and 7.4 let us record two claims regarding vertex covers.

######  Claim 7.6.

Any minimum vertex cover of a graph $H$ contains all vertices of degree at
least $\operatorname*{vc}(H)+1$.

###### Proof.

Any vertex cover of $H$ that does not contain a vertex $u$ of degree at least
$\operatorname*{vc}(H)+1$ must contain all neighbors of $u$ and hence is of
size at least $\operatorname*{vc}(H)+1$. ∎

######  Claim 7.7.

For $i\in[k-1]$ and a graph $H$ on $k$ vertices it holds that if
$S_{[i]}\subseteq H$, then $\operatorname*{vc}(H\setminus
S_{[i]})=\operatorname*{vc}(H)-i$.

###### Proof.

If $i=k-1$, then $H=S_{[i]}$ is the complete graph on $k$ vertices and the
statement readily follows. Otherwise, as every vertex in $[i]$ has degree
$k-1\geq\operatorname*{vc}(H)+1$, it follows by 7.6 that the set $[i]$ is
contained in any minimum vertex cover $W$ of $H$. Since the vertices in
$W\setminus[i]$ have to cover the edges in $H\setminus S_{[i]}$, and since any
vertex cover $W^{\prime}$ of $H\setminus S_{[i]}$ is such that
$W^{\prime}\cup[i]$ is a vertex cover of $H$, we may conclude
$\operatorname*{vc}(H\setminus
S_{[i]})=\big{|}W\setminus[i]\big{|}=\operatorname*{vc}(H)-i$. ∎

Finally we also need to revisit our map $\operatorname{core}$ as we need a
good bound on the number of cores that the graphs containing $S_{[\ell]}$ are
mapped to. Before stating the claim let us recall the construction of the map
$\operatorname{core}$, as done in Section 4.2: given a graph $H$ with
lexicographically first vertex cover $W$ we let $U_{1}$ be the lex first
maximal set of vertices with a matching from $U_{1}$ to $W$ that covers all
vertices in $U_{1}$. Similarly we let $U_{2}$ be the lex first maximal set of
vertices in $H\setminus U_{1}$ with a matching from $U_{2}$ to $W$ covering
all vertices in $U_{2}$. Finally we define $\operatorname{core}(H)=H[W\cup
U_{1}\cup U_{2}]$.

######  Lemma 7.8.

Let $k,\ell,w\in\mathbb{N}$. If $\mathcal{F}_{\ell}(w)$ denotes the set of
cores $F\in\operatorname*{img}(\operatorname{core})$ such that
$S_{[\ell]}\subseteq F\cup E^{\star}_{F}$ and $\operatorname*{vc}(F)=\ell+w$,
then it holds that

$\displaystyle|\mathcal{F}_{\ell}(w)|\leq 2^{3w(\ell+w+\log k)}\enspace.$

###### Proof.

We argue that we can encode elements of the set of cores
$\mathcal{F}_{\ell}(w)$ by using few bits. Fix a core
$F\in\mathcal{F}_{\ell}(w)$ and let $W,U_{1},U_{2}$ as in the construction of
$F$ (see Section 4.2 and the discussion above). By definition we have that
$|W|=\ell+w$ and $|U_{2}|\leq|U_{1}|\leq\ell+w$.

According to 7.6 every vertex in $[\ell]$ is in any minimum vertex cover of
$F$ and thus contained in $W$; the lex first one. Hence there are only $w$
vertices in $W\cap\\{\ell+1,\ldots,k\\}$ to be specified. We spend
$\log\binom{k}{w}$ bits to specify this set. Once we have specified this set
we know that the lex smallest $\ell$ vertices outside $W$ are contained in
$U_{1}$ by construction. With another $\log\binom{k}{w}$ bits we may thus
encode the remaining vertices of $U_{1}$. Similarly, for $U_{2}$, we know that
the lex smallest $\ell$ vertices outside $W\cup U_{1}$ are in $U_{2}$. Hence
$\log\binom{k}{w}$ bits suffice to specify $U_{2}$.

At this point we know the relevant vertices of the core. It remains to encode
the edges. Some edges are given: all edges from $[\ell]$ to the rest of the
core are present. As such there are at most $w\cdot 3(\ell+w)$ many edges left
to be specified. The claim follows. ∎

With these claims at hand we are ready to prove 7.3 and 7.4. We start with 7.3
restated here for convenience.

See 7.3

###### Proof.

Let $B=\\{\ell+1,\ldots,k\\}$ and observe that $H\setminus S_{[\ell]}=H[B]$.
Further using that for $H=S_{[\ell]}$ it holds that $\sum_{t\in
Q}\chi_{(H\setminus S_{[\ell]})(t)}(G)=|Q|$ we may bound

$\displaystyle\Big{|}|Q|-\sum_{t\in
Q}\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}\\\ S_{[\ell]}\subseteq
H\end{subarray}}\chi_{(H\setminus S_{[\ell]})(t)}(G)\Big{|}$
$\displaystyle=\Big{|}\sum_{t\in
Q}\sum_{w=\ell+1}^{d}\sum_{\begin{subarray}{c}F\in\operatorname*{img}(\operatorname{core})\\\
\operatorname*{vc}(F)=w\end{subarray}}\sum_{\begin{subarray}{c}H\in\mathcal{H}(F,E^{\star}_{F})\\\
S_{[\ell]}\subseteq H\end{subarray}}\chi_{H[B](t)}(G)\Big{|}$ (7.14)
$\displaystyle=\Big{|}\sum_{w_{B}=1}^{d-\ell}\sum_{\begin{subarray}{c}F\in\operatorname*{img}(\operatorname{core})\\\
S_{[\ell]}\subseteq F\cup E^{\star}_{F}\\\
\operatorname*{vc}(F[B])=w_{B}\end{subarray}}\sum_{t\in
Q}\sum_{H\in\mathcal{H}(F,E^{\star}_{F}[B])}\chi_{H[B](t)}(G)\Big{|}$ (7.15)
$\displaystyle\leq\sum_{w_{B}=1}^{d-\ell}\sum_{\begin{subarray}{c}F\in\operatorname*{img}(\operatorname{core})\\\
S_{[\ell]}\subseteq F\cup E^{\star}_{F}\\\
\operatorname*{vc}(F[B])=w_{B}\end{subarray}}\Big{|}\sum_{t\in
Q}\sum_{H\in\mathcal{H}(F,E^{\star}_{F}[B])}\chi_{H[B](t)}(G)\Big{|}\enspace,$
(7.16)

where we appeal to 7.7 to obtain (7.15) and to the triangle inequality for
(7.16). Since by Theorem 4.4 it holds that
$\big{|}V\bigl{(}E(F)\bigr{)}\big{|}\leq 3\cdot\operatorname*{vc}(F)$ we may
apply 7.5 with $\big{|}E\bigl{(}F[B]\bigr{)}\big{|}\leq
3\cdot\operatorname*{vc}(F)\cdot\operatorname*{vc}\bigl{(}F[B]\bigr{)}\leq
3d\cdot\operatorname*{vc}\bigl{(}F[B]\bigr{)}$ to the inner expressions to
obtain the bound

$\displaystyle\Big{|}|Q|-\sum_{t\in
Q}\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}\\\ S_{[\ell]}\subseteq
H\end{subarray}}\chi_{H[B](t)}(G)\Big{|}$
$\displaystyle\leq|Q|\cdot\sum_{w_{B}=1}^{d-\ell}\sum_{\begin{subarray}{c}F\in\operatorname*{img}(\operatorname{core})\\\
S_{[\ell]}\subseteq F\cup E^{\star}_{F}\\\
\operatorname*{vc}(F[B])=w_{B}\end{subarray}}O\big{(}p^{-3d\cdot
w_{B}}\cdot(s/10\,k\log n)^{-w_{B}/4}\big{)}\enspace.$ (7.17)

Applying Lemma 7.8 along with the fact that $\ell+w_{B}\leq d\leq\eta D\leq
2\eta\log n$ allows us to conclude

$\displaystyle\Big{|}|Q|-\sum_{t\in
Q}\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}\\\ S_{[\ell]}\subseteq
H\end{subarray}}\chi_{H[B](t)}(G)\Big{|}$ $\displaystyle\leq
O\big{(}|Q|\cdot\sum_{w_{B}=1}^{d-\ell}2^{3w_{B}(d+\log
k)}\cdot(s/10\,n^{24\eta}k\log n)^{-w_{B}/4}\big{)}$ (7.18) $\displaystyle\leq
O\big{(}|Q|\cdot\sum_{w_{B}=1}^{d-\ell}(s/10\,k^{13}n^{48\eta}\log
n)^{-w_{B}/4}\big{)}$ (7.19) $\displaystyle\leq O\big{(}|Q|\cdot
n^{-\varepsilon/4}\big{)}\enspace,$ (7.20)

where we used that $\ell<d$, the bound $s\geq
10\,k^{13}n^{48\eta+\varepsilon}\log n$ and the fact that the final sum is a
geometric series. This completes the proof of 7.3 modulo 7.5. ∎

In order to show that the magnitude of the boundary sums is small, we need to
bound the number of core graphs that contain the edge set
$S_{i-1}\overset{.}{\cup}S_{i}^{\leq j-1}$. The bound from Lemma 7.8 turns out
to be insufficient as it is with respect to $d-(i-1)$, that is, the vertex
cover size outside the set $[i-1]$; as we can apply 7.5 with
$B=\\{\ell+1,\ldots,k\\}$ only, we get concentration with respect to the size
of the vertex cover in the set $\\{\ell+1,\ldots,k\\}$. This is a problem as
the vertex cover in the set $\\{\ell+1,\ldots,k\\}$ may be considerably
smaller than in the set $\\{i,\ldots,k\\}$. We overcome this difference in
parameters by leveraging the difference in the exponential factors
$p^{|S_{[i-1]}\cup S_{i}^{\leq j-1}|}$ and $p^{|S_{[\ell]}|}$ as follows.

######  Claim 7.9.

Let $w_{B},d,i,j,\ell\in[k]$, $i\leq\ell$, $B=\\{\ell+1,\ldots,k\\}$,
$E_{0}=S_{[i-1]}\overset{.}{\cup}S_{i}^{\leq j-1}$ and
$E_{1}=S_{[\ell]}\setminus E_{0}$. It holds that

$\displaystyle\sum_{\begin{subarray}{c}F\in\operatorname*{img}(\operatorname{core})\\\
F\in\mathcal{H}_{d}(\\{i,j\\})\\\ E_{0}\subseteq F\cup E^{\star}_{F}\\\
\operatorname*{vc}(F[B])=w_{B}\end{subarray}}2^{-|E_{1}\setminus
E^{\star}_{F}|}$ $\displaystyle\leq 3d^{2}\cdot\binom{k}{d}^{3}\cdot
2^{-k+3dw_{B}+4d+\ell}\enspace.$

###### Proof.

We first argue that the set over which we sum is not so large and then provide
a lower bound on $|E_{1}\setminus E^{\star}_{F}|$. These two bounds will
together imply the claim.

Let $C=\\{i,\ldots,k\\}$. Given parameters $w_{C}\leq d$ and $c\leq 3d$, we
consider cores $F\in\operatorname*{img}(\operatorname{core})$ such that
$F\in\mathcal{H}_{d}(\\{i,j\\})$, $E_{0}\subseteq F\cup E^{\star}_{F}$,
$\operatorname*{vc}(F[B])=w_{B}$, $\operatorname*{vc}(F[C])=w_{C}$ and
$|V\bigl{(}E(F)\bigr{)}\cap C|=c$. We claim that there are at most

$\displaystyle\binom{k}{d}^{3}\cdot 2^{\binom{c}{2}-\binom{c-w_{C}}{2}}$
(7.21)

such core graphs. Indeed, it is enough to specify the $w_{C}\leq d$ vertices
in a minimum vertex cover of $F[C]$, the other at most $2d$ vertices in
$V\bigl{(}E(F)\bigr{)}\cap C$, and the edges between vertices in the
identified minimum vertex cover of $F[C]$ and $V\bigl{(}E(F)\bigr{)}\cap C$.

In order to obtain a lower bound on $|E_{1}\setminus E^{\star}_{F}|$, note
that the edge set $E^{\star}_{F}$ consists only of edges with exactly one
endpoint in $V\bigl{(}E(F)\bigr{)}$. Hence all edges that are in $E_{1}$ and
that have both endpoints in $V\bigl{(}E(F)\bigr{)}$ are also in
$E_{1}\setminus E^{\star}_{F}$. These include edges between
$V\bigl{(}E(F)\bigr{)}\cap\\{i+1,\ldots,\ell\\}$ and
$V\bigl{(}E(F)\bigr{)}\cap C$. Note that all edges in $F[C]\setminus F[B]$
have one endpoint in $V\bigl{(}E(F)\bigr{)}\cap\\{i,\ldots,\ell\\}$ and thus

$\displaystyle|V\bigl{(}E(F)\bigr{)}\cap\\{i,\ldots,\ell\\}|\geq\operatorname*{vc}(F[C]\setminus
F[B])\geq\operatorname*{vc}(F[C])-\operatorname*{vc}(F[B])=w_{C}-w_{B}\enspace.$
(7.22)

This implies that $|V\bigl{(}E(F)\bigr{)}\cap\\{i+1,\ldots,\ell\\}|\geq
w_{C}-w_{B}-1$ and therefore

$\displaystyle|E_{1}\setminus
E^{\star}_{F}|\geq\binom{c}{2}-\binom{c-(w_{C}-w_{B}-1)}{2}\enspace.$ (7.23)

This bound, however, is not good enough for us. We need to also count edges in
$E_{1}\setminus E^{\star}_{F}$ that are adjacent to $i$ and that we have not
considered yet. Note that these include all the edges in $(E_{1}\setminus
E^{\star}_{F})\cap(\\{i\\}\times B)$. Let $\widetilde{N}(i)$ be the neighbors
of $i$ in the graph $F\cup E^{\star}_{F}$. In particular, we have that
$[j-1]\subseteq\widetilde{N}(i)$ since $S_{i}^{\leq j-1}\subseteq
E_{0}\subseteq F\cup E^{\star}_{F}$. This implies that
$\\{i\\}\times(B\setminus\widetilde{N}(i))\subseteq E_{1}\setminus
E^{\star}_{F}$ and therefore $|(E_{1}\setminus
E^{\star}_{F})\cap(\\{i\\}\times
B)|\geq|\\{i\\}\times(B\setminus\widetilde{N}(i))|\geq|B|-|\widetilde{N}(i)|$.
Now note that it must be the case that $\widetilde{N}(i)$ is in every minimum
vertex cover of $F$; otherwise we would have a minimum vertex cover of $F$
that either contains $i$ (and then $F$ would not be in the
$(d,\\{i,j\\})$-boundary) or is not a vertex cover of the graph $F\cup
E^{\star}_{F}$. This implies that $|\widetilde{N}(i)|\leq d$. We may thus
conclude that

$\displaystyle|E_{1}\setminus
E^{\star}_{F}|\geq\binom{c}{2}-\binom{c-(w_{C}-w_{B}-1)}{2}+k-\ell-d\enspace.$
(7.24)

Using the bounds in Equation 7.21 and Equation 7.24 we may write

$\displaystyle\sum_{\mathclap{\begin{subarray}{c}F\in\operatorname*{img}(\operatorname{core})\\\
F\in\mathcal{H}_{d}(\\{i,j\\})\\\ E_{0}\subseteq F\cup E^{\star}_{F}\\\
\operatorname*{vc}(F[B])=w_{B}\\\ \operatorname*{vc}(F[C])=w_{C}\\\
|V(E(F))\cap C|=c\end{subarray}}}\,2^{-|E_{1}\setminus E^{\star}_{F}|}$
$\displaystyle\leq\binom{k}{d}^{3}\cdot
2^{\binom{c}{2}-\binom{c-w_{C}}{2}}\cdot
2^{-\binom{c}{2}+\binom{c-(w_{C}-w_{B}-1)}{2}-k+\ell+d}$ (7.25)
$\displaystyle=\binom{k}{d}^{3}\cdot
2^{(c-w_{C})(w_{B}+1)-\binom{w_{B}+1}{2}-k+\ell+d}\enspace.$ (7.26)

Since $c\leq 3d$, we have that $(c-w_{C})(w_{B}+1)-\binom{w_{B}+1}{2}\leq
3d(w_{B}+1)$. Finally, we need to sum over all possible values of $w_{C}$ and
$c$. Since $w_{C}\leq d$ and $c\leq 3d$, the statement follows. ∎

In the remainder of this section we prove that boundary sums are small. For
convenience we restate the claim. See 7.4

###### Proof.

Let us first consider the case $j\geq d+3$. For all such $j$ it holds that all
graphs $H$ we sum over contain the edges $S_{[i-1]}\cup S_{i}^{\leq d+2}$. As
vertex $i$ has degree at least $d+1$ and $\operatorname*{vc}(H)=d$, according
to 7.6, it holds that $i$ is contained in any minimum vertex cover of $H$.
This implies that there are no graphs $H$ satisfying $S_{[i-1]}\cup
S_{i}^{\leq d+2}\subseteq H$ that are also in the $(d,\\{i,j\\})$-boundary.
Thus the considered sum is empty for $j\geq d+3$.

We now assume $j\leq d+2$. We can also assume $j>i$ as otherwise the edge
$\\{i,j\\}$ is in any graph we consider and hence cannot be a boundary edge.
Recall that $i\leq\ell$, and let $E_{0}=S_{[i-1]}\cup S_{i}^{\leq j-1}$,
$E_{1}=S_{[\ell]}\setminus E_{0}$ and $B=\\{\ell+1,\ldots k\\}$. Similar to
the proof of 7.3, though this time we rely on Proposition 4.3, we may rewrite
the boundary sum as

$\displaystyle\sum_{t\in
Q}\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}(\\{i,j\\})\\\ E_{0}\subseteq
H\end{subarray}}\chi_{(H\setminus E_{0})(t)}(G)$ $\displaystyle=\sum_{t\in
Q}\sum_{\begin{subarray}{c}F\in\operatorname*{img}(\operatorname{core})\\\
F\in\mathcal{H}_{d}(\\{i,j\\})\end{subarray}}\sum_{\begin{subarray}{c}H\in\mathcal{H}(F,E^{\star}_{F})\\\
E_{0}\subseteq H\end{subarray}}\chi_{(H\setminus E_{0})(t)}(G)$ (7.27)
$\displaystyle=\sum_{\begin{subarray}{c}F\in\operatorname*{img}(\operatorname{core})\\\
F\in\mathcal{H}_{d}(\\{i,j\\})\\\ E_{0}\subseteq F\cup
E^{\star}_{F}\end{subarray}}\sum_{t\in
Q}\sum_{H\in\mathcal{H}(F,E^{\star}_{F}\setminus E_{0})}\chi_{(H\setminus
E_{0})(t)}(G)\enspace.$ (7.28)

We now focus on the inner two sums. Since
$S_{[\ell]}=E_{0}\overset{.}{\cup}E_{1}$ we have that $\chi_{(H\setminus
E_{0})(t)}(G)=\chi_{(H\cap E_{1})(t)}(G)\cdot\chi_{(H\setminus
S_{[\ell]})(t)}(G)$. By definition of a good rectangle, for all $t\in Q$, the
edges $S_{[\ell]}(t)$ are present in $G$ thus $\chi_{(H\cap
E_{1})(t)}(G)=\left((1-p)/p\right)^{|H\cap E_{1}|}$. Let $T=|E^{\star}_{F}\cap
E_{1}|$. Using that $H\setminus S_{[\ell]}=H[B]$ and $E^{\star}_{F}\setminus
S_{[\ell]}=E^{\star}_{F}[B]$ we can derive that

$\displaystyle\sum_{t\in Q}\sum_{H\in\mathcal{H}(F,E^{\star}_{F}\setminus
E_{0})}\chi_{(H\setminus E_{0})(t)}(G)$ $\displaystyle=\sum_{t\in
Q}\sum_{H\in\mathcal{H}(F,E^{\star}_{F}\setminus E_{0})}\chi_{(H\cap
E_{1})(t)}(G)\cdot\chi_{(H\setminus S_{[\ell]})(t)}(G)$ (7.29)
$\displaystyle=\sum_{t\in Q}\sum_{H\in\mathcal{H}(F,E^{\star}_{F}\setminus
S_{[\ell]})}\sum_{\nu=0}^{T}\binom{T}{\nu}\left(\frac{1-p}{p}\right)^{\nu}\chi_{H\setminus
S_{[\ell]}(t)}(G)$ (7.30) $\displaystyle=\sum_{t\in
Q}\sum_{H\in\mathcal{H}(F,E^{\star}_{F}[B])}\chi_{H[B](t)}(G)\sum_{\nu=0}^{T}\binom{T}{\nu}\left(\frac{1-p}{p}\right)^{\nu}$
(7.31) $\displaystyle=p^{-T}\sum_{t\in
Q}\sum_{H\in\mathcal{H}(F,E^{\star}_{F}[B])}\chi_{H[B](t)}(G)\enspace.$ (7.32)

Appealing to the triangle inequality we may thus bound

$\displaystyle\begin{split}\Big{|}\sum_{t\in
Q}\sum_{\begin{subarray}{c}H\in\mathcal{H}_{d}(\\{i,j\\})\\\ E_{0}\subseteq
H\end{subarray}}\chi_{(H\setminus
E_{0})(t)}(G)\Big{|}&=\Big{|}\sum_{\begin{subarray}{c}F\in\operatorname*{img}(\operatorname{core})\\\
F\in\mathcal{H}_{d}(\\{i,j\\})\\\ E_{0}\subseteq F\cup
E^{\star}_{F}\end{subarray}}p^{-|E^{\star}_{F}\cap E_{1}|}\sum_{t\in
Q}\sum_{H\in\mathcal{H}(F,E^{\star}_{F}[B])}\chi_{H[B](t)}(G)\Big{|}\end{split}$
(7.33)
$\displaystyle\leq\sum_{\begin{subarray}{c}F\in\operatorname*{img}(\operatorname{core})\\\
F\in\mathcal{H}_{d}(\\{i,j\\})\\\ E_{0}\subseteq F\cup
E^{\star}_{F}\end{subarray}}p^{-|E^{\star}_{F}\cap E_{1}|}\Big{|}\sum_{t\in
Q}\sum_{H\in\mathcal{H}(F,E^{\star}_{F}[B])}\chi_{H[B](t)}(G)\Big{|}\enspace.$
(7.34)

Fix $F$ and let $w_{B}=\operatorname*{vc}(F[B])$. Note that the characters we
sum in Equation 7.34 solely depend on edges between blocks of size at least
$s$. We may thus apply 7.5 to the inner expressions and, using that
$p^{-|E(F[B])|}\leq
p^{-{3\cdot\operatorname*{vc}(F)\cdot\operatorname*{vc}(F[B])}}=p^{-{3dw_{B}}}\leq
n^{6\eta w_{B}}$ and $s\geq 10\,k^{2}n^{48\eta+\varepsilon}\log n$, we obtain

$\displaystyle\Big{|}\sum_{t\in
Q}\sum_{H\in\mathcal{H}(F,E^{\star}_{F}[B])}\chi_{H[B](t)}(G)\Big{|}$
$\displaystyle\leq
h(w_{B})=O\big{(}|Q|\cdot(n^{24\eta+\varepsilon}k)^{-w_{B}/4}\big{)}\enspace.$
(7.35)

From Lemma 7.8 we know that there are at most $2^{3(d-(i-1))(d+\log k)}$ many
cores we sum over. The problem is that this bound does not depend on $w_{B}$
and hence applying Lemma 7.8 to Equation 7.34 does not readily result in the
desired bound.