Limits of CSP Problems and Efficient
Parameter Testing
arXiv:1406.3514v2 [] 4 Aug 2016

Marek Karpinski∗

Roland Markó†

Abstract

We present a unified framework on the limits of constraint satisfaction problems (CSPs) and efficient parameter testing which depends only on array exchangeability and the method of cut decomposition without recourse to the
weakly regular partitions. In particular, we formulate and prove a representation theorem for compact colored r-uniform directed hypergraph (r-graph) limits,
and apply this to rCSP limits. We investigate the sample complexity of testable
r-graph parameters, we discuss the generalized ground state energies and demonstrate that they are efficiently testable.

1

Introduction

We study the limits and efficient parameter testing properties of Maximum Constraint Satisfaction Problems of arity r (MAX-rCSP or rCSP for short), c.f. e.g., [4]. These two topics,
limiting behavior and parameter estimation, are treated in the paper to a degree separately,
as they require a different set of ideas and could be analyzed on their own right. The establishment of the underlying connection between convergence and testability is one of the
main applications of the limit theory of dense discrete structures, see [10], [11].
In the first part of the paper we develop a general framework for the above CSP problems which depends only on the principles of the array exchangeability without a recourse
to the weakly regular partitions used hitherto in the general graph and hypergraph settings.
Those fundamental techniques and results were worked out in a series of papers by Borgs,
Chayes, Lovász, Sós, Vesztergombi and Szegedy [10],[11],[24], and [26] for graphs including
connections to statistical physics and complexity theory, and were subsequently extended to
Key words and phrases. Approximation, graphs, hypergraphs, graph limits, constraint satisfaction problems, hypergraph parameter testing, exchangeability.
∗
Dept. of Computer Science and the Hausdroff Center for Mathematics, University of Bonn. Supported
in part by DFG grants, the Hausdorff grant EXC59-1. Research partly supported by Microsoft Research
New England. E-mail: marek@cs.uni-bonn.de
†
Hausdorff Center for Mathematics, University of Bonn. Supported in part by a Hausdorff scholarship.
E-mail: roland.marko@hcm.uni-bonn.de

1

hypergraphs by Elek and Szegedy [15] via the ultralimit method. The central concept of
r-graph convergence is defined through convergence of sub-r-graph densities, or equivalently
through weak convergence of probability measures on the induced sub-r-graph yielded by
uniform node sampling. Our line of work particularly relies on ideas presented in [14] by
Diaconis and Janson, where the authors shed some light on the correspondence between combinatorial aspects (that is, graph limits via weak regularity) and the probabilistic viewpoint
of sampling: Graph limits provide an infinite random graph model that has the property
of exchangeability. The precise definitions, references and results will be given in Section 2,
here we only formulate our main contribution informally: We prove a representation theorem
for compact colored r-uniform directed hypergraph limits. This says that every limit object
in this setup can be transformed into a measurable function on the (2r − 2)-dimensional unit
cube that takes values from the probability distributions on the compact color palette, see
Theorem 2.12 below. This extends the result of Diaconis and Janson [14], and of Lovász
and Szegedy [25]. As an application, the description of the limit space of rCSPs is presented
subsequent to the aforementioned theorem.
The second part of the paper, Sections 3 to 5, is dedicated to the introduction of a
notion of efficient parameter testability of r-graphs and rCSP problems. We use the limit
framework from the first part of the paper to formulate several results on it, which are proved
with the aid of the cut decomposition method. We set our focus especially on parameters
called ground state energies and study variants of them. These are in close relationship
with MAX-rCSP problems, our results can be regarded as the continuous generalization of
the former. We rely on the notion of parameter testing and sample complexity, that was
introduced by Goldreich, Goldwasser, and Ron [17] and was employed in the graph limit
theory in [11]. A graph parameter is testable in the sense of [11], when its value is estimable
through a uniform sampling process, where the sample size only depends on the desired error
gap, see Definition 3.3 below for the precise formulation. The characterization of the real
functions on the graph space was carried out in [11], the original motivation of the current
paper was to provide an analogous characterization for efficiently testable parameters. These
latter are parameters, whose required sample size for the estimation is at most polynomial
in the multiplicative inverse of the error.
The investigation of such parameters has been an active area of research for the finite
setting in complexity theory. The method of exhaustive sampling in order to approximately
solve NP-hard problems was proposed by Arora, Karger and Karpinski [5], their upper bound
on the required sample size was still logarithmically increasing in the size of the problem. The
approach in [5] enabled the employment of linear programming techniques. Subsequently, the
testability of MAX-CUT was shown in [17], explicit upper bounds for the sample complexity
in the general boolean MAX-rCSP were given by Alon, F. de la Vega, Kannan and Karpinski
[4] using cut decomposition of r-arrays and sampling, that was inspired by the introduction
of weak regularity by Frieze and Kannan [16]. In [4] and [16], the design of polynomial time
approximation schemes (PTAS) in order to find not only an approximate value for MAXrCSP, but also an assignment to the base variables that certify this value was an important
subject, we did not pursue the generalization regarding this aspect in the current work. The

2

achievements of these two aforementioned contributions turned out to be highly influential,
and took also a key role in the first elementary treatment of graph limits and in the definition
of the δ -metric in [10] that defines an equivalent topology on the limit space to the subgraph
density convergence.
The best currently known upper bound on the sample complexity of MAX-rCSP is
O(ε−4 ), and has been shown by Mathieu and Schudy [27], see also Alon, F. de la Vega,
Kannan and Karpinski [4]. Unfortunately, the approach of [27] does not seem to have a natural counterpart in the continuous setting, although one can use their result on the sample
to achieve an improved upper bound on the sample complexity. We mention that for the
original problem we do not aim to produce an assignment for MAX-rCSP, or a partition for
the ground state energy whose evaluation is nearly optimal as opposed to the above works,
although we believe this could be done without serious difficulties.
Our contribution in the second part of the paper is the following. By employing a refined
version of the proof of the main result of [4] adapted to the continuous setting we are able to
prove the analogous efficient testability result for a general finite state space for ground state
energies, see Theorem 4.4 in Section 4 for a precise formulation. Among the applications
of this development we analyze the testability of the microcanonical version of ground state
energies providing the first explicit upper bounds on efficiency. For the finite version a similar
question was investigated by F. de la Vega, Kannan and Karpinski [13] by imposing additional
global constraints (meaning a finite number of them with unbounded arity). Furthermore,
the continuous version of the quadratic assignment problem is treated the first time in a
sample complexity context, this subject is related to the recent contributions to the topic of
approximate graph isomorphism and homomorphism, see [22] and [8].

1.1

Outline of the paper

The organization of this paper is as follows. In Section 2 we develop the limit theory for Kdecorated r-uniform directed hypergraphs with reference to previously known special (and
in some way generic) cases, and use the representation of the limit to describe the limit
space of rCSP problems. In Section 3 the basic notion of efficiency in context of parameter
testing is given with some additional examples. The subsequent Section 4 contains the
proof of Theorem 4.4 regarding ground state energies of r-graphons, and in the following
Section 5 some variants are examined, in particular microcanonical energies and the quadratic
assignment problem. We summarize possible directions of further research in Section 6.

2

Limit theory and related notions

We will consider the objects called rCSP formulas that are used to define instances of
the decision and optimization problems called rCSP and MAX-rCSP, respectively. In the
current framework a formula consists of a variable set and a set of boolean or integer valued
functions. Each of these functions is defined on a subset of the variables, and the sets of
possible assignments of values to the variables are uniform. Additionally, it will be required
3

that each of the functions, which we will call constraints in what follows, depend exactly
on r of the variables.
For the treatment of an rCSP (of a MAX-rCSP) corresponding to a certain formula we
are required to simultaneously evaluate all the constraints of the formula by assigning values
to each of the variables in the variable set. If we deal with an rCSP optimization problem
on some combinatorial structure, say on graphs, then the formula corresponding to a certain
graph has to be constructed according to the optimization problem in question. The precise
definitions will be provided next.
Let r ≥ 1, K be a finite set, and f be a boolean-valued function f : K r → {0, 1} on
r variables (or equivalently f ⊆ K r ). We call f a constraint-type on K in r variables,
C = C(K, r) denotes the set of all such objects.
Definition 2.1 (rCSP formula). Let V = {x1 , x2 , . . . , xn } be the set of variables, xe =
(xe1 , . . . , xer ) ∈ V r and f a constraint-type on K in r variables. We call an n-variable
function ω = (f ; xe ) : K V → {0, 1} with ω(l1 , . . . , ln ) = f (le1 , . . . , ler ) a constraint on V in r
variables determined by an r-vector of constrained variables and a constraint type.
We call a collection F of constraints on V (F ) = {x1 , x2 , . . . , xn } in r variables of type
C(K, r) for some finite K an rCSP formula.

Two constraints (f1 ; xe1 ) and (f2 ; xe2 ) are said to be equivalent if they constrain the same
r variables, and their evaluations coincide, that is, whenever there exists a π ∈ Sr such that
e1 = π(e2 ) (here π permutes the entries of e2 ) and f1 = π̂(f2 ), where [π̂(f )](l) = f (π(l)).
Two formulas F1 and F2 are equivalent if there is a bijection φ between their variable sets
such that there is a one-to-one correspondence between the constraints of F1 and F2 such
that the corresponding pairs (f1 ; xe1 ) ∈ F1 and (f2 ; xe2 ) ∈ F2 satisfy (f1 ; φ(xe1 )) ≡ (f2 ; xe2 ).
In the above definition the set of states of the variables in V (F ) denoted by K is not
specified for each formula, it will be considered as fixed similar to the dimension r whenever
we study a family of rCSPs. We say that F is symmetric, if it contains only constraints with
constraint-types which are invariant under the permutations of the constrained variables.
When we relax the notion of the types to be real or K-valued functions on K r with K being
a compact space, then we speak of weighted rCSP formulas.
The motivation for the name CSP formula is immediately clear from the notation used
in Theorem 2.1 if we consider constraints to be satisfied at some point in K n , whenever they
evaluate to 1 there. Most problems defined on these objects ask for parameters that are, in
the language of real analysis, global or conditioned extreme values of the objective function
given by an optimization problem and a formula. A common assumption is that equivalent
formulas should get the same parameter value.

Definition 2.2 (MAX-rCSP). Let F be an rCSP formula over a finite domain K. Then
the MAX-rCSP value of F is given by
MAX−rCSP(F ) = max

l∈K V (F )

X

ω(l),

ω=(f ;xe )∈F

and F is satisfiable, if MAX−rCSP(F ) = |{ ω | ω = (f ; xe ) ∈ F }|.
4

(2.1)

Such problems are for example MAX-CUT, fragile MAX-rCSP, MAX-3-SAT, and NotAll-Equal-3-SAT, where only certain constraint types are allowed for instances, or MAXBISECTION, where additionally only specific value assignments are permitted in the above
maximization. In general, formulas can also be viewed as directed r-graphs, whose edges
are colored with constraint types (perhaps with multiple types), and we will exploit this
representation in our analysis.
Typically, we will not store and recourse to an rCSP formula F as it is given by its
definition above, but we will only consider the r-array tuple (F z )z∈K r , where
X X
f (zφ(1) , . . . , zφ(r) )
(2.2)
F z (e) =
φ∈Sr (f ;xφ(e) )∈F

for each e ∈ [n]r . The data set (F z )z∈K r is called the evaluation representation of F , or short
eval(F ), we regard eval(F ) as a parallel colored (with colors from [q]r ) multi-r-graph, see
below. We impose a boundedness criteria on CSPs that will apply throughout the paper,
that means we fix d ≥ 1 for good, and require that kF z k∞ ≤ d for every z ∈ K r and CSP
formula F with eval(F ) = (F z )z∈K r in consideration. We note that for each z ∈ K r , e ∈ [n]r
and φ ∈ Sr we have the symmetry F z (e) = F zφ(1) ,...,zφ(r) (eφ(1) , . . . , eφ(r) ), also, on the diagonal
F z is 0.
The main motivation for what follows in the current section originates from the aim to
understand the long-range behavior of a randomly evolving rCSP formula together with the
value of the corresponding MAX-rCSP by making sense of a limiting distribution. This task
is equivalent to presenting a structural description of rCSP limits analogous to the graph
limits of [24].
The convergence notion should agree with parameter estimation via sampling. In this
setting we pick a set of variables of fixed size at random from the constrained set V (F ) of
an rCSP formula F defined on a large number of variables, and ask for all the constraints
in which the sampled variables are involved and no other, this is referred to as the induced
subformula on the sample. Then we attempt to produce some quantitative statement about
the parameter value of the original formula by relying only on the estimation of the corresponding value of the parameter on a subformula, see Theorem 3.3.
Having formally introduced the notion of rCSP formulas and MAX-rCSP, we proceed to
the outline of the necessary notation and to the analysis of the limit behavior regarding the
colored hypergraph models that are used to encode these formulas.

2.1

Limits of K-colored r-uniform directed hypergraphs

Let K be a compact Polish space and r ≥ 1 an integer. Recall that a space K is called Polish
if it is a separable completely metrizable topological space. In what follows we will consider
the limit space of K-colored r-uniform directed hypergraphs, or with different words r-arrays
with non-diagonal entries from K, and the diagonal entries are occupied by a special element
which also can be in K, but in general this does not have to be the case.
The basic content of the current subsection starts with the general setting given above,
CSPs will be considered as a special case in this topic whose limit characterization will be
5

derived at the end. Some of the basic cases are already settled regarding the representation of
the limits, we refer to Lovász and Szegedy [24], [25], [23] for the r = 2, general K, undirected
case, to Elek and Szegedy [15] for the general r, K = {0, 1}, undirected case; and Diaconis and
Janson [14] for r = 2, K = {0, 1}, directed and undirected case. These three approaches are
fundamentally different in their proof methodology (they rely on weak regularity, ultralimits,
and exchangeability principles respectively) and were further generalized or applied by Zhao
[30] to general r; respectively by Aroskar [7] to the directed case; respectively by Austin [9]
general r and by Janson [20] to the directed case where the graph induces a partial order on
the vertex set.
Definition of convergence Let C denote space C(K) of continuous functionals on K, and
let F ⊂ C be a countable generating set with kf k∞ ≤ 1 for each f ∈ F , that is, the linear
subspace generated by F is dense in C in the L∞ -norm.
Denote by Π(S) = Πr (S) the set of all unlabeled S-decorated directed r-uniform hypergraphs for some arbitrary set S, where we will suppress r in the notation, when it is clear
which r is meant (alternatively, Π(S) denotes the isomorphism classes of the node labeled
respective objects). The set Πk (S) denotes the elements of Π(S) of vertex cardinality k. Let
G(k, F ) denote the random induced subformula of F on the set S ⊂ V (F ) that is chosen uniformly among the subsets of V (F ) of cardinality k. We define the homomorphism densities
next.
Definition 2.3. Let K be an arbitrary set or space, and C(K) be the set of continuous
functionals on K. If for some r ≥ 1 F ∈ Πr (C(K)) is a uniform directed graph with
V (F ) = [k] and G ∈ Πr (K), then the homomorphism density of F in G is defined as
1
t(F, G) =
|V (G)|k

X

k
Y

F (i1 , . . . , ir )(G(φ(i1 ), . . . , φ(ir ))).

(2.3)

φ : [k]→V (G) i1 ,...,ir =1

The injective homomorphism density tinj (F, G) is defined similarly, with the difference
that the average of the products is taken over all injective φ maps (normalization changes
accordingly).
In the special case when K is finite we can associate to the elements of Π(K) functions in
Π(C(K)) through replacing the edge colors in K by the corresponding indicator functions.
Note that this way if F, G ∈ Πr , then tinj (F, G) = P(G(k, G) = F ).
Let the map τ be defined as τ (G) = (t(F, G))F ∈Π(F ) ∈ [0, 1]Π(F ) for each G ∈ Π(K). We
set Π(K)∗ = τ (Π(K)) ⊂ [0, 1]Π(F ) , and Π(K)∗ to the closure of Π(K)∗ . Also, let Π(K)+ =
{ (τ (G), 1/|V (G)|) | G ∈ Π(K) } ⊂ [0, 1]Π(F ) × [0, 1], and let Π(K)+ be the closure of Π(K)+ .
The function τ + (G) = (τ (G), 1/|V (G)|) will be useful for our purposes, because, opposed
to τ , it is injective, which can be verified easily. For any F ∈ Π(F ) the function t(F, .) on
Π(K) can be uniquely continuously extended to a function t(F, .) on Π(K)+ , this is due to
the compactness of [0, 1]Π(F ) × [0, 1]. For an element Γ ∈ Π(K)+ \ Π(K)+ , let t(F, Γ) for
F ∈ Π(F ) denote the real number in [0, 1] that is the coordinate of Γ corresponding to F .
6

+
The functions τinj (G) and τinj
(G), and the sets Πinj (K) = τinj (Π(K)) and Πinj (K)+ are
defined analogously. It was shown in [24] that

|tinj (F, G) − t(F, G)| ≤

|V (F )|2kF k∞
2|V (G)|

(2.4)

for any pair F ∈ Π(C) and G ∈ Π(K).
The precise definition of convergence will be given right after the next theorem which is
analogous to a result of [25].
Theorem 2.4. Let (Gn )∞
n=1 be a random sequence in Π(K) with |V (Gn )| tending to infinity
in probability. Then the following are equivalent.
+
(1) The sequence (τ + (Gn ))∞
n=1 converges in distribution in Π(K) .

(2) For every F ∈ Π(F ), the sequence (t(F, Gn ))∞
n=1 converges in distribution.
(3) For every F ∈ Π(C), the sequence (t(F, Gn ))∞
n=1 converges in distribution.
(4) For every k ≥ 1, the sequence (G(k, Gn ))∞
n=1 of random elements of Π(K) converges in
distribution.
If any of the above apply, then the respective limits in (2) and (3) are t(F, Γ) with Γ being
a random element of Π(K)+ given by (1), and also Γ ∈ Π(K)+ \ Π(K)+ , almost surely.
If t(F, Gn ) in (2) and (3) is replaced by tinj (F, Gn ), then the equivalence of the four
statements still persists and the limits in (2) and (3) are t(F, Γ).
If every Gn is concentrated on some single element of Π(K) (non-random case), then
the equivalence holds with the sequences in (1), (2), and (3) being numerical instead of
distributional, while (4) remains unchanged.
Proof. The equivalence of (1) and (2) is immediate. The implication from (3) to (2) is also
clear by definition.
For showing that (2) implies (3), we consider first an arbitrary F ∈ Π(hF i), where hF i is
the linear space generated by F . Then there exist F 1 , . . . , F l ∈ Π(F ) on the same vertex set
as F , say [k], and λ1 , . . . , λl ∈ R such that for any non-random G ∈ Π(K) and φ : [k] → V (G)
it holds that
k
Y

F (i1 , . . . , ir )(G(φ(i1 ), . . . , φ(ir )))

i1 ,...,ir =1

=

l
X
j=1

λj

k
Y

F j (i1 , . . . , ir )(G(φ(i1 ), . . . , φ(ir ))).

i1 ,...,ir =1

P
So therefore we can express t(F, G) = lj=1 λj t(F j , G). We return to the case when Gn
is random. The weak convergence of t(F, Gn ) is equivalent to the convergence of each of
7

its moments, its tth moment can be written by the linearity of the expectation as a linear combination of a finite number of mixed moments of the densities corresponding to
F 1 , . . . , F l ∈ Π(F ). For an arbitrary vector of non-negative integers α = (α1 , . . . , αl ), let F α
be the element of Π(F ) that is the disjoint union α1 copies of F 1 , α2 copies of F 2 , and so
on. It holds that t(F 1 , Gn )α1 . . . t(F l , Gn )αl = t(F α , Gn ), and in particular the two random
variables on the two sides are equal in expectation. Condition (2) implies that E[t(F α , Gn )]
converges for each α, therefore the mixed moments of the t(F i , Gn ) densities and the moments of t(F, Gn ) also do. This implies that t(F, Gn ) also converges in distribution for any
F ∈ Π(hF i). Now let F ′ ∈ Π(C) and ε > 0 be arbitrary, and F ∈ Π(hF i) on the same vertex
set [k] as F ′ be such that its entries are at most ε-far in L∞ from the corresponding entries
of F ′ . Then
|t(F ′ , G) − t(F, G)|
=

1
|V (G)|k

X

k
Y

F (i1 , . . . , ir )(G(φ(i1 ), . . . , φ(ir )))

φ : [k]→V (G) i1 ,...,ir =1

−
=

1
|V (G)|k

X

k
Y

F ′ (i1 , . . . , ir )(G(φ(i1 ), . . . , φ(ir )))

i1 ,...,ir =1

k
X

Y

F (j1 , . . . , jr )(G(φ(j1 ), . . . , φ(jr )))

φ : [k]→V (G) i1 ,...,ir =1 (j1 ,...,jr )<(i1 ,...,ir )

Y

F ′ (j1 , . . . , jr )(G(φ(j1 ), . . . , φ(jr )))

(j1 ,...,jr )>(i1 ,...,ir )

|F (i1 , . . . , ir )(G(φ(i1 ), . . . , φ(ir ))) − F ′ (i1 , . . . , ir )(G(φ(i1 ), . . . , φ(ir )))|

≤ k r ε max{(kF ′k∞ + ε)k

r −1

, 1}

for any G ∈ Π(K) (random or non-random), which implies (3), as ε > 0 was chosen arbitrarily.
We turn to show the equivalence of (3) and (4). Let Πk (K) ⊂ Π(K) the set of elements of
Π(K) with vertex cardinality k. The sequence (G(k, Gn ))∞
n=1 converges in distribution exactly
when for each continuous function f ∈ C(Πk (K)) on Πk (K) the expectation E[f (G(k, Gn ))]
converges as n → ∞. For each F ∈ Π(C) and α ≥ 1, the function tαinj (F, G) is continuous on
Π|V (F )| (K) and tinj (F, G) = tinj (F, G(|V (F )|, G)), so (3) follows from (4).
For showing the other direction, that (3) implies (4), let us fix k ≥ 1. We claim that
the linear function space M = ht(F, .)|F ∈ Π(C)i ⊂ C(Πk (K)) is an algebra containing
the constant function, and that it separates any two elements of Πk (K). It follows that
ht(F, .)|F ∈ Π(C)i is L∞ -dense in C(Πk (K)) by the Stone-Weierstrass theorem, which implies
by our assumptions that E[f (G(k, Gn ))] converges for any f ∈ C(Πk (K)), since we know
that E[tinj (F, G(k, Gn ))] = E[tinj (F, Gn )] whenever |V (F )| ≤ k. We will see in a moment
that tinj (F, .) ∈ M, convergence of E[tinj (F, Gn )] follows from (2.4) and the requirement that
|V (Gn )| tends to infinity in probability.
8

Now we turn to show that our claim is indeed true. For two graphs F1 , F2 ∈ Π(C) we
have t(F1 , G)t(F2 , G) = t(F1 F2 , G) for any G ∈ Πk (K), where the product F1 F2 denotes
the disjoint union of the two C-colored graphs. Also, t(F, G) = 1 for the graph F on
one node with a loop colored with the constant 1 function. Furthermore we have that
hom(F, G) = k |V (F )| t(F, G) ∈ M for |V (G)| = k, so therefore
X
Y
inj(F, G) =
(−1)|V (F )|−|P|
(|S| − 1)! hom(F/P, G) ∈ M,
S∈P

P partition of V (F )

where inj(F, G) = tinj (F, G)k(k − 1) . . . (k − |V (F )| + 1) and F/P ∈ Π|P| (C) whose edges
are colored by the product of the colors of F on the edges between the respective classes of
P.
P This equality is the consequence of the Mobius inversion formula, and that inj(F, G) =
P partition of V (F ) hom(F/P, G). For G and F defined on the node set [k] recall that
inj(F, G) =

X

k
Y

F (i1 , . . . , ir )(G(φ(i1 ), . . . , φ(ir ))).

(2.5)

φ∈Sk i1 ,...,ir =1

Now fix G1 , G2 ∈ Πk (K) and let F ∈ Πk (C) such that {F (i1 , . . . , ir )(Gj (l1 , . . . , lr ))} are
algebraically independent elements of R (such an F exists, we require a finite number of
algebraically independent reals, and can construct each entry of F by polynomial interpolation). If G1 and G2 are not isomorphic, than for any possible node-relabeling for G2 there
is at least one term in the difference inj(F, G1 ) − inj(F, G2) written out in the form of (2.5)
that does not get canceled out, so therefore inj(F, G1 ) 6= inj(F, G2 ).
We examine the remaining statements of the theorem. Clearly, Γ ∈
/ Π(K)+ , because
|V (Gn )| → ∞ in probability. The results for the case where the map in (1) and the densities
in (2) and (3) are replaced by the injective version are yielded by (2.4), the proof of the
non-random case carries through in a completely identical fashion.
We are now ready to formulate the definition of convergence in Π(K).
Definition 2.5. If (Gn )∞
n=1 is a sequence in Π(K) with |V (Gn )| → ∞ and any of the conditions above of Theorem 2.4 hold, then we say that (Gn )∞
n=1 converges.
We would like to add that, in the light of Theorem 2.4, the convergence notion is independent from the choice of the family F .
The next lemma gives information about the limit behavior of the sequences where the
vertex set cardinality is constant.
Lemma 2.6. Let (Gn )∞
n=1 be a random sequence in Πk (K), and additionally be such that for
every F ∈ Π(F ) the sequences (tinj (F, Gn ))∞
n=1 converge in distribution. Then there exists
a random H ∈ Πk (K), such that for every F ∈ Π(F ) we have t(F, Gn ) → t(F, H) and
tinj (F, Gn ) → tinj (F, H) in distribution.
9

Proof. We only sketch the proof. The distributional convergence of (Gn )∞
n=1 follows the
same way as in the proof of Theorem 2.4, the part about condition (2) implying (3) together
with the part stating that (3) implies (4). The existence of a random H satisfying the
statement of the lemma is obtained by invoking the Riesz representation theorem for positive
functionals.
Exchangeable arrays The correspondence analogous to the approach of Diaconis and
Janson in [14] will be established next between the elements of the limit space Π(K)+ that is
compact, and the extreme points of the space of random exchangeable infinite r-arrays with
entries in K. These are arrays, whose distribution is invariant under finite permutations of
the underlying index set.
Definition 2.7 (Exchangeable r-array). Let (H(e1 , . . . , er ))1≤e1 ,...,er <∞ be an infinite r-array
of random entries from a Polish space K. We call the random array separately exchangeable
if
(H(e1 , . . . , er ))1≤e1 ,...,er <∞
has the same probability distribution as
(H(ρ1 (e1 ), . . . , ρr (er )))1≤e1 ,...,er <∞
for any ρ1 , . . . , ρr ∈ SN collection of finite permutations, and jointly exchangeable (or simply
exchangeable), if the former holds only for all ρ1 = · · · = ρr ∈ SN .
For a finite set S, let h0 (S) and h(S) denote the power set and the set of nonempty subsets
of S, respectively, and h(S, m) the set of nonempty subsets of S of cardinality at most m, also
h0 (S, m) = h(S, m) ∪ {∅}. A 2r − 1-dimensional real vector xh(S) denotes (xT1 , . . . , xT2r −1 ),
where T1 , . . . , T2r −1 is a fixed ordering of the nonempty subsets of S with T2r −1 = S, for a
permutation π of the elements of S the vector xπ(h(S)) means (xπ∗ (T1 ) , . . . , xπ∗ (T2r −1 ) ), where
π ∗ is the action of π permuting the subsets of S. Similar conventions apply when x is indexed
by other set families.
It is clear that if we consider a measurable function f : [0, 1]h0 ([r]) → K, and independent
random variables uniformly distributed on [0, 1] that are associated with each of the subsets
of N of cardinality at most r, then by plugging in these random variables into f for every
e ∈ Nr in the right way suggested by a fixed natural bijection le : e → [r], the result will be
an exchangeable random r-array. The shorthand Samp(f ) denotes this law of the infinite
directed r-hypergraph model generated by f .
The next theorem, states that all exchangeable arrays with values in K arise from some
f in the former way.
Theorem 2.8. [21] Let K be a Polish space. Every K-valued exchangeable r-array (H(e))e∈Nr
has law equal to Samp(f ) for some measurable f : [0, 1]h0([r]) → K, that is, there exists a
function f , so that if (Us )s∈h0 (N,r) are independent uniform [0, 1] random variables, then
H(e) = f (U∅ , U{e1 } , U{e2 } , . . . , Ue\{er } , Ue )
for every e = (e1 , . . . , er ) ∈ Nr , where H(e) are the entries of the infinite r-array.
10

(2.6)

If H in the above theorem is invariant under permuting its coordinates, then the corresponding function f is invariant under the coordinate permutations that are induced by the
set permuting Sr -actions.
Theorem 2.8 was first proved by de Finetti [12] (in the case K = {0, 1}) and by Hewitt
and Savage [18] (in the case of general K) for r = 1, independently by Aldous [1] and Hoover
[19] for r = 2, and by Kallenberg [21] for arbitrary r ≥ 3. For equivalent formulations, proofs
and further connections to related areas see the recent survey of Austin [9].
In general, there are no symmetry assumptions on f , in the directed case H(e) might
differ from H(e′ ), even if e and e′ share a common base set. In this case these two entries
do not have the property of conditional independence over a σ-algebra given by some lower
dimensional structures, that means for instance the independence over { Uα | α ( e } for an
exchangeable r-array with law Samp(f ) given by a function f as above.
With the aid of Theorem 2.8 we will provide a form of representation of the limit space
Π(K)+ through the points of the space of random infinite exchangeable r-arrays. The correspondence will be established through a sequence of theorems analogous to the ones stated
and proved in [14, Section 2 to 5], combined with the compactification argument regarding
the limit space from [25], see also [23, Chapter 17.1] for a more accurate picture. The proofs
in our case are mostly ported in a straightforward way, if not noted otherwise we direct the
reader for the details to [14].
Let L∞ = L∞ (K) denote the set of all node labeled countably infinite K-colored r-uniform
directed hypergraphs. Set the common vertex set of the elements of L∞ to N, and define the
set of [n]-labeled K-colored r-uniform directed hypergraphs as Ln = Ln (K). Every G ∈ Ln
can be viewed as an element of L∞ simply by adding isolated vertices to G carrying the
labels N \ [n] in the uncolored case, and the arbitrary but fixed color c ∈ K to edges incident
to these vertices in the colored case, therefore we think about Ln as a subset of L∞ (and also
of Lm for every m ≥ n). Conversely, if G is a (random) element of L∞ , then by restricting
G to the vertices labeled by [n], we get G|[n] ∈ Ln . If G is a labeled or unlabeled K-colored
r-uniform directed hypergraph (random or not) with vertex set of cardinality n, then let Ĝ
stand for the random element of Ln (and also L∞ ) which we obtain by first throwing away
the labels of G (if there where any), and then apply a random labeling chosen uniformly
from all possible ones with the label set [n].
A random element of L∞ is exchangeable analogously to Theorem 2.7 if its distribution is
invariant under any permutation of the vertex set N that only moves finitely many vertices,
for example infinite hypergraphs whose edge-colors are independently identically distributed
are exchangeable. An element of L∞ can also be regarded as an infinite r-array whose
diagonal elements are colored with a special element ι that is not contained in K, therefore
the corresponding r-arrays will be K ∪ {ι}-colored.
The next theorem relates the elements of Π(K)+ to exchangeable random elements of
L∞ .

Theorem 2.9. Let (Gn )∞
n=1 be a random sequence in Π(K) with |V (Gn )| tending to infinity
in probability. Then the following are equivalent.
(1) τ + (Gn ) → Γ in distribution for a random Γ ∈ Π(K)+ \ Π(K)+ .
11

(2) Ĝn → H in distribution in L∞ (K), where H is a random element of L∞ (K).
If any of these hold true, then Et(F, Γ) = Etinj (F, H|[k]) for every F ∈ Πk (C), and also, H
is exchangeable.
Proof. If G ∈ Π(K) is deterministic and F ∈ Πk (F ) with |V (G)| ≥ k then Etinj (F, Ĝ|[k]) =
tinj (F, G), where the expectation E is taken with respect to the random (re-)labeling Ĝ of G.
For completeness we mention that for a labeled, finite G the quantity t(F, G) is understood
as t(F, G′ ) with G′ being the unlabeled version of G, also, F in t(F, G) is always regarded a
priori as labeled, however the densities of isomorphic labeled graphs in any graph coincide.
If we consider G to be random, then by the fact that 0 ≤ t(F, G) ≤ 1 (as kF k∞ ≤ 1) we
have that |EEtinj (F, Ĝ|[k]) − Etinj (F, G)| ≤ P(|V (G)| < k) for F ∈ Πk (F ).
Assume (1), then the above implies, together with P(|V (Gn )| < k) → 0 and (1), that
EEtinj (F, Ĝn |[k]) → Et(F, Γ) (see Theorem 2.4). This implies that Ĝn |[k] → Hk in distribution
for some random Hk ∈ Lk with Etinj (F, Hk ) = Et(F, Γ), see Theorem 2.6, furthermore, with
appealing to the consistency of the Hk graphs in k, there exists a random H ∈ L∞ such that
H|[k] = Hk for each k ≥ 1, so (1) yields (2).
Another consequence is that H is exchangeable: the exchangeability property is equivalent to the vertex permutation invariance of the distributions of H|[k] for each k. This
is ensured by the fact that H|[k] = Hk , and Hk is the weak limit of a vertex permutation
invariant random sequence, for each k.
For the converse direction we perform the above steps in the reversed order using
|EEt(F, Ĝn |[k] ) − Et(F, Gn ) ≤ P(|V (Gn )| < k)
again in order to establish the convergence of (Et(F, Gn ))∞
n=1 . Theorem 2.4 certifies now the
+
+
existence of the suitable random Γ ∈ Π(K) \ Π(K) , this shows that (2) implies (1).
We built up the framework in the preceding statements Theorem 2.4 and Theorem 2.9
in order to formulate the following theorem, which is the crucial ingredient to the desired
representation of limits.
Theorem 2.10. There is a one-to-one correspondence between random elements of Π(K)+ \
Π(K)+ and random exchangeable elements of L∞ . Furthermore, there is a one-to-one correspondence between elements of Π(K)+ \ Π(K)+ and extreme points of the set of random
exchangeable elements of L∞ . The relation is established via the equalities Et(F, Γ) =
Etinj (F, H|[k]) for every F ∈ Πk (C) for every k ≥ 1.
Proof. Let Γ a random element of Π(K)+ \ Π(K)+ . Then by definition of Π(K)+ there
+
is a sequence (Gn )∞
n=1 in Π(K) with |V (Gn )| → ∞ in probability such that τ (Gn ) → Γ
in distribution in Π(K)+ . By virtue of Theorem 2.9 there exists a random H ∈ L∞ so
that Ĝn → H in distribution in L∞ , and H is exchangeable. The distribution of H|[k] is
determined by the numbers Etinj (F, H|[k]), see Theorem 2.4, Theorem 2.6, and the arguments
therein, and these numbers are provided by the correspondence.
12

For the converse direction, let H be random exchangeable element of L∞ . Then let
Gn = H|[n] , we have Gn → H in distribution, and also Ĝn → H in distribution by the vertex
permutation invariance of Gn as a node labeled object. Again, we appeal to Theorem 2.9,
so τ + (Gn ) → Γ for a Γ random element of Π(K)+ \ Π(K)+ , which is determined completely
by the numbers Et(F, Γ) that are provided by the correspondence, see Theorem 2.9.
The second version of the relation between non-random Γ’s and extreme points of exchangeable elements is proven similarly, the connection is given via t(F, Γ) = Etinj (F, H|[k])
between the equivalent objects.
The characterization of the aforementioned extreme points in Theorem 2.10 was given
[14] in the uncolored graph case, we state it next for our general setting, but refrain from
giving the proof here, as it is completely identical to [14, Theorem 5.5.].
Theorem 2.11. [14] The distribution of H that is an exchangeable random element of L∞
is exactly in that case an extreme point of the set of exchangeable measures if the random
objects H|[k] and H|{k+1,... } are probabilistically independent for any k ≥ 1. In this case the
representing function f from Theorem 2.8 does not depend on the variable corresponding to
the empty set.
Graphons as limit objects Let the r-kernel space Ξ̂r0 denote the space of the bounded
measurable functions of the form W : [0, 1]h([r],r−1) → R, and the subspace Ξr0 of Ξ̂r0 the
symmetric r-kernels that are invariant under coordinate permutations π ∗ induced by some
π ∈ Sr , that is W (xh([r],r−1)) = W (xπ∗ (h([r],r−1)) ) for each π ∈ Sr . We will refer to this
invariance in the paper both for r-kernels and for measurable subsets of [0, 1]h([r]) as rsymmetry. The kernels W ∈ ΞrI take their values in some interval I, for I = [0, 1] we
call these special symmetric r-kernels r-graphons, and their set Ξr . In what follows, λ as
a measure always denotes the usual Lebesgue measure in Rd , where the dimension d is
everywhere clear from the context.
If W ∈ Ξr and F ∈ Πr , then the F -density of W is defined as
t(F, W ) =

Z

[0,1]h([k],r−1)

Y

e∈E(F )

W (xh(e,r−1) )

Y

(1 − W (xh(e,r−1) ))dλ(xh([k],r−1)).

(2.7)

e∈E(F
/
)

Let K be a compact Polish space, and W : [0, 1]h([r]) → K be a measurable function, we
will refer to such an object as a (K, r)-digraphon, their set is denoted by Ξ̃r (K). Note that
there are no symmetry assumptions in this general case, if additionally W is r-symmetric,
then we speak about (K, r)-graphons, their space is Ξr (K). For K = {0, 1} the set P(K) can
be identified with the [0, 1] interval encoding the success probabilities of Bernoulli trials to
r
get the common r-graphon form as a function W : [0, 1]2 −2 → [0, 1] employed in [15].

13

The density of a K-colored graph F ∈ Π̃k (C(K)) in the (K, r)-digraphon W is defined
analogously to (2.3) and (2.7) as
Z
Y
F (e)(W (xh(e,r)))dλ(xh([k],r)).
(2.8)
t(F, W ) =
[0,1]h([k],r)

e∈[k]r

For k ≥ 1 and an undirected W ∈ Ξr (K) the random (K, r)-graph G(k, W ) is defined
on the vertex set [k] by selecting a uniform random point (XS )S∈h([k],r) ∈ [0, 1]h([k],r) that

enables the assignment of the color W (Xh(e) ) to each edge e ∈ [k]
. For a directed W the
r
sample point is as above, the color of the directed edge e ∈ [k]r is W (Xh(e) ), but in this case
the ordering of the power set of the base set e of e matters in contrast to the undirected
situation and is given by e, as W is not necessarily r-symmetric.
Additionally we define the averaged sampled r-graph for
 K ⊂ R denoted by H(k, W ),
[k]
it has vertex set [k], and the weight of the edge e ∈ r is the conditional expectation
E[W (Xh(e) ) | Xh(e,1) ], and therefore the random r-graph is measurable with respect to Xh([k],1).
We will use the compact notation Xi for X{i} for the elements of the sample indexed by
singleton sets.
We define the random exchangeable r-array HW in L∞ as the element that has law
Samp(W ) for the (K, r)-digraphon W , as in Theorem 2.8. Furthermore, we define ΓW ∈
Π(K)+ \ Π(K)+ to be the element associated to HW through Theorem 2.9.
Now we are able to formulate the representation theorem for K-colored r-uniform directed
hypergraph limits using the representation of exchangeable arrays, see (Theorem 2.8). It is
an immediate consequence of Theorem 2.9 and Theorem 2.10 above.
Theorem 2.12. Let (Gn )∞
n=1 be a sequence in Π(K) with |V (Gn )| → ∞ such that for every
F ∈ Π(F ) the sequence t(F, Gn ) converges. Then there exists a function W : [0, 1]h([r]) → K
(that is W ∈ Ξr (K)) such that t(F, Gn ) → t(F, ΓW ) for every F ∈ Π(F ). In the directed
case when the sequence is in Π̃(K), then the corresponding limit object W is in Ξ̃r (K).
We mention that t(F, ΓW ) = t(F, W ) for every F ∈ Π(C(K)) and W ∈ Ξr (K). Alternatively we can also use the form W : [0, 1]h([r],r−1) → P(K) for (K, r)-graphons and digraphons
in Ξr (K) whose values are probability measures, this representation was applied in [25].
In previous works, for example in [14], the limit object of a sequence of simple directed
graphs without
was represented by a 4-tuple of 2-graphons (W (0,0) , W (1,0) , W (0,1) , W (1,1) )
Ploops (i,j)
that satisfies i,j W (x, y) = 1 and W (1,0) (x, y) = W (0,1) (y, x) for each (x, y) ∈ [0, 1]2 . A
generalization of this representation can be given in our case of the Π(K) limits the following
way. We only present here the case when K is a continuous space, the easier finite case can
be dealt with analogously.
We have to fix a Borel probability measure µ on K, we set this to be the uniform distribution if K ⊂ Rd is a domain or K is finite. The limit space consists of collections of
(R, r)-kernels W =R (W u )u∈U , where U is the set of all functions u : Sr → K. Additionally,
∗
W has to satisfy U W u (x)dµ⊗Sr (u) = 1 and 0 ≤ W π (u) (x) = W u (xπ∗ (h([r],r−1)) ) for each
π ∈ Sr and x ∈ [0, 1]h([r],r−1). As before, the action π ∗ of π on [0, 1]h([r],r−1) is the induced
14

coordinate permutation by π, with the unit cubes coordinates indexed by non-trivial subsets
of [r]. Without going into further details we state the connection between the limit form
spelled out above and that in Theorem 2.12. It holds
Z
W u ((xh([r],r−1))dµ⊗Sr (u) = P[(W (xπ∗ (h([r],r−1)) , Y )π∈Sr ) ∈ U]
U

for every measurable U ⊂ U and x ∈ [0, 1]h([r],r−1), where Y is uniform on [0, 1], and the W
on the right-hand side is a (K, r)-digraphon, whereas on the left we have the corresponding
representation as a (possibly infinite) collection of (R, r)-kernels.
In several applications it is more convenient to use a naive form for the limit representation, from which the limit element in question is not decisively retrievable. The naive limit
space consists of naive (K, r)-graphons W : [0, 1]r → P(K), where now the arguments of W
are indexed with elements of [r]. From a proper r-graphon W : [0, 1]h([r]) → K we get its naive
counterpart by averaging, the K-valued random variable E[W (xh([r],1) , Uh([r],r−1)\h([r],1), Y )|Y ]
has distribution W (x1 , . . . , xr ), where (US )S∈h([r],r−1)\h([r],1) and Y are i.i.d. uniform on [0, 1].
On a further note we introduce averaged naive (K, r)-graphons for the case, when K ⊂
R, these are of the form W̃ : [0, 1]r → R and are given by complete averaging, that is
E[W (x1 , . . . , xr , Uh([r])\h([r],1), Y )] = W̃ (x1 , . . . , xr ), where (US )S∈h([r])\h([r],1) are i.i.d. uniform
on [0, 1]. A naive r-kernel is a real-valued, bounded function on [0, 1]r , or equivalently on
[0, 1]h([r],1).
We can associate to each G ∈ Πrn (K) an element WG ∈ Ξr (K ∪ {ι}) by subdividing
the unit r-cube [0, 1]h([r],1) into nr small cubes the natural way and defining the function
W ′ : [0, 1]h([r],1) → K that takes the value G(i1 , . . . , ir ) on [ i1n−1 , in1 ] ×· · · ×[ irn−1 , inr ] for distinct
i1 , . . . , ir , and the value ι on the remaining diagonal cubes, note that these functions are naive
(K, r)-graphons. Then we set WG (xh([r],r−1) ) = W ′ (ph([r],1) (xh([r],r−1))), where ph([r],1) is the
projection to the suitable coordinates. The special color ι here stands for the absence of
colors has to be employed in this setting as rectangles on the diagonal correspond to loop
edges. The corresponding r-graphon W ι is {0, 1}-valued. The sampled random r-graphs
G(k, WG ) and H(k, WG ) from the naive r-graphons are defined analogously to the general
case. If K ⊂ R, then note that H(k, WG ) = G(k, WG ) for every G, because the colors of G
are all point measures.
Note that t(F, G) = t(F, WG ), and

k
|tinj (F, G) − t(F, WG )| ≤

2

n−

k
2



(2.9)

for each F ∈ Πrk , hence the representation as naive graphons is compatible in the sense that
limn→∞ tinj (F, Gn ) = limn→∞ t(F, WGn ) for any sequence (Gn )∞
n=1 with |V (Gn )| tending to
infinity. This implies that dtv (G(k, Gn ), G(k, WGn )) → 0 as n tends to infinity.
We remark that naive and averaged naive versions in the directed case are defined analogously.

15

2.2

Representation of rCSP formulas as hypergraphs, and their
convergence

In this subsection we elaborate on how homomorphism and sampling is meant in the CSP
context, and formulate a representation the limit space in that context. Recall Theorem 2.1
for the way how we perceive rCSP formulas.
Let F be an rCSP formula on the variable set {x1 , . . . , xn } over an arbitrary domain K,
and let F [xi1 , . . . , xik ] be the induced subformula of F on the variable set {xi1 , . . . , xik }. Let
G(k, F ) denote the random induced subformula on k uniformly chosen variables from the
elements of V (F ).
It is clear using the terminology of Theorem 2.7 that the relation ω = (f ; xe ) ∈ F [xi1 , . . . , xik ]
is equivalent to the relation
φ(ω) = (fφ , xφ(e) ) ∈ F [xi1 , . . . , xik ]

(2.10)

for permutations φ ∈ Sr , where fφ (l1 , . . . , lr ) = f (lφ(1) , . . . , lφ(r) ) and φ(e) = (eφ(1) , . . . , eφ(r) ).
This emergence of symmetry will inherently be reflected in the limit space, we will demonstrate this shortly.
Special limits Let K = [q]. As we mentioned above, in general it is likely not to be fruitful to consider formula sequences as sequences of C(K, r)-colored r-graphs obeying certain
symmetries due to constraint splitting. However, in the special case when each r-set of variables carries exactly one constraint we can derive a meaningful representation, MAX-CUT
is an example. A direct consequence of Theorem 2.12 is the following.
Corollary 2.13. Let r ≥ 1, and K be a finite set, further, let K ⊂ C(K, r), so that K is
permutation invariant. Let (Fn )∞
n=1 be a sequence of rCSP formulas with |V (Fn )| tending
to infinity, and each r-set of variables in each of the formulas carries exactly one constraint
of type K. If for every formula H obeying the same conditions the sequences (t(H, Fn ))∞
n=1
converge as (K, r)-graphs, then there exists a (K, r)-digraphon W : [0, 1]h([r]) → K such that
t(H, Fn ) → t(H, W ) as n tends to infinity for every H as above.
Additionally, W satisfies for each x ∈ [0, 1]h([r]) and π ∈ Sr that W (xπ(h([r])) ) = π̂(W (xh([r]) )),
where π̂ is the action of π on constraint types in C(K, r) that permutes the rows and columns
of the evaluation table according to π, that is (π̂(f ))(l1 , . . . , lr ) = f (lπ(1) , . . . , lπ(r) ).
General limits via evaluation In the general case of rCSP formulas we regard them as
their evaluation representation eval.
For |K| = q we identify the set of rCSP formulas with the set of arrays whose entries are
the sums of the evaluation tables of the constraints on r-tuples, that is F with V (F ) = [n]
r
corresponds to a map eval(F ) : [n] × · · · × [n] → {0, 1, . . . , d}([q] ) that obeys the symmetry
condition given after (2.2). This will be the way throughout the paper we look at these
objects from here on. It seems that storing the whole structure of an rCSP formula does
not provide any further insight, in fact splitting up constraints would produce non-identical
formulas in a complete structure representation, which does not seem sensible.
16

r

We denote the set {0, 1, . . . , d}([q] ) by L for simplicity, which one could also interpret as
the set of multisets whose base set is [q]r and whose elements have multiplicity at most d.
This perspective allows us to treat rCSPs as directed r-uniform hypergraphs whose edges
are colored by the aforementioned elements of L, and leads to a representation of rCSP
limits that is derived from the general representation of the limit set of Π(L). We will
show in a moment that the definition of convergence in the previous subsection given by
densities of functional-colored graphs is basically identical to the convergence via densities
of sub-multi-hypergraphs in the current case.
The definition of convergence for a general sequence of rCSP formulas, or equivalently of
elements of Π(L), was given in Theorem 2.5. We describe here the special case for parallel
multicolored graphs, see also [25].
Consider the evaluation representation of the rCSP formulas now as r-graphs whose
oriented edges are parallel multicolored by [q]r . The map ψ : eval(H) → eval(F ) is a homomorphism between two rCSP formulas H and F if it maps edges to edges of the same color
from the color set [q]r and is consistent when restricted to be a mapping between vertex
sets, ψ ′ : V (H) → V (F ), for simple graphs instead of CSP formulas this is the multigraph
homomorphism notion.
Let H be an rCSP formula, and let H̃ be the corresponding element in C(L) on the same
vertex set such that if the color on the fixed edge e of H is the q-sized r-array (H z (e))z∈[q]r
Q H z (e)
xz
. More
with the entries being non-negative integers, then the color of H̃ at e is
z∈[q]r

precisely, for an element A ∈ L the value is given by
Y
z
A(z)H (e) .
[H̃(e)](A) =
z∈[q]r

The linear space generated by the set


 Y

dz
L̃ =
xz | 0 ≤ dz1 ,...,zr ≤ d


r
z∈[q]

forms an L∞ -dense subset in C(L), therefore Theorem 2.4 applies, and for a sequence (Gn )∞
n=1
requiring the convergence of t(F, eval(Gn )) for all F = H̃ with H ∈ Π(L) provides one of
the equivalent formulations of the convergence of rCSP formulas in the subformula density
sense with respect to the evaluations.
The limit object will be given by Theorem 2.12 as the space of measurable functions
W : [0, 1]h([r]) → L, where, as in the general case, the coordinates of the domain of W are
indexed by the non-empty subsets of [r]. In our case, not every possible W having this form
will serve as a limit of some sequence, the above mentioned symmetry in (2.10) of the finite
objects is inherited in the limit.
We state now the general evaluation rCSP version of Theorem 2.12.
Corollary 2.14. Let (Fn )∞
n=1 be a sequence of rCSP formulas that evaluate to at most
d on all r-tuples with |V (Fn )| → ∞ such that for every finite rCSP formula H obeying
17

the same upper bound condition the sequence (t(H̃, eval(Fn )))∞
n=1 converges. Then there
exists an (L, r)-graphon W : [0, 1]h([r]) → L such that t(H̃, eval(Fn )) → t(H̃, W ) for every H.
Additionally, W satisfies for each x ∈ [0, 1]h([r]) and π ∈ Sr that W (xπ(h([r])) ) = π̂(W (xh([r]))),
where π̂ is as in Theorem 2.13 when elements of L are considered as maps from [q]r to
non-negative integers.
Exchangeable partition-indexed processes We conclude the subsection with a remark
that is motivated by the array representation of rCSPs. The next form presented seems to
be the least redundant in some aspect, since no additional symmetry conditions have to be
fulfilled by the limit objects.
The most natural exchangeable infinite random object fitting the one-to-one correspondence of Theorem 2.9 with rCSP limits is the following process, that preserves every piece
of information contained in the evaluation representation.
Definition
2.15. Let Nqr = { P = (P1 , . . . , Pq ) | the sets Pi ⊂ N are pairwise disjoint and
Pq
i=1 |Pi | = r } be the set of directed q-partitions of r-subsets of N. We call the random
process (XP )P∈Nqr that takes values in some compact Polish space K a partition indexed
process. The process (XP )P∈Nqr has the exchangeability property if its distribution is invariant
d

under the action induced by finite permutations of N, i.e., (XP )P∈Nqr = (Xρ∗ (P) )P∈Nqr for any
ρ ∈ Sym0 (N).
Unfortunately, the existence of a representation theorem for partition-indexed exchangeable processes analogous to Theorem 2.8 that offers additional insight over the directed
colored r-array version is not established, and there is little hope in this direction. The
reason for this is again the fact that there is no standard way of separating the generating
process of the elements XP and XP ′ non-trivially in the case when P and P ′ have the same
underlying base set of cardinality r but are different as partitions into two non-trivial random stages with the first being identical for the two variables and the second stage being
conditionally independent over the outcome of the first stage.

3

Graph and graphon parameter testability

First we will invoke the method of sampling from K-colored r-graphs and r-graphons, as
well as inspect the metrics that will occur later.
Let (US )S∈h([k],r) be an independent uniform sample from [0, 1]. Then for an r-graph
G, respectively an r-graphon W , the random r-graphs G(k, G) and G(k, W ) have vertex
set [k], and edge weights WG ((Upe (S) )S∈h(ê,r) ), respectively W ((Upe (S) )S∈h(ê,r) ). Keep in mind,
that G(k, G) 6= G(k, WG ), the first term corresponds to sampling without, the second with
2
replacement, but it is true that P(G(k, G) 6= G(k, WG )) ≤ |V r(G)| .
Norms and distances We also mention the definitions of the norms and distances that
will play a important role in what follows. In the next definition each object is real-valued.
18

Definition 3.1. The cut norm of an n × · · · × n r-array A is
kAk =

1
nr

max

S1 ,...,Sr ⊂[n]

and the 1-norm is
kAk1 =

1
nr

n
X

i1 ,...,ir =1

|A(S1 , . . . , Sr )| ,
|A(i1 , . . . , ir )|.

The cut distance of two labeled r-graphs or r-arrays F and G on the same vertex set [n] is
d (F, G) = kF − Gk ,
where F (S1 , . . . , Sr ) =

P

ij ∈Sj

F (i1 , . . . , ir ). The edit distance of the same pair is
d1 (F, G) = kF − Gk1 .

The continuous counterparts are described as follows.
Definition 3.2. The cut norm of a naive r-graphon W is
kW k =

max

S1 ,...,Sr ⊂[0,1]

Z

W (x)dx ,

S1 ×···×Sr

the cut distance of two naive r-graphons W and U is
δ (W, U) = inf kW φ − U ψ k ,
φ,ψ

where the infimum runs over all measure-preserving permutations of [0, 1], and the graphon
W φ is defined as W φ (x1 , . . . , xr ) = W (φ(x1 ), . . . , φ(xr )). The cut distance for arbitrary
unlabeled r-graphs or r-arrays F and G is
δ (F, G) = δ (WF , WG ).
We remark that the above definition of the cut norm and distance is not satisfactory from
one important aspect for r ≥ 3: Not all sub-r-graph densities are continuous functions in the
topology induced by this norm even in the most simple case, when K = {0, 1}. Examples of
subgraphs whose densities behave well with respect to the above norms are linear hypegraphs,
that have the property that any two distinct edges intersect at most in one node.
Originally, in [10], testability of (K, r)-graph parameters (which are real functions invariant under r-graph-isomorphisms) was defined as follows.
Definition 3.3. A (K, r)-graph parameter f is testable, if for every ε > 0 there exists a
k(ε) ∈ N such that for every k ≥ k(ε) and simple (K, r)-graph G on at least k vertices
P(|f (G) − f (G(k, G))| > ε) < ε.
A (K, r)-graphon parameter f is a functional on the space of r-graphons that is invariant
under the action induced by measure preserving maps from [0, 1] to [0, 1], that is, f (W ) =
f (W φ ). Their testability is defined analogously to Definition 3.3.
19

Testing parameters A characterization of the testability of a graph parameter in terms
of graph limits was developed in [10] for K = {0, 1} in the undirected case, we will focus
in the next paragraphs on this most simple setting and give an overview on previous work.
Recall Theorem 3.3.
Theorem 3.4. [10] Let f be a simple graph parameter, then the following statements are
equivalent.
(i) The parameter f is testable.
(ii) For every ε > 0 there exists a k(ε) ∈ N such that for every k ≥ k(ε) and simple graph
G on at least k vertices
|f (G) − Ef (G(k, G))| < ε.
(iii) For every convergent sequence (Gn )∞
n=1 of simple graphs with |V (Gn )| → ∞ the numer∞
ical sequence (f (Gn ))n=1 also converges.
(iv) For every ε > 0 there exist a ε′ > 0 and a n0 ∈ N such that for every pair G1
and G2 of simple graphs |V (G1 )|, |V (G2 )| ≥ n0 and δ (G1 , G2 ) < ε′ together imply
|f (G1 ) − f (G2 )| < ε.
(v) There exists a δ -continuous functional f ′ on the space of graphons, so that f (Gn ) →
f ′ (W ) whenever Gn → W .
A closely related notion to parameter testing is property testing. A simple graph property
P is characterized by the subset of the set of simple graphs containing the graphs which have
the property, in what follows P will be identified with this subset.
Definition 3.5. [26] P is testable, if there exists another graph property P ′ , such that
(a) P(G(k, G) ∈ P ′ ) ≥

2
3

for every k ≥ 1 and G ∈ P, and

(b) for every ε > 0 there is a k(ε) such that for every k ≥ k(ε) and G with d1 (G, P) ≥ ε we
have that P(G(k, G) ∈ P ′ ) ≤ 13 .
Note that 31 and 32 in the definition can be replaced by arbitrary constants 0 < a < b < 1,
this change may alter the corresponding certificate P ′ , but not the characteristic of testability.
The link below between the two notions is a simple consequence of the definitions. These
concepts may be extended to the infinitary space of graphons, where a similar notion of
sampling is available.
Lemma 3.6. [26] P is a testable graph property if and only if d1 (., P) is a testable graph
parameter.
We provide some remarks yielded by Theorem 3.4.
Remark 3.7. In the case r = 2, the testability of a graphon parameter is equivalent to
continuity in the δ distance.
20

Remark 3.8. The intuitive reason for the absence of an analogous, easily applicable characterization of testability for higher rank uniform hypergraphs as in Theorem 3.4 is that no
natural notion of a suitable distance is available at the moment. The construction of such a
metric would require to establish a standard method to compare a large hypergraph Hn to
its random induced subgraph on a uniform sample.
The δ metric for graphs is convenient because of its concise formulation and it induces a
compact limit space, the main characteristic that is exploited that the total variation distance
of probability measures of induced subgraphs of fixed size is continuous in this distance, any
other δvar with this property would fit into the above framework.

3.1

Examples of testable properties and parameters

We introduce now a notion of efficient parameter testability. Theorem 3.3 of testability does
not ask for a specific upper bound on k(ε) in terms of ε, but in applications the order of
magnitude of this function may be an important issue once its existence has been verified.
Therefore we introduce a more restrictive class of graph parameters, we refer to them as
being efficiently testable.
Definition 3.9. An r-graph parameter f is called β-testable for a family of measurable
functions β = { βi | βi : R+ → R+ , i ∈ I }, if there exists an i ∈ I such that for every ε > 0
and r-graph G we have
P(|f (G) − f (G(βi (ε), G))| > ε) < ε.
With slight abuse of notation we will also use the notion of β-testability for a family
containing only a single function β. The term efficient testability will serve as shorthand
for β-testability for some (family) of functions β(ε) that are polynomial in 1ε . One could
rephrase this in the light of Theorem 3.9 by saying that a testable parameter f is efficiently
testable if its sample complexity is polynomial in 1/ε.
We will often deal with statistics that are required to be highly concentrated around their
mean, this might be important for us even if their mean is not known to us in advance. A
quite universal tool for this purpose is a Chernoff-type large deviation result, the AzumaHoeffding-inequality for martingales with bounded jumps. Mostly, we require the formulation
given below, see e.g. [3] for a standard proof and a wide range of applications. We will also
apply a more elaborate version of this concentration inequality below.
Lemma 3.10 (Azuma-Hoeffding-inequality). Let (Mk )nk=0 be a super-martingale with the
natural filtration such that with probability 1 for every k ∈ [n] we have |Mk − Mk−1 | ≤ ck .
Then for every ε > 0 we have


ε2
P(|Mn − M0 | ≥ ε) ≤ 2 exp − Pn 2 .
2 k=1 ck

We will list some examples of graph parameters, for which there is information available
about their sample complexity implicitly or explicitly in the literature.
21

Example 3.11. One of the most basic testable simple graph parameters are subgraph densities fF (G) = t(F, G), where F is a simple graph. The next result was formulated as Theorem
2.5 in [24], see also for hypergraphs Theorem 11 in [15].
Lemma 3.12. [24, 15] Let ε > 0 q, r ≥ 1 be arbitrary. For any q-colored r-graphs F and
G, and integer k ≥ |V (F )| we have


ε2 k
,
P(|tinj (F, G) − tinj (F, G(k, G))| > ε) < 2 exp −
2|V (F )|2
and


P(|t(F, G) − t(F, G(k, G))| > ε) < 2 exp −

ε2 k
18|V (F )|2

For any q-colored r-graphon W we have



ε2 k
P(|t(F, W ) − tinj (F, G(k, W ))| > ε) < 2 exp −
2|V (F )|2


and


P(|t(F, W ) − t(F, G(k, W ))| > ε) < 2 exp −

ε2 k
8|V (F )|2

.





(3.1)

,

.

This implies that for any F that the parameter fF is O(log( 1ε )ε−2 )-testable. In the
case of (K, r)-graphs for arbitrary r the same as Theorem 3.12 holds, this can be shown by
a straightforward application of the Azuma-Hoeffding inequality, Theorem 3.10, as in the
original proofs.
Example 3.13. For r = 2, q, n ∈ N, J ∈ Rq×q , h ∈ Rq , and G ∈ Π2n we consider the energy
Eφ (G, J, h) =

1 X
1 X
−1
−1
hi |φ−1 (i)|,
J
e
(φ
(i),
φ
(j))
+
ij
G
n2 1≤i,j≤q
n 1≤i≤q

(3.2)

of a partition φ : V (G) → [q], and
ˆ
E(G,
J, h) =

max

φ : V (G)→[q]

Eφ (G, J, h),

(3.3)

that is the ground state energy of the graph G (cf. [11]) with respect to J and h, where
eG (S, T ) denotes the number of edges going form S to T in G. These graph functions
originate from statistical physics, for the rigorous mathematical treatment of the topic see
e.g. Sinai’s book [29]. The energy expression whose maximum is sought is also referred to
as a Hamiltonian. In the literature this notion is also often to be found with negative sign
or different normalization, more on this below.
This graph parameter can be expressed in the terminology applied for MAX-2CSP. Let
the corresponding 2CSP formula to the pair (G,J) be F with domain K = [q]. The formula F
is comprised of the constraints (g0 ; x(i,j) ) for every edge (i, j) of G, where g0 is the constraint
22

type whose evaluation table is J, and additionally it contains n copies of (g1 ; xi ) for every
vertex i of G, where g1 is the constraint type in one variable with evaluation vector h. Then
the optimal value of the objective function of the MAX-2CSP problem of the instance F is
ˆ
equal to E(G,
J, h). Note that this correspondence is consistent with the sampling procedure,
that is, to the pair (G(k, G),J) corresponds the 2CSP formula G(k, F ). Therefore Ê(., J, h)
has sample complexity O( ε14 )(see [4],[27]).
These energies are directly connected to the number hom(G, H) of admissible vertex
colorings of G by the colors V (H) for a certain small weighted graph H. This was pointed
out in [11], (2.16), namely


1
1
,
(3.4)
ln hom(G, H) = Ê(G, J) + O
|V (G)|2
|V (G)|
where the edge weights of H are βij (H) = exp(Jij ). The former line of thought of transforming ground state energies into MAX-2CSPs is also valid in the case of r-graphs and rCSPs
for arbitrary r.
The results on the sample complexity of MAX-rCSP for q = 2 can be extended beyond
the case of simple hypergraphs, higher dimensional Hamiltonians are also expressible as
rCSP formulas. The generalization for arbitrary q and to r-graphons will follow in the next
section. Additionally we note, that an analogous statement to (3.4) on testability of coloring
numbers does not follow immediately for r ≥ 3.
On the other hand, with the notion of the ground state energy available, we may rewrite
the MAX-2CSP in a compact form as an energy problem. We will execute this task right
away for limit objects. First, we introduce the ground state energy of a 2-kernel with respect
to an interaction matrix J. The collection φ = (φ1 , . . . , φq ) is a fractional q-partition of [0, 1]
with the components
being measurable non-negative functions on [0, 1], if for every x ∈ [0, 1]
P
it holds that qi=1 φi (x) = 1.
Definition 3.14. Let q ≥ 1, J ∈ Rq×q . Then the ground state energy of the 2-kernel W
with respect to J is
Z
X
Jz
E(W, J) = max
φz1 (x)φz2 (y)W (x, y)dxdy,
φ

z∈[q]2

[0,1]2

where φ runs over all fractional q-partitions of [0, 1].
2

Let K = [q], L = {0, 1, . . . , d}[q] and (Fn )∞
n=1 be a convergent sequence of 2CSP formulas.
Consider the corresponding sequence of graphs eval(Fn ) = (F̃nz )z∈[q]2 for each n, and let W =
(W z )z∈[q]2 be the respective limit. Let f be the (L, 2)-graph parameter so that f (eval(F )) is
equal to the density of the MAX-2CSP value for the instance F . Then it is not hard to see
that f can be extended to the limit space the following way
Z
q
X
f (W ) = max
φi (x)φj (y)W (i,j)(x, y)dxdy,
φ

i,j=1
[0,1]2

23

where φ runs over all fractional q-partitions of [0, 1]. The formula is a special case of the
layered ground state energy with the interaction matrices defined by J i,j (k, l) = Ii (k)Ij (l)
that is defined below.
Example 3.15. The efficiency of testing a graph parameter can be investigated in terms of
some additional continuity condition in the δ metric. Direct consequence of results from
[10] will be presented in the next lemma.
Lemma 3.16. Let f be a simple graph parameter that is α-Hölder-continuous in the δ
metric in the following sense: There exists a C > 0 such that for every ε > 0 there exists
n0 (ε) so that if for the simple graphs G1 , G2 it holds that |V (G1 )|, |V (G2 )| ≥ n0 (ε) and

δ (G1 , G2 ) ≤ ε, then |f (G1 ) − f (G2 )| ≤ Cδα (G1 , G2 ). Then f is max{2
testable.

O

1
ε2/α

, n0 (ε)}-

Proof. To see this, let us fix ε > 0. Then for an arbitrary simple graph G with |V (G)| ≥ n0 (ε)
and k ≥ n0 (ε) we have
!α
10
α
|f (G) − f (G(k, G))| ≤ C [δ (G, G(k, G))] < C p
,
(3.5)
log2 k
2

k
with probability at least 1−exp(− 2 log
). The last probability bound in (3.5) is the statement
2k
α

10
, the substitution
of Theorem 2.9 of [10]. We may rewrite (3.5) by setting ε = C √
log2 k

implies that f is 2O(

ε−2/α

) -testable, whenever n (ε) ≤ 2
0

O(ε−2/α )

.

This latter approach is hard to generalize in a meaningful way to r-graphs for r ≥ 3
because of the absence of a suitable metric, see the discussion above. The converse direction,
namely formulating a qualitative statement about the continuity of f with respect to δ
obtained from the information about the sample complexity is also a worthwhile problem.

4

Testability of the ground state energy

Assume that K is a compact Polish space, and r is a positive integer. First we provide the
basic definition of the energy of a (K, r)-graphon W : [0, 1]h([r]) → K with respect to some
q ≥ 1, an r-array J ∈ C(K)q×···×q , and a fractional partition φ = (φ1 , . . . , φq ). With slight
abuse of notation, the graphons in the upcoming parts of the section assume both the Kvalued and the probability measure valued form, it will be clear from the context which one
of them is meant.
Recall ?? of the energies of naive r-kernels, the version for true (K, r)-graphons is
Eφ (W, J) =

q
X

Z

Jz1 ,...,zr (W (xh([r])))

z1 ,...,zr =1
[0,1]h([r])

r
Y
j=1

24

φzj (x{j} )dλ(xh([r]) ).

(4.1)

The value of the above integral can be determined by first integrating over the coordinates
corresponding to subsets of [r] with at least two elements, and then over the remaining ones.
The interior partial integral is then not dependent on φ, so it can be calculated in advance
in the case when we want to optimize over all choices of fractional partitions. Therefore
focusing attention on the naive kernel version does not lead to any loss of generality in terms
of testing, see below.
When dealing with a so-called integer partition φ = (IT1 , . . . , ITq ), one is able to rewrite
the former expression (4.1) as
Z
q
X
Jz1 ,...,zr (W (xh([r])))dλ(xh([r] ),
Eφ (W, J) =
z1 ,...,zr =1 −1
ph([r],1) (Tz1 ×···×Tzr )

where pD stands for the projection of [0, 1]h([r]) to the coordinates contained in the set D.
The energy of a (K, r)-graph G on k vertices with respect to the J ∈ C(K)q×···×q for
the fractional q-partition xn = (xn,1 , . . . , xn,q ) for n = 1, . . . , k (i. e., xn,m ∈ [0, 1] and
P
m xn,m = 1) is defined as
1
Ex (G, J) = r
k

q
X

k
X

Jz1 ,...,zr (G(n1 , . . . , nr ))

z1 ,...,zr =1 n1 ,...,nr =1

r
Y

xnj ,zj .

(4.2)

j=1

In the case when K = {0, 1} and Jz1 ,...,zr (x) = az1 ,...,zr I1 (x) is a constant multiple of
the indicator function of 1 we retrieve the original GSE notion in Theorem 3.13 and Theorem 3.14.
Remark 4.1. Ground state energies and subgraph densities are Lipschitz continuous graph
parameters in the sense of Theorem 3.16 ([10],[11]), but that result implies much weaker
upper bounds on the sample complexity, than the best ones√known to date. This is due to
the fact, that δ (G, G(k, G)) decreases with magnitude 1/ log k in k, which is the result
of the difficulty of finding a near optimal overlay between two graphons through a measure
preserving permutation of [0, 1] in order to calculate their δ distance. On the other hand,
if the sample size k(ε) is exponentially large in 1/ε, then the distance δ (G, G(k, G)) is
small with high probability, therefore all Hölder-continuous graph parameters at G can be
estimated simultaneously with high success probability by looking at the values at G(k, G)).
Next we introduce the layered version of the ground state energy. This is a generalized
optimization problem where we wish to obtain the optimal value corresponding to fractional
partitions of the sums of energies over a finite layer set.
Definition 4.2. Let E be a finite layer set, K be a compact set, and W = (W e )e∈E be a tuple
of (K, r)-graphons. Let q be a fixed positive integer and let J = (J e )e∈E with J e ∈ C(K)q×···×q
for every e ∈ E. For a φ = (φ1 , . . . , φq ) fractional q-partition of [0, 1] let
X
Eφ (W e , J e )
Eφ (W, J) =
e∈E

25

and let
E(W, J) = max Eφ (W, J),
φ

denote the layered ground state energy, where the maximum runs over all fractional qpartitions of [0, 1].
We define for G = (Ge )e∈E the energy Ex (G, J) analogously as the energy sum over E, see
(4.2) above, and Ê(G, J) = maxx Ex (G, J) where the maximum runs over integer q-partitions
(xn,m ∈ {0, 1} ), respectively E(G, J) = maxx Ex (G, J), where the maximum is taken over all
fractional q-partitions x.
Now we will rewrite the unweighted boolean limit MAX-rCSP (recall Theorem 2.2) as a
layered ground state energy problem. Let E = {0, 1}r , K = {0, 1, . . . , 2r }, W = (W z )z∈{0,1}r
with W z being (K, r)-graphons, and let
α(W ) = max
φ

X

z∈{0,1}r

Z

[0,1]h([r])

r
Y
j=1

φ(x{j} )zj (1 − φ(x{j} ))1−zj W z (x)dλ(x),

where the maximum is taken over all measurable functions φ : [0, 1] → [0, 1]. If eval(F ) =
(F z )z∈{0,1}r is a (KE , r)-graph corresponding to a boolean rCSP formula F with k variables,
then the finite integer version of α is given by
α̂(eval(F )) = max
x

1
kr

X

z∈{0,1}r

k
X

n1 ,...,nr =1

F z (n1 , . . . , nr )

r
Y

xnj ,zj ,

j=1

where the maximum runs over integer 2-partitions of [k]. It is clear that α̂(eval(F )) is equal
to the density of the optimum of the MAX-rCSP problem of F .
We return to the general setting and summarize the involved parameters in the layered
ground state energy problem. These are the dimension r, the layer set E, the number of
states q, the color set K, the finite or limit case. Our main theorem on the paper will be a
generalization of the following theorem on sample complexity of rCSPs with respect to these
factors.
The main result of [4] was the following.
Theorem 4.3. [4] Let F be an unweighted boolean rCSP formula. Then for any ε > 0 and
δ > 0 we have that for k ∈ O(ε−4 log( 1ε )) it holds that
P (|α̂(eval(F )) − α̂(G(k, eval(F )))| > ε) < δ.
The upper bound on k in the above result was subsequently improved by Mathieu and
Schudy [27] to k ∈ O(ε−4 ). We will see in what follows that also the infinitary version of the
above statement is true. It will be stated in terms of layered ground state energies of edge
colored hypergraphs, and will settle the issue regarding the efficiency of testability of the
mentioned parameters in the greatest generality with respect to the previously highlighted
26

aspects. However, what the exact order of the magnitude of the sample complexity of the
MAX-rCSP and the GSE problem is remains an open question.
In order to simplify the analysis we introduce the canonical form of the problem, that
denote layered ground state energies of [q]r -tuples of ([−d, d], r)-graphons with the special
interaction r-arrays Jˆz for each z ∈ [q]r , that have the identity function f (x) = x as the
(z1 , . . . , zr ) entry and the constant 0 function for the other entries. In most of what follows
we will drop the dependence on J in the energy function when it is clear that we mean
ˆ and will employ the notation Ex (G), E(G), E(G),
ˆ
the aforementioned canonical J,
Eφ (W ),
and E(W ) (dependence on q is hidden in the notation), where G and W are [q]r -tuples of
([−d, d], r)-graphs and graphons, respectively. We are ready to state the main result of the
paper.
Theorem 4.4. Let r ≥ 1, q ≥ 1, and ε > 0. Then for any [q]r -tuple of ([−kW k∞ , kW k∞ ], r)r+7 r
graphons W = (W z )z∈[q]r and k ≥ Θ4 log(Θ)q r with Θ = 2 ε q r we have
ˆ
P(|E(W ) − E(G(k,
W ))| > εkW k∞ ) < ε.

(4.3)

A direct consequence of Theorem 4.4 is the corresponding result for layered ground state
energies.
Corollary 4.5. Let E be a finite layer set, K a compact Polish color set, q ≥ 1, r-arrays
J = (J e )e∈E with J e ∈ C(K)q×···×q , and ε > 0. Then we have that for any E-tuple of
r+7 r
(K, r)-graphon W = (W e )e∈E and k ≥ Θ4 log(Θ)q r with Θ = 2 ε q r that
ˆ
P(|E(W, J) − E(G(k,
W ), J)| > ε|E| kJk∞ kW k∞ ) < ε.

Proof. We make no specific restrictions on the color set K and on the set E of layers except
for finiteness of the second, therefore it will be convenient to rewrite the layered energies
Eφ (W, J) into a more universal form as a sum of proper Hamiltonians in order to suppress
the role of K and E. Let
Z
Y
X X
Eφ (W, J) =
φzj (x{j} )Jze1 ,...,zr (W e (x))dλ(xh([r]) )
e∈E z1 ,...,zr ∈[q]
j∈[q]
[0,1]h([r])

=

X

Z

Y

z1 ,...,zr ∈[q]
j∈[r]
[0,1]h([r])

φzj (x{j} )

"
X
e∈E

#

Jze1 ,...,zr (W e (x)) dλ(xh([r]) ).

Motivated by this reformulation we introduce for every (W, J) pair a special auxiliary instance
r
of the ground state problem that is defined for a [q]
of ([−d, d], r)-graphons, where d =
P -tuple
r
z
|E| kJk∞ kW k∞ . For any z ∈ [q] , let Ŵ (x) = e∈E Jze1 ,...,zr (W e (x)) for each x ∈ [0, 1]h([r]),
and let the interaction matrices Jˆz be of the canonical form. We obtain for any fractional
ˆ and also Ex (G(k, W ), J) =
partition φ of [0, 1] into q parts that Eφ (W, J) = Eφ (Ŵ , J),
ˆ
Ex (G(k, Ŵ ), J) for any fractional partition x, where the two random r-graphs are obtained via
the same sample. Therefore, without loss of generality, we are able to reduce the statement of
the corollary to the statement of Theorem 4.4 dealing with ground state energies of canonical
form.
27

We start with the proof of Theorem 4.4 by providing the necessary background. We
will proceed loosely along the lines of the proof of Theorem 4.3 from [4] with most of the
required lemmas being refinements of the respective ones in the proof of that theorem. We
will formulate and verify these auxiliary lemmas one after another, afterwards we will compile
them to prove the main statement. The arguments made in [4] carry through adapted to
our continuous setting with some modifications, and we will also draw on tools from [10] and
[11]. The first lemma tells us that in the real-valued case the energy of the sample and that
of the averaged sample do not differ by a large amount.
Lemma 4.6. Let W be a ([−d, d], r)-graphon, q ≥ 1, J ∈ Rq×···×q . Then for every k ≥ 1
there is a coupling of G(k, W ) and H(k, W ) such that
  2



εk
P |Ê(G(k, W ), J) − Ê(H(k, W ), J)| > εkJk∞ kW k∞ ≤ 2 exp −k
− log q
2
Proof. Let us fix a integer q-partition x of [k], and furthermore let the two random r-graphs
be generated by the same sample (US )S∈h([k],r). Then
1
Eˆx (G(k, W ), J) = r
k

q
X

k
X

z1 ,...,zr =1 n1 ,...,nr =1

Jz1 ,...,zr W ((US )S∈h({n1 ,...,nr },r) )

r
Y

xnj ,zj ,

j=1

and
Êx (H(k, W ), J)
1
= r
k

q
X

k
X

z1 ,...,zr =1 n1 ,...,nr =1

Jz1 ,...,zr E[W ((US )S∈h({n1 ,...,nr },r) ) | (US )S∈h({n1 ,...,nr },1) ]

Let us enumerate the elements of

k
2



r
Y

xnj ,zj .

j=1

as e1 , e2 , . . . , e(k) , and define the martingale
2

Y0 = E[Eˆx (G(k, W ), J) | { Uj | j ∈ [k] }],
and
h
i
Yt = E Eˆx (H(k, W ), J) | { Uj | j ∈ [k] } ∪ ∪tj=1 { US | ej ⊂ S }

for each 1 ≤ t ≤

k
2



, so that Y0 = Eˆx (H(k, W ), J) and Y(k) = Êx (G(k, W ), J). For each t ∈
2

we can upper bound the difference, |Yt−1 − Yt | ≤
inequality, Theorem 3.10, it follows that

ρ2 k 4
P(|Yt − Y0 | ≥ ρ) ≤ 2 exp − k
2 2 kJk2∞ kW k2∞

for any ρ > 0.

28

1
kJk∞ kW k∞ .
k2

!


≤ 2 exp −

k
2



By the Azuma-Hoeffding

ρ2 k 2
2kJk2∞ kW k2∞



,

(4.4)

There are q k distinct integer q-partitions of [k], hence

  2


εk
− log q
. (4.5)
P |Ê(G(k, W ), J) − Ê(H(k, W ), J)| > εkJk∞ kW k∞ ≤ 2 exp −k
2
In the following lemmas every r-graph or graphon is meant to be as bounded real-valued
and directed.
We would like to point out in the beginning that in the finite case we are able to shift
from the integer optimization problem to the relaxed one with having a reasonably good
upper bound on the difference of the optimal values of the two.
Lemma 4.7. Let G be a real-valued r-graph on [k] and J ∈ Rq×···×q . Then
1
ˆ
|E(G, J) − E(G,
J)| ≤ r 2 kGk∞ kJk∞ .
2k
ˆ
Proof. Trivially we have E(G, J) ≥ E(G,
J). We define G′ by setting all entries of G to 0
which have at least two coordinates which are the same (for r = 2 these are the diagonal
entries). Thus, we get that
 
r 1
′
|E(G, J) − E(G , J)| ≤
kGk∞ kJk∞ .
2 k
Now assume that we are given a fractional partition x so that Ex (G′ , J) attains the maximum
E(G′ , J). We fix all the entries xn,1 , . . . xn,q of x with n = 2, . . . , k and regard Ex (G′ , J) as a
function of x1,1 , . . . , x1,q . P
This function will be linear in the variables x1,1 , . . . , x1,q , and with
the additional condition rj=1 x1,j = 1 we obtain a linear program. By standard arguments
this program possesses an integer valued optimal solution, so we are allowed to replace
x1,1 , . . . , x1,q by integers without letting Ex (G′ , J) decrease. We repeat this procedure for each
ˆ ′ , J).
n ∈ [k], obtaining an integer optimum for Ex (G′ , J), which implies that E(G′, J) = E(G
Hence, the claim follows.
Next lemma is the continuous generalization of Theorem 4 from [4], and is closely related
to the Weak Regularity Lemma, ??, of [16], and its continuous version ??. The result is a
centerpiece of the cut decomposition method.
Lemma 4.8. Let ε > 0 arbitrary. For any bounded measurable function W : [0, 1]r → R
j
there exist an s ≤ ε12 , measurable sets
PsSi ⊂ [0, 1] with i = 1, . . . , s, j = 1, . . . , r, and real
numbers d1 , . . . , ds so that with B = i=1 di ISi1 ×···×Sir it holds that
(i) kW k2 ≥ kW − Bk2 ,

(ii) kW − Bk < εkW k2 , and
Ps
1
(iii)
i=1 |di | ≤ ε kW k2 .

29

Proof. We construct stepwise the required rectangles and the respective coefficients implicitly. Let W 0 = W , and suppose that after the t’th step of the construction we have already
obtained every setPSij ⊂ [0, 1] with i = 1, . . . , t, j = 1, . . . , r, and the real numbers d1 , . . . , dt .
Set W t = W − ti=1 di ISi1 ×···×Sir . We proceed to the (t + 1)’st step, where two possible
situations can occur. The first case is when
kW t k ≥ εkW k2.
1
r
This implies
by definition that there exist measurable subsets St+1
, . . . , St+1
of [0, 1] such
R
t
that | S 1 ×···×S r W (x)dλ(x)| ≥ εkW k2. We define dt+1 to be the average of W t on the
t+1

t+1

1
r
product set St+1
× · · · × St+1
, and proceed to the (t + 2)’nd step. In the case of

kW t k < εkW k2
we are ready with the construction and set s = t.
We analyze the first case to obtain an upper bound on the total number of steps required
by the construction. So suppose that the first case above occurs. Then
Z
Z
t 2
t+1 2
t 2
kW k2 − kW k2 =
(W ) (x)dλ(x) −
(W t (x) − dt+1 )2 dλ(x)
1 ×···×S r
St+1
t+1

1 ×···×S r
St+1
t+1

1
r
= d2t+1 λ(St+1
) . . . λ(St+1
) ≥ ε2 kW k22.

(4.6)

This means that the square of the 2-norm of W t decreases in t in every step when the first
case occurs in the construction by at least ε2 kW k22 , therefore it can happen only at most ε12
times, with other words s ≤ ε12 . It is also clear that the 2-norm decreases in each step, so
we are left to verify the upper bound on the sum of the absolute values of the coefficients
di . From (4.6) we get, that
kW k22

=

s
X
t=1

kW t−1 k22

−

kW t k22

≥

s
X

d2t λ(St1 ) . . . λ(Str ).

t=1

We also know for every t ≤ s that |dt |λ(St1) . . . λ(Str ) ≥ εkW k2 . Hence,
s
X
t=1

and therefore

Ps

t=1

|dt |εkW k2 ≤

s
X
t=1

d2t λ(St1 ) . . . λ(Str ) ≤ kW k22,

|dt | ≤ 1ε kW k2 .

Next we state that the cut approximation provided by Theorem 4.8 is invariant under
sampling. This is a crucial point of the whole argument, and is the r-dimensional generalization of Lemma 4.6 from [10].

30

Lemma 4.9. For any ε > 0 and bounded measurable function W : [0, 1]r → R we have that


ε2 k
P (|kH(k, W )k − kW k | > εkW k∞) < 2 exp −
32r 2
 2 4
.
for every k ≥ 16rε

Proof. Fix an arbitrary 0 < ε <1, r ≥ 2, and further let W be a real-valued naive r-kernel.
4
2
Set the sample size to k ≥ 16rε
. Let us consider the array representation of H(k, W ) and
denote the r-array AH(k,W ) by G that has zeros on the diagonal. We will need the following
lemma from [4].
Lemma 4.10. G is a real r-array on some finite product set V1 × · · · × Vr , where Vi are
copies of V of cardinality k. Let S1 ⊂ V1 , . . . , Sr ⊂ Vr be fixed subsets and Q1 a uniform
random subset of V2 × · · · × Vr of cardinality p. Then

kr
G(S1 , . . . , Sr ) ≤ EQ1 G(P (Q1 ∩ S2 × · · · × Sr ), S2 , . . . , Sr ) + √ kGk2 ,
p
P
where P (Q1 ) = PG (Q1 ) = { x1 ∈ V1 | (y2 ,...yr )∈Q1 G(x1 , y2 , . . . , yr ) > 0 } and the 2-norm
1/2
P
2
xi ∈Vi G (x1 ,...,xr )
.
denotes kGk2 =
|V1 |...|Vr |
If we apply Theorem 4.10 repeatedly r times to the r-arrays G and −G, then we arrive
at an upper bound on G(S1 , . . . , Sr ) ((−G)(S1 , . . . , Sr ) respectively) for any collection of the
S1 , . . . , Sr which does not depend on the particular choice of these sets any more, so we get
that
max{G(PG (Q′1 ), . . . , PG (Q′r )); (−G)(P−G (Q′1 ), . . . , P−G (Q′r ))}
k r kGk ≤ EQ1 ,...,Qr max
′
r

Qi ⊂Qi

rk
+ √ kGk∞ ,
p

(4.7)

since kGk2 ≤ kGk∞ .
Let us recall that G stands for the random H(k, W ). We are interested in the expectation
E of the left hand side of (4.7) over the sample that defines G. Now we proceed via the method
of conditional expectation. We establish an upper bound on the expectation of right hand
side of (4.7) over the sample U1 , . . . , Uk for each choice of the tuple of sets Q1 , . . . , Qr . This
bound does not depend on the actual choice of the Qi ’s, so if we take the average (over the
Qi ’s), that upper bound still remains valid.
In order to do this, let us fix Q1 , . . . , Qr , set Q to be the set of elements of V (G) which
are contained in at least one of the Qi ’s, and fix also the sample points of UQ = { Ui | i ∈ Q }.
Take the expectation EUQc only over the remaining Ui sample points.
To this end, by Fubini we have the estimate
max{G(PG (Q′1 ) ∩ Qc , . . . , PG (Q′r ) ∩ Qc );
k r EU[k] kGk ≤ EQ1 ,...Qr EUQ [EUQc max
′
Qi ⊂Qi

31

(−G)(P−G (Q′1 )

c

∩Q

, . . . , P−G (Q′r )

rk r
∩ Q )}] + √ kGk∞ + pr 3 k r−1 kGk∞ ,
p
(4.8)
c

where US = { Ui | i ∈ S }.
Our goal is to uniformly upper bound the expression in the brackets in (4.8) so that in
the dependence on the particular Q1 , . . . Qr and the sample points from UQ vanishes. To
achieve this, we consider additionally a tuple of subsets Q′i ⊂ Qi , and introduce the random
variable Y (Q′1 , . . . , Q′r ) = G(PG (Q′1 ) ∩ Qc , . . . , PG (Q′r ) ∩ Qc ), where the randomness comes
from UQc exclusively. Let
X
W (Uy1 , . . . , Uyi−1 , xi , Uyi+1 , . . . Uyr ) > 0 }
Ti = { xi ∈ [0, 1] |
(y1 ,...,yi−1 ,yi+1 ,...yr )∈Q′i

for i ∈ [r]. Note that ti ∈ PG (Q′i ) is equivalent to Uti ∈ Ti . Then
X
EUQc G(t1 , . . . , tr )IPG (Q′1 ) (t1 ) . . . IPG (Q′r ) (tr ) + r 2 k r−1 kW k∞
EUQc Y (Q′1 , . . . , Q′r ) ≤
t1 ,...,tr ∈Qc
ti 6=tj

≤k

r

Z

W (x)dλ(x) + r 2 k r−1 kW k∞ ≤ k r kW k + r 2 k r−1 kW k∞ .

T1 ×···×Tr

By the Azuma-Hoeffding inequality we also have high concentration of the random variable
Y (Q′1 , . . . , Q′r ) around its mean, that is
 2 
ρk
′
′
′
′
r
P(Y (Q1 , . . . , Qr ) ≥ EUQc Y (Q1 , . . . , Qr ) + ρk kW k∞ ) < exp − 2 ,
(4.9)
8r

since modification of one sampled element changes the value of Y (Q′1 , . . . , Q′r ) by at most
2rk r−1 kW k∞ . Analogous upper bounds on the expectation and the tail probability hold for
each of the expressions (−G)(P−G (Q′1 ), . . . , PG (Q′r )).
With regard to the maximum expression in (4.8) over the Q′i sets we have to this end either
that the concentration event from (4.9) holds for each possible choice of the Q′i subsets for
2
both expressions in the brackets in (4.8), this has probability at least 1 − 2pr+1 exp(− ρ8rk2 ), or
it fails for some choice. In the first case we can employ the upper bound k r kW k + (r 2 k r−1 +
ρk r )kW k∞ , and in the event of failure we still have the trivial upper bound of k r kW k∞ .
Eventually we presented an upper bound on the expectation that does not depend on the
choice of Q1 , . . . , Qr , and the sample points from UQ . Hence by taking expectation and
assembling the terms, we have
 2 

r2
ρk
r
pr 3
pr+1
+ρ+
+2
exp − 2
.
EU[k] kGk ≤ kW k + kW k∞ √ +
p
k
k
8r
√
2
√
Let p = k and ρ = 4r
4 . Then
k


 √
√ 
r3
4r 2 r 2
r
2
+ exp 2 kr − 2r k
+√ +√
+
EU[k] kGk ≤ kW k + kW k∞ √
4
4
k
k
k
k
32

≤ kW k + kW k∞



ε2
ε
ε4
ε2
ε
+ 8 + + 16 6 + 8 6
16r 2 r 4 2 r
2r



≤ kW k + ε/2kW k∞ .

The direction concerning the lower bound, EkGk ≥ kW k −ε/2 follows from a standard
sampling argument, the idea is that we can project each set S ⊂ [0, 1] to a set Ŝ ⊂ [k]
through the sample, which will fulfill the desired conditions, we leave the details to the
reader. Concentration follows by the Azuma-Hoeffding inequality. We conclude that


1
P (|kGk − kW k | > εkW k∞ ) ≤ P EkGk − r kGk > ε/2kW k∞
k


2
εk
≤ 2 exp −
.
32r 2
Next we state a result on the relationship of a continuous linear program (LP) and its
randomly sampled finite subprogram. We will rely on the next concentration result that is a
generalization of the Azuma-Hoeffding inequality, Theorem 3.10, and suits well the situation
when the martingale jump sizes have inhomogeneous distribution. It can be found together
with a proof in the survey [28] as Corollary 3.
Lemma 4.11 (Generalized Azuma-Hoeffding inequality). Let k ≥ 1 and (Xn )kn=0 be a martingale sequence with respect to the natural filtration (Fn )kn=1 . If |Xn − Xn+1 | ≤ d almost
surely and E[(Xn − Xn+1 )2 | Fn ] ≤ σ 2 for each n ∈ [k], then for every n ≤ k and δ > 0 it
holds that



σ2
δd
δd
δd
P(Xn − X0 > δn) ≤ exp −n 2 (1 + 2 ) ln(1 + 2 ) − 2
.
(4.10)
d
σ
σ
σ
Measurability for all of the following functions is assumed.
Lemma 4.12. Let cm : [0, 1] → R, Ui,m : [0, 1] → R for i = 1, . . . , s, m = 1, . . . , q, u ∈ Rs×q ,
2
α ∈ R. Let d and σ be positive reals such that kck∞ ≤ d and kck2 ≤ σ and set γ = σd2 . If the
optimum of the linear program

maximize

subject to

Z1 X
q

fm (t)cm (t)dt

0

m=1

Z1

fm (t)Ui,m (t)dt ≤ ui,m

0

0 ≤ fm (t) ≤ 1
q
X
fm (t) = 1

for i ∈ [s] and m ∈ [q]
for t ∈ [0, 1] and m ∈ [q]
for t ∈ [0, 1]

m=1

33

is less than α, then for any ε, δ > 0 and k ∈ N and a uniform random sample {X1 , . . . , Xk }
of [0, 1]k the optimum of the sampled linear program
maximize
subject to

q
X X
1
xn,m cm (Xn )
k
1≤n≤k m=1
X 1
xn,m Ui,m (Xn ) ≤ ui,m − δkUk∞
k
1≤n≤k

0 ≤ xn,m ≤ 1
q
X
xn,m = 1

for i ∈ [s] and m ∈ [q]
for n ∈ [k] and m ∈ [q]
for n ∈ [k]

m=1

is less than α + ε with probability at least




 2 
ε
ε
ε
δ k
+ exp −kγ (1 + ) ln(1 + ) −
.
1 − exp −
2
γd
γd
γd
Proof. We require a continuous version of Farkas’ Lemma.
R1
Claim 1. Let (Af )i,m = 0 Ai,m (t)fm (t)dt for the bounded measurable functions Ai,m on
[0, 1] for i ∈ [s] and m ∈ [q] , and let v ∈ Rsq . There is no fractional q-partition solution
f = (f1 , . . . , fq ) to Af ≤ v if and only if, there exists a non-zero 0 ≤ y ∈ Rsq with kyk1 = 1
such that there is no fractional q-partition solution f to y T (Af ) ≤ y T v.
For clarity we remark that in the current claim and the following one Af and v are indexed
by a pair of parameters, but are regarded as 1-dimensional vectors in the multiplication
operation.

Proof. One direction is trivial: if there is a solution f to Af ≤ v, then it is also a solution
to y T (Af ) ≤ y T v for any y ≥ 0.
We turn to show the opposite direction. Let
C = { Af | f is a fractional q-partition of [0, 1] }.
The set C is a nonempty convex closed subset of Rsq containing 0. Let B = { x | xi,m ≤
vi,m } ⊂ Rsq , this set is also a nonempty convex closed set. The absence of a solution to
Af ≤ v is equivalent to saying that C ∩ B is empty. It follows from the Separation Theorem
for convex closed sets that there is a 0 6= y ′ ∈ Rsq such that y ′T c < y ′T b for every c ∈ C
′
and b ∈ B. Additionally every coordinate yi,m
has to be non-positive. To see this suppose
′
that yi0 ,m0 > 0, we pick a c ∈ C and b ∈ B, and send bi0 ,m0 to minus infinity leaving every
other coordinate of the two points fixed (b will still be an element of B), for bi0 small enough
the inequality y ′T c < y ′T b will be harmed eventually. We conclude that for any f we have
′
y ′T (Af ) < y ′T v, hence for y = ky−y′ k1 the inequality y T (Af ) ≤ y T v has no solution.
From this lemma the finitary version follows without any difficulties.
34

Claim 2. Let B be a real sq × k matrix, and let v ∈ Rsq . There is no fractional q-partition
x ∈ Rkq so that Bx ≤ v if and only if, there is a non-zero 0 ≤ y ∈ Rsq with kyk1 = 1 such
that there is no fractional q-partition x ∈ Rkq so that y T Bx ≤ y T v.
P
B
Proof. Let Ai,m (t) = kn=1 (i,m),n
I[ n−1 , n ) (t) for i = 1, . . . , s. The nonexistence of a fractional
k
k
k
kq
q-partition x ∈ R so that Bx ≤ v is equivalent to nonexistence of a fractional q-partition f
so that Af ≤ v. For any nonzero 0 ≤ y, the nonexistence of a fractional q-partition x ∈ Rkq
so that y T Bx ≤ y T v is equivalent to the nonexistence of a fractional q-partition f so that
y T (Af ) ≤ y T v. Applying Claim 1 verifies the current claim.
The assumption of the lemma is by P
ClaimP
1 equivalent to the statement that there exists
a nonzero 0 ≤ y ∈ Rsq and 0 ≤ β with si=1 qm=1 yi,m + β = 1 such that
Z1 X
q
s X
0

i=1 m=1

Z1

yi,m Ui,m (t)fm (t)dt −

β

0

q
X

m=1

cm (t)fm (t) ≤

q
s X
X

i=1 m=1

yi,m ui,m − βα

has no solution f among fractional q-partitions. This is equivalent to the condition
Z1

h(t)dt > A,

0

Ps Pq
P
where h(t) = min [ si=1 yi,mUi,m (t) − βcm (t)], and A =
m=1 yi,m ui,m − βα. Let
i=1
mP
s
Tm = { t | h(t)
i=1 yi,m Ui,m (t) − βcm (t)
P=
P}q for m ∈ [q] and define the functions h1 (t) =
P
s
q
(t)
[
y
U
(t)]
and
h
(t)
=
I
i,m i,m
2
m=1 ITm (t)βcm (t). Clearly, h(t) = h1 (t)−h2 (t).
m=1 Tm
P
Pi=1
q
s
Set also A1 = i=1 m=1 yi,m ui,m and A2 = βα. Fix an arbitrary δ > 0 and k ≥ 1. By the
2
Azuma-Hoeffding inequality it follows that with probability at least 1 − exp(− kδ2 ) we have
that
k
1X
h1 (Xn ) > A1 − δkh1 k∞ .
k n=1
P P
P P
Note that kh1 k∞ = k si=1 qm=1 ITm Ui,m yi,m k∞ ≤ kUk∞ si=1 qm=1 |yi,m| ≤ kUk∞ . Moreover, by Theorem 4.11 the event
k

1X
h2 (Xn ) < A2 + ε
k n=1


has probability at least 1 − exp −kγ (1 +
k

s

ε
) ln(1
γd

q

+

ε
)
γd

(4.11)
−

ε
γd



. Thus,

XX
1X
yi,m (ui,m − δkUk∞ ) − β(α + ε)
h(Xn ) >
k n=1
i=1 m=1
35

with probability at least

 2 



δ k
ε
ε
ε
1 − exp −
+ exp −kγ (1 + ) ln(1 + ) −
.
2
γd
γd
γd
We conclude the proof by noting that the last event is equivalent to the event in the
statement of our lemma by Claim 2.
We start the principal part of the proof of the main theorem in this paper.
Proof of Theorem 4.4. It is enough to prove Theorem 4.4 for tuples of naive ([−d, d], r)digraphons. We first employ Theorem 4.6 to replace the energy Ê(G(k, W )) by the energy
ˆ
of the averaged sample E(H(k,
W )) without altering the ground state energy of the sample
substantially with high probability. Subsequently, we apply Theorem 4.7 to change from the
ˆ
integer version of the energy E(H(k,
W )) to the relaxed one E(H(k, W )). That is
|Ê(G(k, W )) − E(H(k, W ))| ≤ ε2 kW k∞
with probability at least 1 − ε2 .
We begin with the main argument by showing that the ground state energy of the sample
can not be substantially smaller than that of the original, formally
E(H(k, W )) ≥ E(W ) −

r2
kW k∞
k 1/4

(4.12)

with high probability. In what follows E denotes the expectation with respect to the uniform
independent random sample (US )S∈h([k],r) from [0, 1]. To see the correctness of the inequality,
we consider a fixed fractional partition φ of [0, 1], and define the random fractional partition
of [k] as yn,m = φm (Un ) for every n ∈ [k] and m ∈ [q]. Then we have that
EE(H(k, W )) ≥ EEy (H(k, W ))

k
r
Y
1 X X
z
=E r
W (Uh({n1 ,...,nr },r) )
ynj ,zj
k
r
j=1
z∈[q] n1 ,...,nr =1
Z
r
Y
X
r2
k!
W z (th([r]) )
φzj (tj )dλ(t) − kW k∞
≥ r
k (k − r)!
k
r
j=1
z∈[q]

[0,1]h([r])

2

≥ Eφ (W ) −

r
kW k∞ .
k

This argument proves the claim in expectation, concentration will be provided by standard martingale arguments. For convenience, we define a martingale by Y0 = EE(H(k, W ))
and Yj = E [E(H(k, W )) | { US | S ∈ h([j], r − 1) }] for 1 ≤ j ≤ k. The difference |Yj −
36

kW k∞ is bounded from above for any j, thus by the inequality of Azuma and
Yj+1| ≤ 2r
k
Hoeffding, Theorem 3.10, it follows that


2r 2
P E(H(k, W )) < E(W ) − 1/4 kW k∞
k


r2
≤ P E(H(k, W )) < EE(H(k, W )) − 1/4 kW k∞
k
√ !


r2 k
r2
.
(4.13)
= P Yk < Y0 − 1/4 kW k∞ ≤ exp −
k
8
So the lower bound (4.12) on E(H(k, W )) is established. Note that
by the condition regarding
√
r2 k
k we can establish (rather crudely) the upper bound exp(− 8 ) ≤ ε2−7.
Now we turn to prove that E(H(k, W )) < E(W ) + ε holds also with high probability
 r+7 r 4
r+7 r
for k ≥ 2 ε q r log( 2 ε q r )q r . Our two main tools will be Theorem 4.8, that is a variant
the Cut Decomposition Lemma from [4] (closely related to the Weak Regularity Lemma
by Frieze and Kannan [16]), and linear programming duality, in the form of Theorem 4.12.
Recall the definition of the cut norm, for W : [0, 1]r → R, it is given as
kW k =

Z

max

S 1 ,...,S r ⊂[0,1]

W (x)dλ(x) ,

S 1 ×···×S r

and for an r-array G by the expression
kGk =

1
kr

max

S 1 ,...,S r ⊂V (G)

G(S 1 , . . . , S r ) .

Before starting the second part of the technical proof, we present an informal outline. Our
task is to certify that there is no assignment of the variables on the sampled energy problem,
which produces an overly large value relative to the ground state energy of the continuous
problem. For this reason we build up a cover of subsets over the set of fractional partitions of
the variables of the finite problem, also build a cover of subsets over the fractional partitions
of the original continuous energy problem, and establish an association scheme between the
elements of the two in such a way, that with high probability we can state that the optimum
on one particular set of the cover of the sampled energy problem does not exceed the optimal
value of the original problem on the associated set of the other cover. To be able to do this,
first we have to define these two covers, this is done with the aid of the cut decomposition, see
Theorem 4.8. We will replace the original continuous problem by an auxiliary one, where the
number of variables will be bounded uniformly in terms of our error margin ε. Theorem 4.9
makes it possible for us to replace the sampled energy problem by an auxiliary problem with
the same complexity as for the continuous problem. This second replacement will have a
straightforward relationship to the approximation of the original problem. We will produce
the cover sets of the two problems by localizing the auxiliary problems, association happens
37

through the aforementioned straightforward connection. Finally, we will linearize the local
problems, and use the linear programming duality principle from Theorem 4.12 to verify
that the local optimal value on the sample does not exceed the local optimal value on the
original problem by an infeasible amount, with high probability.
Recall that for a φ = (φ1 , . . . , φq ) a fractional q-partition of [0, 1] the energy is given by
the formula
X Z Y
φzj (tj )W z (t)dλ(t),
(4.14)
Eφ (W ) =
z∈[q]r[0,1]r j∈[r]

and for an x = (x1,1 , x1,2 , . . . , x1,q , x2,1 , . . . , xk,q ) a fractional q-partition of [k] by
X 1
Ex (H(k, W )) =
kr
r
z∈[q]

k
X

Y

xtj ,zj W z (Un1 , . . . , Unr ).

(4.15)

n1 ,...,nr =1 j∈[r]

We are going to establish a term-wise connection with respect to the parameter z in the
previous formulas. Therefore we consider the function
Z Y
z
z
Eφ (W ) =
φzj (tj )W z (t)dλ(t),
(4.16)
[0,1]r j∈[r]

P

it follows that Eφ (W ) =

z∈[q]r

Eφz (W z ). Analogously we consider

Exz (H(k, W z ))

1
= r
k

k
X

Y

xtj ,zj W z (Un1 , . . . , Unr ),

n1 ,...,nr =1 j∈[r]

so Ex (H(k, W )) = z∈[q]r Exz (H(k, W z )) with the sampled graphs on the right generated by
the same sample points. Note that the formulas (4.14)-(4.16) make prefect sense even when
the parameters φ and x are only vectors of bounded functions and reals respectively without
forming partition.
6 2r
Theorem 4.8 delivers for any z ∈ [q]r an integer sz ≤ 2 εq2 , measurable sets Sz,i,j ⊂ [0, 1]
with i = 1, . . . , sz , j = 1, . . . , r, and the real numbers dz,1 , . . . , dz,sz such that the conditions
of the lemma are satisfied, namely
P

kW z −
Psz

8q r

sz
X
i=1

dz,i ISz,i,1 ×···×Sz,i,r k ≤

ε
kW z k2 ,
8q r

and i=1 |dz,i | ≤ ε kW z k2 . The
Psz cut function allows a sufficiently good approximation for
z
z
Eφ (W ), for any φ. Let D = i=1 dz,i ISz,i,1 ×···×Sz,i,r . Then
|Eφz (W z )

−

Eφz (D z )|

=

Z

Y

[0,1]r j∈[r]

φzj (tj ) [W z (t) − D z (t)] dλ(t)

38

≤ kW z − D z k ≤

ε
kW z k∞ .
8q r

We apply the cut approximation to W z for every z ∈ [q]r to obtain the [q]r -tuple of naive
r-kernels D = (D z )z∈[q]r . We define the ”push-forward” of this approximation for the sample
H(k, W ). To do this we need to define the subsets [k] ⊃ Ŝz,i,j = { m | Um ∈ Sz,i,j }. Let
Pz
dz,i IŜz,i,1 ×···×Ŝz,i,r . First we condition on the event from Theorem 4.9, call this
D̂ z = si=1
event E1 , that is

\ 
ε
z
z
z
z
kH(k, W ) − D̂ k − kW − D k < r kW k∞ .
E1 =
8q
r
z∈[q]

On E1 it follows that for any x that is a fractional q-partition
|Exz (H(k, W z )) − Exz (D̂ z )| ≤ kH(k, W z ) − D̂ z k
ε
≤ kW z − D z k + r kW k∞ .
8q
This implies that
ε
and |Ex (H(k, W )) − Ex (H(k, D))| ≤ kW k∞ .
4


 7 r 2 4
2
The probability that E1 fails is at most 2q r exp − 211εr2kq2r whenever k ≥ 2 qε r
due to
 r+7 r 4
r+7 r
Theorem 4.9, in the current theorem we have the condition k ≥ 2 ε q r log( 2 ε q r )q r ,
which implies the aforementioned one. The failure probability of E1 is then strictly less than
ε
.
27
Let S = { Sz,i,j | z ∈ [q]r , 1 ≤ i ≤ sz , 1 ≤ j ≤ r } denote their set, and let S ′ stand for
the corresponding set on the sample. Note that s′ = |S| ≤ 26 rq 3r ε12 in general, but in some
cases the W z functions are constant multiples of each other, so the cut approximation can be
chosen in a way that Sz,i,j does not depend on z ∈ [q]r , and in this case we have the slightly
refined upper bound 26 rq 2r ε12 for s′ , consequences of this in the special case are discussed in
the remark after the proof. Let η > 0 be arbitrary, and define the sets
ε
|Eφ (W ) − Eφ (D)| ≤ kW k∞
8

I(b, η) =







and
I ′ (b, η) =

φ | ∀z ∈ [q]r , 1 ≤ i ≤ sz , 1 ≤ j ≤ r :





Z

φzj (t)dt − bz,i,j ≤ 2η

Sz,i,j

x | ∀z ∈ [q]r , 1 ≤ i ≤ sz , 1 ≤ j ≤ r :
39

1
kU

X

n ∈Sz,i,j





,




xn,zj − bz,i,j ≤ η





For a collection of non-negative reals {bz,i,j }. At this point in the definitions of the above sets
we do not require φ and x to be fractional q-partitions, but to be vectors of bounded functions
and vectors respectively. We will use the grid points A = { (bz,i,j )z,i,j | ∀z, i, j : bz,i,j ∈
[0, 1] ∩ ηZ }.
On every nonempty set I(b, η) we can produce a linear approximation of Eφ (D) (linearity
is meant in the functions φm ) which carries through to a linear approximation of Ex (H(k, D))
via sampling. The precise description of this is given in the next auxiliary result.
Lemma 4.13 (Local linearization). If η ≤ 16qεr 2r , then for every b ∈ A there exist l0 ∈ R
and functions l1 , l2 , . . . , lq : [0, 1] → R such that for every φ ∈ I(b, η) it holds that
Z1 X
q

Eφ (D) − l0 −

0

lm (t)φm (t)dt <

m=1

ε
2r+3

kW k∞ ,

and for every x ∈ I ′ (b, η) we have
q
k X
X
1
ε
Ex (H(k, D)) − l0 −
xn,m lm (Ui ) < r+5 kW k∞ .
k
2
n=1 m=1

Additionally we have that l1 , l2 , . . . , lq are bounded from above by
22r+9 r 2 q 3r kW k2∞ .

8q 2r
kW k∞
ε

and

R 1 Pq
0

2
m=1 lm (t)dt

Proof. Recall the decomposition of the energies as sums over z ∈ [q]r into terms
Eφz (D z )

=

sz
X

dz,i

i=1

=

sz
X

[0,1]r

dz,i

i=1

and
Exz (D̂ z )

Z Y
r

=

Z

[0,1]r

sz
X
i=1

j=1

φzj (tj )ISz,i,1 ×···×Sz,i,r (t)dt

q
r
Y
Y

m=1 j=1
zj =m

φm (tj )ISz,i,1 ×···×Sz,i,r (t)dt,

q
r
1 Y Y
dz,i r
k m=1 j=1

zj =m

X

xn,m .

n : Un ∈Sz,i,j

We linearize and compare the functions Eφz (D z ) and Exz (D̂ z ) term-wise. In the end we will
sum up the errors and deviations occurred at each term. Let b ∈ A and η > 0 as in the
statement of the lemma with I(b, η) being nonempty. Let us fix an arbitrary φ ∈ I(b, η),
z ∈ [q]r , and 1 ≤ i ≤ sz . Then

 1
 1

Z
Z
r
r
Y
X
 φzj (tj )ISz,i,j (tj )dtj  = B i (z) +
 φzj (tj )ISz,i,j (tj )dtj − bz,i,j  B i,j (z) + ∆
j=1

0

j=1

0

40

≤



1

= (1 − r)B i (z) +

q Z
X

m=1 0

φm (t) 

r
X

j=1,zj =m



ISz,i,j (t)B i,j (z) dt + ∆,

Q
Q
where B i (z) stands for rj=1 bz,i,j , B i,j (z) = l6=j bz,i,l , and |∆| ≤ 4η 2 2r . Analogously for an
arbitrary fixed element x ∈ I ′ (b, η) and a term of Exz (D̂ z ) we have


r
Y
X
1
xn,zj − bz,i,j + bz,i,j 
k
j=1
n : Un ∈Sz,i,j


q
k
r
XX 1
X
= (1 − r)B i (z) +
xn,m 
ISz,i,j (Un )B i,j (z) + ∆′ ,
k
m=1 n=1
j=1,z =m
j

where |∆′ | ≤ η 2 2r .
If we multiply these former expressions by the respective coefficient dz,i and sum up over
i and z, then we obtain the final linear approximation consisting of the constant l0 and the
functions l1 , . . . , lq . We would like to add that these objects do not depend on η if I(b, η) is
nonempty, only the accuracy of the approximation does. As overall error in approximating
2r
ε
kW k∞ , and in
the energies we get in the first case of Eφ (D) at most 32η 2 2r qε kW k∞ ≤ 2r+3
ε
the second case of Ex (H(k, D)) at most 2r+5 kW k∞ .
Now we turn to prove the upper bound on |lm (t)|. Looking at the above formulas we
could write out lm (t) explicitly, for our upper bound it is enough to note that
r
X

ISz,i,j (t)B i,j (z)

j=1,zj =m

is at most r. So it follows that for any t ∈ [0, 1] it holds that

8q 2r
rkW k∞ .
ε
R1P
2
It remains to verify the assertion regarding 0 qm=1 lm
(t)dt. Note that I(b, η) ⊂ I(b, 2η),
so we can apply the same linear approximation to elements ψ of I(b, 2η) as above with a
ε
kW k∞ from Eψ (D). Let φ be an arbitrary element
deviation of at most 2r+1
Pq of I(b, η), and
let T ⊂ [0, 1] denote the set of measure η corresponding to the largest m=1 |lm (t)| values.
Define
(
φm (t) + sgn(lm (t)) if t ∈ T
φ̂m (t) =
φm (t)
otherwise.
|lm (t)| ≤

Then φ̂ ∈ I(b, 2η), since kφm − φ̂m k1 ≤ η for each m ∈ [q], but φ̂ is not necessarily a fractional
partition. Therefore we have
Z X
q
T

m=1

|lm (t)|dt =

Z1 X
q
0

(φ̂m (t) − φm (t))lm (t)dt

m=1

41

≤

Z1 X
q

m=1

0

φ̂m (t)lm (t)dt − Eφ̂ (D) + |Eφ̂ (D) − Eφ (D)|
Z1 X
q

+

m=1

0

5

≤

φm (t)lm (t)dt − Eφ (D)

εkW k∞ + |Eφ̂ (D) − Eφ (D)|.
2r+3
We have to estimate the last term of the above expression.
!
r
r
X Z
Y
Y
|Eφ̂ (D) − Eφ (D)| ≤
φzj (tj ) −
φ̂zj (tj ) D z (t)dt
z∈[q]r [0,1]r

≤ 2kW k∞

j=1

r
r
Y
X Z X

z∈[q]r[0,1]r j=1
r r−1

≤ 2kW k∞ 2 q

T

m=1

r

q
X

m=1

We conclude that
Z X
q

j=1

i>j

5
2r+3

r
+ 3
2

This further implies that for each t ∈
/ T we have
r+1
r
(10 + 2 r) q kW k∞ . These former bounds indicate
Z1 X
q
0

2
lm
(t)dt

Z

=

m=1

[0,1]\T

≤2

q
X

2
lm
(t)dt

+

m=1

r q

kW k2∞



εkW k∞.

Pq

m=1

Z X
q
T

2r+8 2 2r

φ̂zi (ti )(φ̂zj (tj ) − φzj (tj )) dt

kφm − φ̂m k1 ≤ 2kW k∞ 2r q r rη.



|lm (t)|dt ≤

φzi (ti )

i<j

r
Y

|lm (t)| ≤

≤
≤

(2

r
23

ε

η

kW k∞ ≤

m=1

+ klk∞

2
r q kW k2∞ +
22r+9 r 2 q 3r kW k2∞ .

+

2
lm
(t)dt

Z X
q
T

2r+8 2 2r

5
2r+3

r+4

m=1

|lm (t)|dt

rq r )(8q 2r r)kW k2∞

We return to the proof of the main theorem, and set η = 16qεr 2r . For each b ∈ A we apply
Theorem 4.13, so that we have for any φ ∈ I(b, η) and x ∈ I ′ (b, η) that
1

Eφ (W ) − l0 −

q Z
X

φm (t)lm (t)dt =

m=1 0

42

ε
2r+3

kW k∞ ,

Ex (H(k, W )) − l0 −

k
X
1
n=1

k

xn,m lm (Un ) =

ε
2r+5

kW k∞ ,

since η is small enough. Note that l0 , l1 , . . . , and lq inherently depend on b. We introduce
the event E2 (b), which stands for the occurrence of the following implication:
If the linear program
maximize
subject to

q
k X
X
1
l0 +
xn,m lm (Un )
k
n=1 m=1

x ∈ I ′ (b, η)
0 ≤ xn,m ≤ 1
q
X
xn,m = 1

for n = 1, . . . , k and m = 1, . . . , q
for m = 1, . . . , q

m=1

has optimal value α, then the continuous linear program
maximize

l0 +

Z1 X
q
0

subject to

lm (t)φm (t)dt

m=1

φ ∈ I(b, η)
0 ≤ φm (t) ≤ 1
q
X
φm (t) = 1

for t ∈ [0, 1] and m = 1, . . . , q
for t ∈ [0, 1]

m=1

has optimal value at least α − (ε/2)kW k∞ .
2r

We apply Theorem 4.12 with δ = η, σ 2 = 22r+9 r 2 q 3r kW k2∞ , d = 8qε rkW k∞ , and γ =
and attain that the probability that E2 (b) fails is at most





εkW k∞
kη 2
εkW k∞
εkW k∞
+ exp −kγ (1 +
exp −
) ln(1 +
)−
2
γd
γd
γd





2
1
kε
≤ exp − 8 2r 2r + exp −kε2 22r+3 q −r
4r+15
2 q 2
2
qr r2






kε2
kε2
kε2
= exp − 2r+8 2r + exp − 2r+12 2r 2 ≤ 2 exp − 2r+12 2r 2 ,
2
q
2
q r
2
q r

σ2
,
d2

where we used that (1 + x) ln(1 + x) − x ≥ (1 + x)(x − x2 /2) − x = x2 /2 − x3 /2 ≥ x2 /4 for
0 ≤ x ≤ 41 . Denote by E2 the event that for each b ∈ A the event E2 (b) occurs. Then we
have


 r+3 r 26 rq3r 12
ε
kε2
2 q
exp − 2r+12 2r 2
P(E2 ) ≥ 1 − 2
ε
2
q r
43


  r+3 r 
2r+7q r r 2r+16 2 3r −2
2 q
6 3r −2
2 rq ε − log(
)2
r q ε
≥ 1 − 2 exp log
ε
ε


2r+7q r r 2r+15 2 3r −2
)2
r q ε
≥ 1 − 2 exp − log(
ε
≥ 1 − ε/4.
 r+7 r 4
r+7 r
Therefore for k ≥ 2 ε q r log( 2 ε q r )q r we have that P(E1 ∩ E2 ) ≥ 1 − ε/2. We only need
to check that conditioned on E1 and E2 our requirements are fulfilled. For this, consider
an arbitrary fractional q-partition of [k] denoted by x. For some b ∈ A we have that
x ∈ I ′ (b, η). If we sum up the error gaps that were allowed for the Cut Decomposition and at
the local linearization stage, then the argument we presented above yields that there exists
a φ ∈ I(b, η) such that conditioned on the event E1 ∩ E2 it holds
Eφ (W ) ≥ Ex (H(k, W )) − εkW k∞ .
This is what we wanted to show.
We can improve on the tail probability bound in Theorem 4.4 significantly by a constant
factor strengthening of the lower threshold condition imposed on the sample size.
Corollary 4.14. Let r ≥ 1, q ≥ 1, and ε > 0. Then for any [q]r -tuple of ([−d, d], r)-graphons
r+10 r
W = (W z )z∈[q]r and k ≥ Θ4 log(Θ)q r with Θ = 2 ε q r we have that
 2 
εk
(4.17)
P(|E(W ) − Ê(G(k, W ))| > εkW k∞) < 2 exp − 2 .
8r
Proof. For k ≥ Θ4 log(Θ)q r we appeal to Theorem 4.4, hence

ˆ
ˆ
|E(W ) − EE(G(k,
W ))| ≤ P(|E(W ) − E(G(k,
W ))| > ε/8kW k∞)2kW k∞ + ε/8kW k∞
< ε/2kW k∞ .

Using a similar martingale construction to the one in the first part of the proof of Theorem 4.4
the Azuma-Hoeffding inequality can be applied, thus
ˆ
P(|E(W ) − E(G(k,
W ))| > εkW k∞ ) ≤ P(|EÊ(G(k, W )) − Ê(G(k, W ))| > ε/2kW k∞)
 2 
ε k
≤ 2 exp − 2 .
8r
Remark 4.15. A simple investigation of the above proof also exposes that in the case when
the W z ’s are constant multiples of each other then we can employ the same cut decomposition
to all of them with the right scaling, which implies that the upper bound on |S| can be
strengthened to 26 rq 2r ε12 , gaining a factor of q r . Therefore in this case the statement of
 r+10 r 4
r+10 r
Theorem 4.14 is valid with the improved lower bound condition 2 ε q r log( 2 ε q r ) on
k.
44

Remark 4.16. Suppose that f is the following simple graph parameter. Let q ≥ 1, m0 ≥ 1,
and g be a polynomial of l variables and degree d with values between 0 and 1 on the unit
cube, where l is the number of unlabeled node-q-colored graphs on m0 vertices, whose set
2
we denote by Mq,m0 . Note that l ≤ 2m0 /2 q m0 . Let then
f (G) = max g((t(F, (G, T )))F ∈Mq,m0 ),

(4.18)

T

where the maximum goes over all node-q-colorings of G, and (G, T ) denotes the node-qcolored graph by imposing T on the node set of G. Using the identity t(F1 , G)t(F2 , G) =
t(F1 ∪ F2 , G), where F1 ∪ F2 is the disjoint union of the (perhaps colored) graphs F1 and F2 ,
we can replace in (4.18) g by g ′ that is linear, and its variables are indexed by Mq,dm0 . Then
it becomes clear that f can be regarded as a ground state energy of dm0 -dimensional arrays
by associating to every G an tuple (Az )z∈[q]r with r = dm0 , where the entries Az (i1 , . . . , ir )
are the coefficients of g ′ corresponding to the element of Mq,dm0 given by the pair z and
G|(i1 ,...,ir ) . We conclude that f is efficiently testable by Theorem 4.4.

5

Testability of variants of the ground state energy

In the current section we derive further testability results using the techniques employed
in the proofs of the previous section, and apply Theorem 4.4 to some specific quadratic
programming problems.

5.1

Microcanonical version

Next we will state and prove the microcanonical version of Theorem 4.4, that is the continuous generalization of the main result of [13] for an arbitrary number q of the states. To be
able to do this, we require the microcanonical analog of Theorem 4.7, that will be a generalization of Theorem 5.5 from [11] for arbitrary r-graphs (except for the fact that we are
not dealing with node weights), and its proof will also follow the lines of the aforementioned
theorem. Before stating the lemma, we outline some notation and state yet another auxiliary
lemma.
P
Definition 5.1. Let for a = (a1 , . . . , aq ) ∈ Pdq (that is, ai ≥ 0 for each i ∈ [q] and i ai = 1)
denote


Z1


Ωa = φ fractional q-partition of [0, 1] | φi (t)dt = ai for i ∈ [q] ,


0

ωa =





x fractional q-partition of V (G) |

45

1
|V (G)|

X

u∈V (G)

xu,i = ai for i ∈ [q]





,

and
ω̂a =

(

x integer q-partition of V (G) |

P

u∈V (G)

xu,i

|V (G)|

1
− ai ≤
for i ∈ [q]
|V (G)|

)

.

The elements of the above sets are referred to as integer a-partitions and fractional apartitions, respectively.
We call the following expressions microcanonical ground state energies with respect to a
for (K, r)-graphs and graphons and C(K)-valued r-arrays J, in the finite case we add the
term fractional and integer respectively to the name. Denote
Ea (W, J) = max Eφ (W, J),
φ∈Ωa

Ea (G, J) = max Ex (G, J),
x∈ωa

Êa (G, J) = max Ex (G, J).
x∈ω̂a

The layered versions for a finite layer set E, and the canonical versions Ea (W ), Ea (G),
and Eˆa (G) are defined analogously.
The requirements for an x to be an integer fractional a-partition (that is φ ∈ Ωa ) are
rather strict and we are not able to guarantee with high probability that if we sample from
an fractional a-partition of [0, 1], that we will receive an fractional a-partition on the sample,
in fact this will not happen with probability 1. To tackle this problem we need to establish
an upper bound on the difference of two microcanonical ground state energies with the same
parameters. This was done in the two dimensional case in [11], we slightly generalize that
approach.
Lemma 5.2. Let r ≥ 1, and q ≥ 1. Then for any [q]r -tuple of naive r-kernels W =
(W z )z∈[q]r , and probability distributions a, b ∈ Pdq we have
|Ea (W ) − Eb (W )| ≤ rkW k∞ ka − bk1 .
The analogous statement is true for a [q]r -tuple of ([−d, d], r)-digraphs G = (Gz )z∈[q]r ,
|Ea (G) − Eb (G)| ≤ rkGk∞ ka − bk1 .
Proof. We will find for each fractional a-partition φ a fractional b-partition φ′ and vice
versa, so that the corresponding energies are as close to each other as in the statement. So
let φ = (φ1 , . . . , φq ) be an arbitrary fractional a-partition, we define φ′i so that the following
holds: if ai ≥ bi then φ′i (t) ≤ φi (t) for every t ∈ [0, 1], otherwise φ′i (t) ≥ φi (t) for every
t ∈ [0, 1]. It is easy to see that such a φ′ = (φ′1 , . . . , φ′q ) exists. Next we estimate the energy
deviation.
|Eφ (W ) − Eφ′ (W )| ≤

X

Z

z∈[q]r [0,1]r

φz1 (x1 ) . . . φzr (xr ) − φ′z1 (x1 ) . . . φ′zr (xr )dλ(x) kW k∞

46

≤
=

Z
r
X X

z∈[q]r m=1 [0,1]r
r Z
X X

z∈[q]r

=

m=1
[0,1]

q Z
r X
X

m=1 j=1

(φzm (xm ) − φ′zm (xm ))

Y

j<m

φzm (xm ) − φ′zm (xm ) dxm
φj (t) − φ′j (t) dt

[0,1]

q
X
j=1

φzj (xj )

aj

Y

j<m

!m−1

Y

j>m

azj

Y

j>m
q
X

bj

j=1

φ′zj (xj )dλ(x) kW k∞

bzj kW k∞
!r−m−1

kW k∞

= rka − bk1 kW k∞ .
The same way we can find for any fractional b-partition φ an fractional a-partition φ′ so that
their respective energies differ at most by rka − bk1 kW k∞ . This implies the first statement
of the lemma. The finite case is proven in a completely analogous fashion.
We are ready to show that the difference of the fractional and the integer ground state
energies is o(|V (G)|) whenever all parameters are fixed, this result is a generalization with
respect to the dimension in the non-weighted case of Theorem 5.5 of [11], the proof proceeds
similar to the one concerning the graph case that was dealt with in [11].
Lemma 5.3. Let q, r, k ≥ 1,a ∈ Pdq , and G = (Gz )z∈[q]r be a tuple of ([−d, d], r)-graphs on
[k]. Then
1
|Ea (G) − Eˆa (G)| ≤ kGk∞ 5r q r+1 .
k
Proof. The inequality Ea (G) ≤ Êa (G) + k1 kGk∞ 5r q r+1 follows from Theorem 5.2. Indeed, for
this bound a somewhat stronger statement it possible,
Eˆa (G) ≤

q
Eb (G) ≤ Ea (G) + r kGk∞ .
b : |bi −ai |≤1/k
k
max

Now we will show that Eˆa (G) ≥ Ea (G) − k1 kGk∞ 5r q r+1 . We consider an arbitrary fractional
a-partition x. A node i from [n] is called bad in a fractional partition x, if at least two
elements of {xi,1 , . . . , xi,q } are positive. We will reduce the number of fractional entries of
the bad nodes of x step by step until we have at most q of them, and keep track of the cost
of each conversion, at the end we round the corresponding fractional entries of the remaining
bad nodes in some certain way.
We will describe a step of the reduction of fractional entries. For now assume that we
have at least q + 1 bad nodes and select an arbitrary set S of cardinality q + 1 of them. To
each element of S corresponds a q-tuple of entries and each of these q-tuples has at least two
non-{0, 1} elements.
We reduce the number of fractional entries corresponding to S while not disrupting any
entries corresponding to nodes that lie outside of S. To do this we fix for each i ∈ [q] the
47

P
P
sums v∈S xv,i and for each v ∈ S the sums qi=1 xv,i (these latter are naturally fixed to be
1), in total 2q + 1 linear equalities. We have at least 2q + 2 fractional entries corresponding to
S, therefore there exists a subspace of solutions of dimension at least 1 for the 2q + 1 linear
equalities. That is, there is a family of fractional partitions parametrized by −t1 ≤ t ≤ t2
for some t1 , t2 > 0 that obey our 2q + 1 fixed equalities and have the following form. Let
xti,j = xi,j + tβi,j , where βi,j = 0 if i ∈
/ S or xi,j ∈ {0, 1}, and βi,j 6= 0 else, together these
entries define xt . The boundaries −t1 and t2 are non-zero and finite, because eventually
an entry corresponding to S would exceed 1 or would be less than 0 with t going to plus,
respectively minus infinity. Therefore at these boundary points we still have an fractional apartition that satisfies our selected equalities, but the number of fractional entries decreases
by at least one. We will formalize how the energy behaves when applying this procedure.
Ext (G) = Ex (G) + c1 t + · · · + cr tr ,
where for l ∈ [r] we have
cl =

1 X
kr
r
z∈[q]

X

βu1 ,zπ(1) . . . βul ,zπ(l) xul+1 ,zπ(l+1) . . . xur ,zπ(r) Gz (uπ(1) , . . . , uπ(r) ),

u1 ,...,ul ∈S
ul+1 ,...,ur ∈V \S
π

where the second sum runs over permutations π of [k] that preserves the ordering of the
elements of {1, . . . , l} and {l + 1, . . . , r} at the same time. We deform the entries corresponding to S through t in the direction so that c1 t ≥ 0 until we have eliminated at
least one fractional entry, that is we set t = −t1 , if c < 0, and t = t2 otherwise. Note,
that as xt is a fractional partition, therefore 0 ≤ xP
i,j + tβi,j ≤ 1, which implies that for
tβ
Pi,j ≤ 0 we have
P |tβi,j | ≤ xi,j . On the
P other hand, j tβi,j = 0 for any t and i. Therefore
|tβ
|
=
2
|tβ
|I
≤
2
i,j
i,j {tβi,j ≤0}
j
j
j xi,j = 2 for any i ∈ [k]. This simple fact enables us
to upper bound the absolute value of the terms cl tl .
|cl tl | ≤

X X
(k − q − 1)r−l
|tβu1 ,zπ(1) | . . . |tβul ,zπ(l) |
kGk
∞
kr
r u ,...,u ∈S
z∈[q]

1

π

l

 
(k − q − 1)r−l
r r−l X X
=
q
|tβu1 ,z1 | . . . |tβul ,zl |
kGk
∞
l
kr
z∈[q]l u1 ,...,ul ∈S

l
 
 
X
r r−l 
r r−l
1
1
q
|tβu,j | ≤ l kGk∞
q (2q + 2)l .
≤ l kGk∞
k
l
k
l
u∈S,j∈[q]

It follows that in each step of elimination of a fractional entry of x we have to admit a
decrease of the energy value of at most
r
X
l=2

|cl tl | ≤

1
kGk∞ (3q + 2)r .
2
k
48

There are in total kq entries in x, therefore, since in each step the number of fractional entries
is reduced by at least 1, we can upper bound the number of required steps for reducing the
cardinality of bad nodes to at most q by k(q − 1), and conclude that we admit an overall
energy decrease of at most k1 kGk∞ (q − 1)(3q + 2)r to construct from x a fractional partition
x′ with at most q nodes with fractional entries In the second stage we proceed as follows.
Let B = {u1 , . . . , um } be the set of the remaining bad nodes of x′ , with m ≤ q. For ui ∈ B
we set x′′ui ,j = Ii (j), for the rest of the nodes we set x′′ = x′ , obtaining an integer a-partition
of [k]. Finally, we estimate the cost of this operation. We get that
Ex′′ (G) ≥ Ex′ (G) −

1
kGk∞ |B|k r−1 q r .
r
k

The original fractional a-partition was arbitrary, therefore it follows that
1
Ea (G) − Eˆa (G) ≤ kGk∞ 5r q r+1 .
k

We are ready state the adaptation of Theorem 4.4 adapted to the microcanonical setting.
Theorem 5.4. Let r ≥ 1, q ≥ 1, a ∈ Pdq , and ε > 0. Then for any [q]r -tuple of ([−d, d, r])r+7 r
graphons W = (W z )z∈[q]r and k ≥ Θ4 log(Θ)q r with Θ = 2 ε q r we have


P |Ea (W ) − Êa (G(k, W ))| > εkW k∞ < ε.
r+7 r

Proof. Let W be as in the statement and k ≥ Θ4 log(Θ)q r with Θ = 2 ε q r . We start with
pointing out that we are allowed to replace the quantity Eˆa (G(k, W )) by Ea (G(k, W )) in
the statement of the theorem by Theorem 5.3 and only introduce an initial error at most
1
kGk∞ 5r q r+1 ≤ 2ε kW k∞ .
k
The lower bound on Ea (G(k, W )) is the result of standard sampling argument combined
with Theorem 5.2. Let us consider a fixed a-partition φ of [0, 1], and define the random
fractional partition of [k] as yn,m = φm (Un ) for every n ∈ [k] and m ∈ [q]. The partition y
is not necessarily an fractional a-partition, but it can not be very far from being one. For
m ∈ [q] it holds that
!
Pk
n=1 yn,m
− am ≥ ε ≤ 2 exp(−ε2 k/2),
P
k
therefore for our choice of k the sizes of the partition classes obey | k1
for every m ∈ [q] with probability at least 1 − ε/2.
We appeal to Theorem 5.2 to conclude
EEa (G(k, W )) ≥ EEy (G(k, W )) − (ε/2)kW k∞
49

Pk

n=1 yn,m −am |

<

ε
2(q+1)

r
k
Y
1 X X
ynj ,zj − (ε/2)kW k∞
W (Un1 , . . . , Unr )
=E r
k
r
n
,...,n
=1
j=1
z∈[q] 1
r
 2

Z
r
Y
X
r
k!
W (t1 , . . . , tr )
φzj (tj )dt −
+ ε/2 kW k∞
≥ r
k (k − r)!
k
r
j=1
z∈[q] [0,1]r

≥ Eφ (W ) −




r2
+ ε/2 kW k∞ .
k

The concentration of the random variable Ea (G(k, W )) can be obtained through martingale
arguments identical to the technique used in the proof of the lower bound in Theorem 4.4.
For the upper bound on Ea (G(k, W )) we are going to use the cut decomposition and local
linearization, the approach to approximate the energy of Eφ (W ) and Ex (G(k, W )) for certain
partitions φ, respectively x is completely identical to the proof of Theorem 4.4, therefore we
borrow all the notation from there, and we do not refer to again in what follows.
Now we consider a b ∈ A and define the event E3 (b) that is occurrence the following
implication.
If the linear program
maximize
subject to

q
k X
X
1
l0 +
xn,m lm (Un )
k
n=1 m=1

x ∈ I ′ (b, η) ∩ ωa
0 ≤ xn,m ≤ 1
q
X
xn,m = 1

for n = 1, . . . , k and m = 1, . . . , q
for n = 1, . . . , k

m=1

has optimal value α, then the continuous linear program
maximize

l0 +

Z1 X
q
0

subject to

lm (t)φm (t)dt

m=1



φ ∈ I(b, η) ∩ 

[

c : |ai −ci |≤η

0 ≤ φm (t) ≤ 1
q
X
φm (t) = 1



Ωc 

for t ∈ [0, 1] and m = 1, . . . , q
for t ∈ [0, 1]

m=1

has optimal value at least α − 2ε kW k∞ .
Recall that η = 16qεr 2r . It follows by applying Theorem 4.12 that E3 (b) has probability


kε2
at least 1 − 2 exp − 22r+12 q2r r2 . When conditioning on E1 , the event from the proof of
50

Theorem 4.4, and E3 = ∩b∈A E3 (b) we conclude that
Ea (G(k, W )) ≤

max

c : |ai −ci |≤η

Ec (W )+ε/2)kW k∞ ≤ Ea (W )+(rqη+ε/2)kW k∞ ≤ Ea (W )+εkW k∞.

Also, like in Theorem 4.4, the probability of the required events to happen simultaneously
is at least 1 − ε/2. This concludes the proof.

5.2

Quadratic assignment and maximum acyclic subgraph problem

The two optimization problems that are the subject of this subsection, the quadratic assignment problem (QAP) and maximum acyclic subgraph problem (AC), are known to be
NP-hard, similarly to MAX-rCSP that was investigated above. The first polynomial time
approximation schemes were designed for the QAP by Arora, Frieze and Kaplan [6]. Dealing with a QAP means informally that one aims to minimize the transportation cost of his
enterprise that has n production locations and n types of production facilities. This is to
be achieved by an optimal assignment of the facilities to the locations with respect to the
distances (dependent on the location) and traffic (dependent on the type of the production).
In formal, terms this means that we are given two real quadratic matrices of the same size,
G and J ∈ Rn×n , and the objective is to calculate
n

X
1
Q(G, J) = 2 max
Ji,j Gρ(i),ρ(j) ,
n ρ i,j=1
where ρ runs over all permutations of [n]. We speak of metric QAP, if the entries of J are all
non-negative with zeros on the diagonal, and obey the triangle inequality, and d-dimensional
geometric QAP if the rows and columns of J can be embedded into a d-dimensional Lp
metric space so that distances of the images are equal to the entries of J.
The continuous analog of the problem is the following. Given the measurable functions
W, J : [0, 1]2 → R, we are interested in obtaining
Z
Q̂ρ (W, J) =
J(x, y)W (ρ(x), ρ(y))dxdy,
Q̂(W, J) = max Q̂ρ (W, J),
ρ

[0,1]2

where ρ in the previous formula runs over all measure preserving permutations of [0, 1].
In even greater generality we introduce the QAP with respect to fractional permutations of
[0, 1]. A fractional permutation µ is a probability kernel, that is µ : [0, 1] × L([0, 1]) → [0, 1]
so that
(i) for any A ∈ L([0, 1]) the function µ(., A) is measurable,
(ii) for any x ∈ [0, 1] the function µ(x, .) is a probability measure on L([0, 1]), and
R1
(iii) for any A ∈ L([0, 1]) 0 dµ(x, A) = λ(A).
51

Here L([0, 1]) is the σ-algebra of the Borel sets of [0, 1].
Then we define
Z Z
Qµ (W, J) =
J(α, β)W (x, y)dµ(α, x)dµ(β, y)dαdβ,
[0,1]2 [0,1]2

and
Q(W, J) = max Qµ (W, J),
µ

where the maximum runs over all fractional permutations. For each measure preserving
permutation ρ one can consider the fractional permutation µ with the probability measure
µ(α, .) is defined as the atomic measure δρ(α) concentrated on ρ(α), for this choice of µ we
have Qρ (W, J) = Qµ (W, J).
An r-dimensional generalization of the problem for J and W : [0, 1]r → R is
Z Z
Q(W, J) = max
J(α1 , . . . , αr )W (x1 , . . . , xr )dµ(α1 , x1 ) . . . dµ(αr , xr )dα1 . . . dαr ,
µ

[0,1]r [0,1]r

where the maximum runs over all fractional permutations µ of [0, 1]. The definition of the
finitary case in r dimensions is analogous.
A special QAP is the maximum acyclic subgraph problem (AC). Here we are given a
weighted directed graph G with vertex set of cardinality n, and our aim is to determine the
maximum of the total value of edge weights of a subgraph of G that contains no directed
cycle. We can formalize this as follows. Let G ∈ Rn×n be the input data, then the maximum
acyclic subgraph density is
n

X
1
AC(G) = 2 max
Gi,j I(ρ(i) < ρ(j)),
n ρ i,j=1
where ρ runs over all permutations of [n].
This can be thought of as a QAP with the restriction that J is the upper triangular
n × n matrix with zeros on the diagonal and all nonzero entries being equal to 1. However in
general AC cannot be reformulated as metric QAP. The continuous version of the problem
Z
ˆ
AC(W ) = sup
I(φ(x) > φ(y))W (x, y)dxdy
φ

[0,12 ]

for a function W : [0, 1]2 → R is defined analogous to the QAP, where the supremum runs
over measure preserving permutations φ : [0, 1] → [0, 1], as well as the relaxation AC(W ),
where the supremum runs over probability kernels.
Both the QAP and the AC problems resemble the ground state energy problems that
were investigated in previous parts of this paper. In fact, if the number of clusters of the
distance matrix J in the QAP is bounded from above by an integer that is independent from
52

n, then this special QAP is a ground state energy with the number of states q equal to the
number of clusters of J. By the number of clusters we mean here the smallest number m
such that there exists an m × m matrix J ′ so that J is a blow-up of J ′ , that is not necessarily
equitable. To establish an approximation to the solution of the QAP we will only need the
cluster condition approximately, and this will be shown in what follows.
Definition 5.5. We call a measurable function J : [0, 1]r → R ν-clustered for a non-increasing
function ν : R+ → R+ , if for any ε > 0 there exists another measurable function J ′ : [0, 1]r →
R that is a step function with ν(ε) steps and kJ − J ′ k1 < εkJk∞ .
Note, that by the Weak Regularity Lemma ([16]), ??, any J can be well approximated
1
by a step function with ν(ε) = 2 ε2 steps in the cut norm. To see why it is likely that this
approximation will not be sufficient for our purposes, consider an arbitrary J : [0, 1]r → R.
Suppose that we have an approximation in the cut norm of J at hand denoted by J ′ . Define
the probability kernel µ0 (α, .) = δα and the naive r-kernel W0 = J − J ′ . In this case
|Qµ0 (W, J) − Qµ0 (W, J ′ )| = kJ − J ′ k22 . This 2-norm is not granted to be small compared to
ε by any means.
In some special cases, for example if J is a d-dimensional geometric array or the array
corresponding to the AC, we are able to require bounds on the number of steps required for
the 1-norm approximation of J that are sub-exponential in 1ε . By the aid of this fact we can
achieve good approximation of the optimal value of the QAP via sampling. Next we state
an application of Theorem 4.4 to the clustered QAP.
Lemma 5.6. Let ν : R+ → R+ be nondecreasing, and let J : [0, 1]r → R be a ν-clustered
measurable function. Then there exists an absolute constant c > 0 so that for every ε > 0,
r
r
)( ν(ε)
)4 we have
every naive r-kernel W , and k ≥ c log( ν(ε)
ε
ε
P(|Q(W, J) − Q(G(k, W ), G′ (k, J))| ≥ εkW k∞ kJk∞ ) ≤ ε,
where G(k, W ) and G′ (k, J) are generated by distinct independent samples.
Proof. Without loss of generality we may assume that kJk∞ ≤ 1. First we show that under
the cluster condition we can introduce a microcanonical ground state energy problem whose
optimum is close to Q(W, J), and the same holds for the sampled problem. Let ε > 0 be
arbitrary and J ′ be an approximating step function with q = ν(ε) steps. We may assume
that kJ ′ k∞ ≤ 1. We set a = (a1 , . . . , aq ) to be the vector of the sizes of the steps of J ′ , and
construct from J ′ a real r-array of size q in the natural way by associating to each class of
the steps of J ′ an element of [q] (indexes should respect a), and set the entries of the r-array
corresponding to the value of the respective step of J ′ . We will call the resulting r-array J ′′ .
From the definitions it follows that
Q(W, J ′ ) = Ea (W, J ′′ )
for every r-kernel W . On the other hand we have
|Q(W, J)−Q(W, J ′ )|
53

≤ max |Qµ (W, J) − Qµ (W, J ′ )|
µ

= max
µ

Z

′

(J − J )(α1 , . . . , αr )

[0,1]r

≤ max
µ

Z

[0,1]r

Z

W (x)dµ(α1 , x1 ) . . . dµ(αr , xr )dα1 . . . dαr

[0,1]r

|(J − J ′ )(α1 , . . . , αr )|kW k∞ dα1 . . . dαr

= kJ − J ′ k1 kW k∞ ≤ εkW k∞ .
Now we proceed to the sampled version of the optimization problem. First we gain control
over the difference between the QAPs corresponding to J and J ′ . G(k, W ) is induced by the
sample U1 , . . . , Uk , G′ (k, J) and G′ (k, J ′ ) by the distinct independent sample Y1 , . . . , Yk .
|Q(G(k, W ), G(k, J)) − Q(G(k, W ), G(k, J ′ ))|
≤ max |Qρ (G(k, W ), G(k, J)) − Qρ (G(k, W ), G(k, J ′ ))|
ρ

1
= max r
ρ k

k
X

(J − J ′ )(Yi1 , . . . , Yir ) kW k∞ .

(5.1)

i1 ,...,ir =1

We analyze the random sum on the right hand side of (5.1) by first upper bounding its
expectation.
k
X

1
EY
kr

(J − J ′ )(Yi1 , . . . , Yir )

i1 ,...,ir =1
2

r
[kJk∞ + kJ ′ k∞ ] + EY |(J − J ′ )(Y1 , . . . , Yr )|
k
2r 2
=
+ ε ≤ 2ε.
k

≤

By the Azuma-Hoeffding inequality the sum is also sufficiently small in probability.
!
k
X
1
(J − J ′ )(Yi1 , . . . , Yir ) ≥ 4ε ≤ 2 exp(−ε2 k/8) ≤ ε.
P
k r i ,...,i =1
1

r

We obtain that
|Q(G(k, W ), G′ (k, J)) − Q(G(k, W ), G′ (k, J ′ ))| ≤ 4εkW k∞
with probability at least 1 − ε, if k is such as in the statement
P of the lemma. Set b =
(b1 , . . . , bq ) to be the probability distribution for that bi = k1 kj=1 ISi (Yj ), where Si is the
ith step of J ′ with λ(Si ) = ai . Then we have
Q(G(k, W ), G(k, J ′ )) = Êb (G(k, W ), J ′′ ).
54

It follows again from the Azuma-Hoeffding inequality that we have P(|ai − bi | > ε/q) ≤
2
2 exp(− ε2qk2 ) for each i ∈ [q], thus we have ka − bk1 < ε with probability at least 1 − ε. We
can conclude that with probability at least 1 − 2ε we have
|Q(W, J) − Q(G(k, W ), G(k, J))| ≤ |Q(W, J) − Q(W, J ′ )|

+ |Ea (W, J ′′ ) − Êb (G(k, W ), J ′′ )| + |Q(G(k, W ), G(k, J)) − Q(G(k, W ), G(k, J ′ ))|
≤ (5 + 2r)εkW k∞ + |Ea (W, J ′′ ) − Êa (G(k, W ), J ′′ )|.

By the application of Theorem 5.4 the claim of the lemma is verified.
Next we present the application of Theorem 5.6 for two special cases of QAP.
Corollary 5.7. The optimal values of the d-dimensional geometric QAP and the maximum
acyclic subgraph problem are efficiently testable. That is, let d ≥ 1, for every ε > 0 there
exists an integer k0 = k0 (ε) such that k0 is a polynomial in 1/ε, and for every k ≥ k0 and
any d-dimensional geometric QAP given by the pair (G, J) we have
P(|Q(G, J) − Q(G(k, G), G′ (k, J))| ≥ εkGk∞ kJk∞ ) ≤ ε,

(5.2)

where G(k, W ) and G′ (k, J) are generated by distinct independent samples. The formulation
regarding the testability of the maximum acyclic subgraph problem is analogous.
Note that testability here is meant in the sense of the statement of Theorem 5.6, since
the size of J is not fixed and depends on G.
Proof. In the light of Theorem 5.6 it suffices to show that for both cases any feasible J is
ν-clustered, where ν(ε) is polynomial in 1/ε. For both settings we have r = 2.
We start with the continuous version of the d-dimensional geometric QAP given by the
measurable function J : [0, 1]2 → R+ , and an instance is given by the pair (W, J), where W
is a 2-kernel. Note, that d refers to the dimension corresponding to the embedding of the
indices of J into an Lp metric space, not the actual dimension of J. We are free to assume
that 0 ≤ J ≤ 1, simply by rescaling. By definition, there exists a measurable embedding
ρ : [0, 1] → [0, 1]d , so that J(i, j) = kρ(i) − ρ(j)kp for every (i, j) ∈ [0, 1]2 . Fix ε > 0 and
, 1]) of the unit interval into
consider the partition P ′ = (T1 , . . . , Tβ ) = ([0, β1 ), [ β1 , β2 ), . . . , [ β−1
β
√
p

β = ⌈ 2 ε d ⌉ classes. Define the partition P = (P1 , . . . , Pq ) of [0, 1] consisting of the classes
d d/p
ρ−1 (Ti1 × · · · × Tid ) for each (i1 , . . . , id ) ∈ [β]r , where |P| = q = β d = 2 εdd . We construct
the approximating step function J ′ of J by averaging J on the steps determined by the
partition classes of P. It remains to show that this indeed is a sufficient approximation in
the L1 -norm.
Z
Z
q
q
X
X
1
′
′
kJ − J k1 =
|J(x) − J ′ (x)|dx ≤
|J(x) − J (x)|dx =
ε = ε.
2
q
i,j
i,j=1
Pi ×Pj

[0,1]2

55

By Theorem 5.6 and Theorem 5.4 it follows that the continuous d-dimensional metric QAP
1
is O(log( 1ε ) ε4rd+4
)-testable, and so is the discrete version of it.
Next we show that the AC is also efficiently testable given by the upper triangular matrix
J whose entries above the diagonal are 1. Note that here we have r = 2. Fix ε > 0 and
consider the partition P = (P1 , . . . , Pq ) with q = 1ε , and set J ′ to 0 on every step Pi × Pj
whenever i ≥ j, and to 1 otherwise. This function is indeed approximating J in the L1 -norm.
Z
Z
q
X
′
′
|J(x) − J ′ (x)|dx ≤ ε.
kJ − J k1 =
|J(x) − J (x)|dx =
i=1 P ×P
i
i

[0,1]2

Again, by Theorem 5.6 and Theorem 5.4 it follows that the AC is O(log( 1ε ) ε112 )-testable.

6

Further Research

Our framework based on exchangeability principles allows us to extend the notion of a limit
to the case of unbounded hypergraphs and efficient testability of ground state energies in
this setting. The notion of exchangeability is crucial here. The notion of efficient testability
in an unbounded case could be of independent interest, perhaps the results on ground state
energy carry through for the setting when the r-graphons (induced by r-graphs) are in an
Lp space for some p ≥ 1.
Another problem is to characterize more precisely the class of problems which are efficiently parameter testable as opposed to the hard ones. Improving the bounds in 1/ε for the
efficiently testable problems is also a worthwhile question.

Acknowledgement
We thank Jennifer Chayes, Christian Borgs and Tim Austin for a number of interesting and
stimulating discussions and the relevant new ideas in the early stages of this research.

References
[1] David J. Aldous. Representations for partially exchangeable arrays of random variables.
J. Multivariate Anal., 11(4):581–598, 1981.
[2] Noga Alon and Asaf Shapira. A characterization of the (natural) graph properties
testable with one-sided error. SIAM J. Comput., 37(6):1703–1727, 2008.
[3] Noga Alon and Joel H. Spencer. The probabilistic method. Wiley-Interscience Series in
Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, third
edition, 2008. With an appendix on the life and work of Paul Erdős.
56

[4] Noga Alon, W. Fernandez de la Vega, Ravi Kannan, and Marek Karpinski. Random
sampling and approximation of MAX-CSP problems. In Proceedings of the ThirtyFourth Annual ACM Symposium on Theory of Computing, pages 232–239, 2002. Also
appeared in J. Comput. System Sci., 67(2):212–243,2003.
[5] Sanjeev Arora, David R. Karger, and Marek Karpinski. Polynomial time approximation
schemes for dense instances of NP-hard problems. In Proceedings of the Twenty-Seventh
Annual ACM Symposium on Theory of Computing, pages 284–293, 1995. Also appeared
in J. Comput. System Sci., 58(1):193–210, 1999.
[6] Sanjeev Arora, Alan Frieze, and Haim Kaplan. A new rounding procedure for the
assignment problem with applications to dense graph arrangement problems. Math.
Program., 92(1, Ser. A):1–36, 2002.
[7] Ashwini
Aroskar.
Limits,
Regularity
and
Removal
for
tional and Weighted Structures.
dissertation, CMU, 2012.
http://repository.cmu.edu/dissertations/144.

RelaURL

[8] Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and Yadu Vasudev. Approximate graph isomorphism. In Mathematical foundations of computer science 2012, volume 7464 of Lecture Notes in Comput. Sci., pages 100–111. Springer, Heidelberg, 2012.
[9] Tim Austin. On exchangeable random variables and the statistics of large graphs and
hypergraphs. Probab. Surv., 5:80–145, 2008.
[10] C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi. Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing. Adv.
Math., 219(6):1801–1851, 2008.
[11] C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi. Convergent sequences of dense graphs II. Multiway cuts and statistical physics. Ann. of Math. (2),
176(1):151–219, 2012.
[12] B. de Finetti. Funzione Caratteristica Di un Fenomeno Aleatorio, pages 251–299. 6.
Memorie. Academia Nazionale del Linceo, 1931.
[13] Wenceslas Fernandez de la Vega, Ravi Kannan, and Marek Karpinski. Approximation
of global max-csp problems. 2006. Technical Report TR06-124.
[14] Persi Diaconis and Svante Janson. Graph limits and exchangeable random graphs.
Rend. Mat. Appl. (7), 28(1):33–61, 2008.
[15] Gábor Elek and Balázs Szegedy. A measure-theoretic approach to the theory of dense
hypergraphs. Adv. Math., 231(3-4):1731–1772, 2012.
[16] Alan M. Frieze and Ravi Kannan. Quick approximation to matrices and applications.
Combinatorica, 19(2):175–220, 1999.
57

[17] Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection
to learning and approximation. J. ACM, 45(4):653–750, 1998.
[18] Edwin Hewitt and Leonard J. Savage. Symmetric measures on Cartesian products.
Trans. Amer. Math. Soc., 80:470–501, 1955.
[19] D. N. Hoover. Relations on probability spaces and arrays of random variables (preprint),
1979.
[20] Svante Janson. Poset limits and exchangeable random posets. Combinatorica, 31(5):
529–563, 2011.
[21] Olav Kallenberg. Symmetries on random arrays and set-indexed processes. J. Theoret.
Probab., 5(4):727–765, 1992.
[22] Michael Langberg, Yuval Rabani, and Chaitanya Swamy. Approximation algorithms for
graph homomorphism problems. In Approximation, randomization and combinatorial
optimization, volume 4110 of Lecture Notes in Comput. Sci., pages 176–187. Springer,
Berlin, 2006.
[23] László Lovász. Large networks and graph limits, volume 60 of American Mathematical
Society Colloquium Publications. American Mathematical Society, Providence, RI, 2012.
[24] László Lovász and Balázs Szegedy. Limits of dense graph sequences. J. Combin. Theory
Ser. B, 96(6):933–957, 2006.
[25] László Lovász and Balázs Szegedy. Limits of compact decorated graphs, 2010. preprint,
arXiv:1010.5155.
[26] László Lovász and Balázs Szegedy. Testing properties of graphs and functions. Israel
J. Math., 178:113–156, 2010.
[27] Claire Mathieu and Warren Schudy. Yet another algorithm for dense max cut: go
greedy. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete
Algorithms, pages 176–182. ACM, New York, 2008.
[28] Igal Sason. On refined versions of the azuma-hoeffding inequality with applications in
information theory, 2011. preprint, arXiv:1111.1977.
[29] Ya. G. Sinaı̆. Theory of phase transitions: rigorous results, volume 108 of International
Series in Natural Philosophy. Pergamon Press, Oxford-Elmsford, N.Y., 1982. Translated
from the Russian by J. Fritz, A. Krámli, P. Major and D. Szász.
[30] Yufei Zhao. Hypergraph limits: a regularity approach, 2013. preprint, arXiv:1302.1634.

58

