# A Weighted Regularity Lemma with Applications

Authors: Béla Csaba; András Pluhár
Journal: International Journal of Combinatorics
 (2014)

---

## Abstract

We prove an extension of the regularity lemma with vertex and edge weights which in principle can be applied for arbitrary graphs. The applications involve random graphs and a weighted version of the Erdős-Stone theorem. We also provide means to handle the otherwise uncontrolled exceptional set.


---

## Body

## 1. Introduction

LetG
=
G
(
A
,
B
) be a bipartite graph. For X
,
Y
⊂
A
∪
B let e
G
(
X
,
Y
) denote the number of edges with one endpoint in X and the other in Y. Given an ε
>
0 we say that the (
A
,
B
)-pair is ε-regular if
(1)
|
e
G
(
A
′
,
B
′
)
|
A
′
|
|
B
′
|
-
e
G
(
A
,
B
)
|
A
|
|
B
|
|
<
ε
for every A
⊂
A, |
A
′
|
>
ε
|
A
| and B
′
⊂
B, |
B
′
|
>
ε
|
B
|.This definition plays a crucial role in the celebrated Regularity Lemma of Szemerédi; see [1, 2]. The regularity lemma is a very powerful tool when applied to a dense graph. It has found lots of applications in several areas of mathematics and computer science; for applications in graph theory see for example, [3]. However, it does not tell us anything useful when applied for a sparse graph (i.e., a graph on n vertices having o
(
n
2
) edges).There has been significant interest to find widely applicable versions for sparse graphs. This turns out to be a very hard task. Kohayakawa [4] proved a sparse regularity lemma, and with Kohayakawa et al. [5] they applied it for finding arithmetic progressions of length 3 in dense subsets of a random set. In their sparse regularity lemma dense graphs are substituted by dense subgraphs of a random (or quasirandom) graph. Naturally, a new definition of ε-regularity was needed; below we formulate a slightly different version from theirs.LetF
(
A
,
B
) and G
(
A
,
B
) be two bipartite graphs such that F
⊂
G. We say that the (
A
,
B
)-pair is ε-regular in F relative to G if
(2)
|
e
F
(
A
′
,
B
′
)
e
G
(
A
′
,
B
′
)
-
e
F
(
A
,
B
)
e
G
(
A
,
B
)
|
<
ε
for every A
′
⊂
A, B
′
⊂
B and |
A
′
|
>
ε
|
A
|, |
B
′
|
>
ε
|
B
|. It is easy to see that the above is a generalization of ε-regularity; in the original definition the role of G is played by the complete bipartite graph K
A
,
B. In this more general definition F can be a rather sparse graph; it only has to be denserelative to
G; that is, e
(
F
)
/
e
(
G
) should be a constant.In this paper we further generalize the notion of quasirandomness andε-regularity by introducingweighted regularity using vertex and edge weights. This enables us to prove a more general and perhaps more applicable regularity lemma. Let us remark that another notion of regularity is used by Alon et al. [6]; later we will discuss how their work relates to ours. A recent approach by Scott [7] defines regularity of matrices and deduces a regularity lemma for graphs via their adjacency matrices. This approach turns out to be less flexible than the one we choose in the present paper (for earlier versions, see [8]).The basic tool is the Strong Structure Theorem of Tao [9], where he simplifies the proof of the original regularity lemma itself and gives new insights, too. Following his lines became technically feasible to extend regularity to the case when both the edges and the vertices of a graph are weighted (note that the measures are in close connection with each other.) We remark that similar ideas might be used to find a regularity lemma for sparse hypergraphs as well.The structure of the paper is as follows. First we discuss weighted quasirandomness and weightedε-regularity in the second section. In the third section we prove the new version of the regularity lemma. Finally, we show some applications in the fourth section; in particular, we prove a weighted version of the Erdős-Stone theorem.


## 2. Basic Definitions and Tools

Throughout the paper we apply the relation “≪”: a
≪
b if a is sufficiently smaller than b. This notation is widely applied in papers using the regularity lemma and simplifies our notation, too.Letβ
>
0 and G
=
(
V
,
E
) be a graph on n vertices. Set δ
G
=
e
(
G
)
/
(
n
2
); this is thedensity of G. We define the density of the A, B pair of subsets of V
(
G
) by δ
G
(
A
,
B
)
=
e
G
(
A
,
B
)
/
(
|
A
|
|
B
|
). We say that G is β-quasi-random if it has the following property: If A
,
B
⊂
V
(
G
) such that A
∩
B
=
∅ and |
A
|
,
|
B
|
>
β
n then
(3)
|
δ
G
-
δ
G
(
A
,
B
)
|
<
β
δ
G
.
That is, the edges of G are distributed “randomly.” In order to formulate our regularity lemma we have to define quasirandomness in a more general way that admits weights on vertices and edges.For a functionw
:
S
→
R
+ and A
⊂
S, w
(
A
) is defined by the usual way; that is, w
(
A
)
=
∑
x
∈
A
‍
w
(
x
). We will also use the indicator function of the edge set of a graph H
.
1
H: (
V
(
H
)
2
)
→
{
0,1
} and 1
H
(
x
,
y
)
=
1 if  x
y
∈
E
(
H
).We define the weighted quasirandomness of a graphG
=
(
V
,
E
) with given weight-functions μ
:
V
→
R
+ and ρ
:
(
V
2
)
→
R
+. For A
,
B
⊂
V let
(4)
ρ
G
(
A
,
B
)
:
=
∑
u
∈
A
,
v
∈
B
‍
1
G
(
u
,
v
)
ρ
(
u
,
v
)
.
In particular, ρ
G
(
u
,
v
)
=
1
G
(
u
,
v
)
ρ
(
u
,
v
) for u
,
v
∈
V. Observe that the function μ is an analogon of the vertex counting function on a set, while the function ρ counts the edges in the unweighted case.Definition 1.
A graphG
=
(
V
,
E
) is weighted β-quasi-random with weight-function μ and ρ if for any A
,
B
⊂
V
(
G
) such that A
∩
B
=
∅ and μ
(
A
)
≥
β
μ
(
V
), μ
(
B
)
≥
β
μ
(
V
) one has
(5)
|
ρ
G
(
A
,
B
)
μ
(
A
)
μ
(
B
)
-
ρ
G
(
V
,
V
)
μ
(
V
)
μ
(
V
)
|
<
β
.Observe that choosingμ
≡
1 and ρ
≡
1
/
δ
G gives back the first definition of quasirandomness. The notion of quasirandomness readily extends to bipartite (or multipartite) graphs. In that case the sets A and B are chosen from different classes. There is another weaker notion of quasirandomness, which we will also use.Definition 2.
LetK
>
1 be an absolute constant. A graph G
=
(
V
,
E
) is weighted (
K
,
β
)-quasi-random with weight-functions μ and ρ if for any A
,
B
⊂
V
(
G
) such that A
∩
B
=
∅ and μ
(
A
)
≥
β
μ
(
V
), μ
(
B
)
≥
β
μ
(
V
) one has
(6)
1
K
ρ
G
(
V
,
V
)
μ
(
V
)
μ
(
V
)
≤
ρ
G
(
A
,
B
)
μ
(
A
)
μ
(
B
)
≤
K
ρ
G
(
V
,
V
)
μ
(
V
)
μ
(
V
)
.Clearly, if a graph isβ-quasi-random and K
>
max
⁡
{
1
+
β
/
y
,
1
+
β
/
(
y
-
β
)
}, then it is (
K
,
β
)-quasi-random, where y
:
=
ρ
G
(
V
,
V
)
/
μ
(
V
)
2. Now we need to describe the weighted version of relative regularity.Definition 3.
LetG and F be graphs, F
⊂
G, and assume that G is a (
K
,
β
)-quasi-random with weight functions μ and ρ as defined above. For A
,
B
⊂
V
(
G
) and A
∩
B
=
∅ the pair (
A
,
B
) in F is (
μ
,
ρ
)-weighted ϵ-regular relative to G, or briefly weighted ϵ-regular, if
(7)
|
ρ
F
(
A
′
,
B
′
)
μ
(
A
′
)
μ
(
B
′
)
-
ρ
F
(
A
,
B
)
μ
(
A
)
μ
(
B
)
|
<
ϵ
for every A
′
⊂
A and B
′
⊂
B provided that μ
(
A
′
)
≥
ϵ
μ
(
A
), μ
(
B
′
)
≥
ϵ
μ
(
B
). Here
(8)
ρ
F
(
A
,
B
)
=
∑
u
∈
A
,
v
∈
B
‍
1
F
(
u
,
v
)
ρ
(
u
,
v
)
.Remarks. Note that weighted ϵ-regularity is nothing but the well-known ϵ-regularity when G
=
K
A
,
B and μ
≡
1 and ρ is chosen to be identically the reciprocal of the density of G as before. Since 1
F
(
u
,
v
)
≤
1
G
(
u
,
v
)
≤
1
(
u
,
v
) we also have ρ
F
(
A
,
B
)
≤
ρ
G
(
A
,
B
)
≤
ρ
(
A
,
B
). Hence, the first inequality of the definition does not refer to G explicitly but contains information on it.Next we define weighted regular partitions.Definition 4.
LetG
=
(
V
,
E
) and F
⊂
G be graphs, and μ and ρ weight functions. F has a weighted ϵ-regular partition relative to G if its vertex set V can be partitioned into l
+
1 clusters W
0
,
W
1
,
…
,
W
l such that(i)
μ
(
W
0
)
≤
ϵ
μ
(
V
),
(ii)
|
μ
(
W
i
)
-
μ
(
W
j
)
|
≤
max
⁡
x
∈
V
{
μ
(
x
)
} for every 1
≤
i, j
≤
l,
(iii)
all but at mostϵ
l
2 of the pairs (
W
i
,
W
j
) for 1
≤
i
<
j
≤
l are weighted ϵ-regular in F relative to G.In order to show our main result we will use the Strong Structure Theorem of Tao that allows a short exposition. In fact we will closely follow his proof for the regularity lemma as discussed in [9].First we have to introduce some definitions. LetH be a real finite-dimensional Hilbert space, and let S be a set of basic functions or basic structured vectors of H of norm at most 1. The function g
∈
H is (
M
,
K
)-structured with the positive integers M, K if one has a decomposition
(9)
g
=
∑
1
≤
i
≤
M
‍
c
i
s
i
with s
i
∈
S and c
i
∈
[
-
K
,
K
] for 1
≤
i
≤
M. We say that g is β-pseudorandom for some β
>
0 if |
〈
g
,
s
〉
|
≤
β for all s
∈
S. Then we have the following.Theorem 5 (Strong Structure Theorem—T. Tao).
LetH and S be as above, let ε
>
0, and let J
:
Z
+
→
R
+ be an arbitrary function. Let f
∈
H be such that ∥
f
∥
H
≤
1. Then we can find an integer M
=
M
J
,
ε and a decomposition f
=
f
str
+
f
psd
+
f
err
⁡ where (i) f
str is (
M
,
M
)-structured, (ii) f
psd is 1
/
J
(
M
)-pseudorandom, and (iii) ∥
f
err
⁡
∥
H
≤
ε.Note that the proof of Theorem5 yields a polynomial algorithm; hence, our regularity lemma has the same complexity.


## 3. Weighted Regularity Lemma Relative to a Quasirandom GraphG

First we define the Hilbert spaceH, and S. We generalize Example 2.3 of [9] to weighted graphs. Let G
=
(
V
,
E
) be a β-quasi-random graph on n vertices with weight functions μ and ρ. Let H be the (
n
2
)-dimensional space of functions g
:
(
V
2
)
→
R, endowed with the inner product
(10)
〈
g
,
h
〉
=
1
(
n
2
)
∑
(
u
,
v
)
∈
(
V
2
)
‍
g
(
u
,
v
)
h
(
u
,
v
)
ρ
G
(
u
,
v
)
.It is useful to normalize the vertex and edge weight functions; we assume thatμ
(
V
)
=
n and 〈
1,1
〉
=
1. We also assume that μ
(
v
)
=
o
(
|
V
|
) for every v
∈
V. Observe that if F
⊂
G then ∥
1
F
∥
≤
1. We let S be the collection of 0,1-valued functions γ
A
,
B for A
,
B
⊂
V
(
G
), A
∩
B
=
∅, where γ
A
,
B
(
u
,
v
)
=
1 if and only if u
∈
A and v
∈
B. We have the following.Theorem 6 (weighted regularity lemma).
LetK
>
1 and β
,
ε
∈
(
0,1
), such that 0
<
β
≪
ε
≪
1
/
K, and let L
≥
1. If G
=
(
V
,
E
) is a weighted (
K
,
β
)-quasi-random graph on n vertices with n sufficiently large depending on ε and L, F
⊂
G, then F admits a weighted ε-regular partition relative to G into the partition sets W
0
,
W
1
,
…
,
W
l such that L
≤
l
≤
C
ε
,
L for some constant C
ε
,
L.Proof.
Let us apply Theorem5 to the function 1
F with parameters η and function J to be chosen later. We get the decomposition
(11)
1
F
=
f
str
+
f
psd
+
f
err
⁡
,
where f
str is (
M
,
M
)-structured, f
psd is 1
/
J
(
M
)-pseudorandom, and ∥
f
err
⁡
∥
≤
η with M
=
M
J
,
η
=
M
J
,
ε.
The functionf
str is the combination of at most M basic functions:
(12)
f
str
=
∑
1
≤
k
≤
M
‍
α
k
γ
A
k
,
B
k
,
where A
k
,
B
k are subsets of V and γ
A
k
,
B
k agrees with the indicator function of the edges of G in between A
k and B
k. Any (
A
k
,
B
k
) pair partitions V into at most 4 subsets. Overall we get a partitioning of V into at most 4
M subsets; we will refer to them asatoms. Divide every atom into subsets of total vertex weight ε
n
/
(
L
+
4
M
), except possibly one smaller subset. The small subsets will be put into W
0; the others give W
1
,
W
2
,
…
,
W
l, with l
=
(
L
+
4
M
)
/
ε. We refer to the sets W
i for i
=
1
,
…
,
l asclusters. If n is sufficiently large then this partitioning is nontrivial. From the construction it follows that each W
i is entirely contained within an atom. It is also clear that μ
(
W
0
)
≤
ε
n and μ
(
W
i
)
≈
m
=
Θ
(
n
/
l
) for every 1
≤
i
≤
l.
We have that(13)
∥
f
err
⁡
∥
2
=
1
(
n
2
)
∑
(
u
,
v
)
∈
(
V
2
)
‍
|
f
err
⁡
(
u
,
v
)
|
2
ρ
G
(
u
,
v
)
≤
η
2
.
From this and the normalization of ρ it follows that
(14)
1
(
l
2
)
∑
1
≤
i
<
j
≤
l
‍
1
ρ
G
(
W
i
,
W
j
)
∑
u
∈
W
i
,
v
∈
W
j
‍
|
f
err
⁡
(
u
,
v
)
|
2
ρ
G
(
u
,
v
)
=
O
(
η
2
)
.
Clearly,
(15)
1
ρ
G
(
W
i
,
W
j
)
∑
u
∈
W
i
,
v
∈
W
j
‍
|
f
err
⁡
(
u
,
v
)
|
2
ρ
G
(
u
,
v
)
=
O
(
η
)
for all but at most O
(
η
l
2
) pairs (
i
,
j
). If the above is satisfied for a pair (
i
,
j
) then we call it agood pair. We will apply the Cauchy-Schwarz inequality. For that let a
(
u
,
v
)
=
|
f
err
⁡
(
u
,
v
)
|
ρ
G
(
u
,
v
) and b
(
u
,
v
)
=
ρ
G
(
u
,
v
); then
(16)
∑
u
∈
W
i
,
v
∈
W
j
‍
a
(
u
,
v
)
b
(
u
,
v
)
∑
u
∈
W
i
,
v
∈
W
j
‍
b
2
(
u
,
v
)
≤
∑
u
∈
W
i
,
v
∈
W
j
‍
a
2
(
u
,
v
)
.
Since
(17)
∑
u
∈
W
i
,
v
∈
W
j
‍
a
2
(
u
,
v
)
=
O
(
η
)
ρ
G
(
W
i
,
W
j
)
,
we get that
(18)
1
ρ
G
(
W
i
,
W
j
)
∑
u
∈
W
i
,
v
∈
W
j
‍
|
f
err
⁡
(
u
,
v
)
|
ρ
G
(
u
,
v
)
=
O
(
η
)
if (
i
,
j
) is a good pair.
Assume that(
i
,
j
) is a good pair. From the pseudorandomness of f
psd we have that
(19)
|
〈
f
psd
,
γ
A
,
B
〉
|
=
1
(
n
2
)
|
∑
u
∈
A
,
v
∈
B
‍
f
psd
(
u
,
v
)
ρ
G
(
u
,
v
)
|
≤
1
J
(
M
)
for every A
⊂
W
i and B
⊂
W
j.
We will show that every good pair is weightedε-regular in F relative to G. Let (
i
,
j
) be a good pair, and assume that A
⊂
W
i, μ
(
A
)
>
ε
μ
(
W
i
) and B
⊂
W
j, μ
(
B
)
>
ε
μ
(
W
j
). To show that (
W
i
,
W
j
) is weighted ε-regular, it is sufficient to show that
(20)
|
ρ
F
(
A
,
B
)
μ
(
A
)
μ
(
B
)
-
ρ
F
(
W
i
,
W
j
)
μ
(
W
i
)
μ
(
W
j
)
|
<
ε
.
Recall that
(21)
ρ
F
(
A
,
B
)
=
∑
u
∈
A
,
v
∈
B
‍
1
F
(
u
,
v
)
ρ
(
u
,
v
)
=
∑
u
∈
A
,
v
∈
B
‍
1
F
(
u
,
v
)
ρ
G
(
u
,
v
)
,
since F
⊂
G.
Substitutingf
str
+
f
psd
+
f
err
⁡ for 1
F it is sufficient to verify the following inequalities:
(22)
|
∑
u
∈
A
,
v
∈
B
‍
f
str
(
u
,
v
)
ρ
G
(
u
,
v
)
μ
(
A
)
μ
(
B
)

-

∑
u
∈
W
i
,
v
∈
W
j
‍
f
str
(
u
,
v
)
ρ
G
(
u
,
v
)
μ
(
W
i
)
μ
(
W
j
)
|

<
ε
/
3
,
(23)
|
∑
u
∈
A
,
v
∈
B
‍
f
psd
(
u
,
v
)
ρ
G
(
u
,
v
)
μ
(
A
)
μ
(
B
)

-

∑
u
∈
W
i
,
v
∈
W
j
‍
f
psd
(
u
,
v
)
ρ
G
(
u
,
v
)
μ
(
W
i
)
μ
(
W
j
)
|

<
ε
/
3
,
(24)
|
∑
u
∈
A
,
v
∈
B
‍
f
err
⁡
(
u
,
v
)
ρ
G
(
u
,
v
)
μ
(
A
)
μ
(
B
)

-

∑
u
∈
W
i
,
v
∈
W
j
‍
f
err
⁡
(
u
,
v
)
ρ
G
(
u
,
v
)
μ
(
W
i
)
μ
(
W
j
)
|

<
ε
/
3
.
For proving (22) recall that f
str is constant on W
i
×
W
j and (
M
,
M
)-structured. Since the γ
X
,
Y basic functions are 0,1-valued, we get that |
f
str
|
≤
M
2. Moreover, G is (
K
,
β
)-quasi-random, where 0
<
β
≪
ε. Therefore, (22) follows from the inequality K
M
2
β
<
ε
/
3, since β
≪
ϵ.
The proof of (23) goes as follows. The first term is
(25)
|
∑
u
∈
A
,
v
∈
B
‍
f
psd
(
u
,
v
)
ρ
G
(
u
,
v
)
μ
(
A
)
μ
(
B
)
|
=
(
n
2
)
|
〈
f
psd
,
γ
A
,
B
〉
|
≤
(
n
2
)
J
(
M
)
μ
(
A
)
μ
(
B
)
,
and the second is
(26)
|
∑
u
∈
W
i
,
v
∈
W
j
‍
f
psd
(
u
,
v
)
ρ
G
(
u
,
v
)
μ
(
W
i
)
μ
(
W
j
)
|
=
(
n
2
)
|
〈
f
psd
,
γ
W
i
,
W
j
〉
|
≤
(
n
2
)
J
(
M
)
μ
(
W
i
)
μ
(
W
j
)
.
Noting that μ
(
W
k
)
=
Θ
(
n
/
l
) for k
≥
1 we get that the sum of the above terms is at most
(27)
l
2
2
J
(
M
)
(
1
+
1
ε
2
)
<
ε
3
,
if J
(
M
)
≫
l
2
/
ε
3.
For (24) first notice that it is upper bounded by
(28)
O
(
η
)
(
ρ
G
(
W
i
,
W
j
)
μ
(
W
i
)
μ
(
W
j
)
+
ρ
G
(
W
i
,
W
j
)
μ
(
A
)
μ
(
B
)
)
≤
O
(
η
)
ρ
G
(
W
i
,
W
j
)
ε
2
μ
(
W
i
)
μ
(
W
j
)
.
We also have that
(29)
ρ
G
(
W
i
,
W
j
)
μ
(
W
i
)
μ
(
W
j
)
=
O
(
1
)
by the normalization of μ and ρ and from the fact that G is quasirandom. From this it is easy to see that if η
≪
ε
6 then (24) is at most ε
/
3. This finishes the proof of the theorem.


## 4. Quasirandom Weightings and Applications

In this section we first prove that a random graph with widely differing edge probabilities is quasirandom, if none of the edge probabilities are too small. In this case the vertex weights will all be one, but edges will have different weights. Then we show examples where vertices have different weights. We will consider the relation of weighted regularity and volume regularity. We define the “natural weighting” ofK
n and prove a weighted version of the Erdős-Stone theorem for this weighting. Finally, we show how to partially control the nonexceptional set by natural weightings.


### 4.1. Quasirandomness in theG
(
n
,
p
i
j
) Model

In this section we will prove that random graphs of theG
(
n
,
p
i
j
) model are quasirandom in the strong sense with high probability. A special case of this model is the well-known G
(
n
,
p
) model for random graphs. A regularity lemma for this case was first applied by Kohayakawa et al. [5]. They studied G
(
n
,
p
) for p
=
c
/
n in order to find arithmetic progressions of length three in dense subsets of random subsets of [
N
].TheG
(
n
,
p
i
j
) model was first considered by Bollobás [10]. Recently it was also studied by Chung and Lu [11]. In this model one takes n vertices and draws an edge between the vertices x
i and x
j with probability p
i
j, randomly and independently of each other. Note that if p
i
j
≡
p, then we get back the well-known G
(
n
,
p
) model. It is a straightforward application of the Chernoff bound that a random graph G
∈
G
(
n
,
p
) is quasirandom with high probability if p
≫
1
/
n. However, the case of G
(
n
,
p
i
,
j
) is somewhat harder.Lemma 7.
Letβ
>
0. There exists a K
=
K
(
β
) such that if G
∈
G
(
n
,
p
i
j
) and p
i
j
≥
K
/
n for every i and j, then G is weighted β-quasi-random with probability at least 1
-
2
-
n if n is sufficiently large.Proof.
First of all letμ
≡
1, and let ρ
(
i
,
j
)
=
1
/
p
i
,
j. Set K
=
4800
/
β
6. Let p
0
=
K
/
n, and let p
k
=
e
k
p
0 for 1
≤
k
≤
log
⁡
⁡
n. Let A and B be a pair of disjoint sets, both of size at least β
n. We partition the pairs (
u
,
v
), where u
∈
A and v
∈
B, into O
(
log
⁡
⁡
n
) disjoint sets H
1
,
H
2
,
…
,
H
l: if p
k
≤
p
u
v
<
p
k
+
1 then (
u
,
v
) will belong to H
k. Let a
k
=
(
β
3
/
10
)
e
k
K
n. We will denote |
H
k
| by m
k.
We will prove that the following inequality holds with probability at least1
-
2
-
3
n:
(30)
|
∑
u
∈
A
,
v
∈
B
‍
X
u
v
p
u
v
|
A
|
|
B
|
-
1
|
<
β
/
2
,
where X
u
v is a random variable which is 1 if u
v
∈
E
(
G
); otherwise it is 0. This implies the quasirandomness of G since there are less than 2
2
n pairs of disjoint subsets of V
(
G
). Observe that
(31)
∑
u
∈
A
,
v
∈
B
‍
E
X
u
v
p
u
v
|
A
|
|
B
|
=
1
.
Applying the large deviation inequalitiesA
.
1.11 and A
.
1.13 from [12], we are able to bound the number of edges in between A and B for the edges of H
k in case m
k is sufficiently large as follows. According to A
.
1.11 we have that
(32)
Pr
(
∑
(
u
,
v
)
∈
H
k
‍
(
X
u
v
-
E
X
u
v
)
>
a
k
)
<
e
-
(
a
k
2
/
2
q
k
m
k
)
+
(
a
k
3
/
2
q
k
2
m
k
2
)
,
where
(33)
p
k
≤
q
k
=
∑
(
u
,
v
)
∈
H
k
‍
p
u
v
m
k
<
p
k
+
1
.
We estimate the exponent in case m
k
=
n
2:
(34)
-
a
k
2
2
q
k
m
k
+
a
k
3
2
q
k
2
m
k
2
≤
-
β
6
200
(
e
2
e
)
k
K
n
3
e
m
k
+
β
9
2000
(
e
3
e
2
)
k
e
K
n
5
m
k
2
<
-
3
n
,
where we used the definition of K. For m
k being much less than n
2, direct substitution gives a useless bound. For this case we have the useful inequality
(35)
1
2
Pr
(
∑
i
=
1
m
k
‍
Y
i
>
a
k
)
≤
Pr
(
∑
i
=
1
n
2
‍
Y
i
>
a
k
2
)
,
where Pr
(
Y
i
=
1
-
q
k
)
=
q
k and Pr
(
Y
i
=
-
q
k
)
=
1
-
q
k. This implies that the exponent is at most -
3
n even in case m
k
<
n
2.
Indeed, letA, B, and C be the events that ∑
i
=
1
m
k
‍
Y
i
>
a
k, ∑
i
=
1
n
2
‍
Y
i
>
a
k
/
2, and ∑
i
=
m
k
+
1
n
2
‍
Y
i
<
-
a
k
/
2, respectively. Clearly A and C are independent, and A
∩
C
-
⊂
B. So we have Pr
(
B
)
≥
Pr
(
A
∩
C
-
)
=
Pr
(
A
)
Pr
(
C
-
); that is, Pr
(
A
)
≤
Pr
(
B
)
/
Pr
(
C
-
)
<
Pr
(
B
)
/
2, since by A
.
1.13
(36)
Pr
(
∑
i
=
m
k
+
1
n
2
‍
Y
i
<
-
a
k
2
)
<
e
-
a
k
2
/
8
q
k
(
n
2
-
m
k
)
<
1
2
.
With this we have proved that the sum of the weights of the edges of H
k will not be much larger than their expectation with high probability.
Now we estimate the probability that the sum of the weights is much less than their expectation. Let us useA
.
1.13 again directly to the sums over H
k’s:
(37)
Pr
(
∑
(
u
,
v
)
∈
H
k
‍
(
X
u
v
-
E
X
u
v
)
<
-
a
k
)
<
e
-
a
k
2
/
2
q
k
m
k
.
The exponent in the inequality can be estimated very similarly as before:
(38)
-
a
k
2
2
q
k
m
k
≤
-
β
6
200
(
e
2
e
)
k
K
n
3
e
m
k
<
-
3
n
;
moreover, this bound applies for an arbitrary m
k.
Putting these together we have that(39)
Pr
(
|
∑
(
u
,
v
)
∈
H
k
‍
(
X
u
v
-
E
X
u
v
)
|
>
a
k
)
<
2
-
3
n
.
This implies that
(40)
|
∑
(
u
,
v
)
∈
H
k
X
u
v
-
E
X
u
v
p
u
v
|
A
|
|
B
|
|
≤
|
∑
(
u
,
v
)
∈
H
k
X
u
v
-
E
X
u
v
p
k
-
1
|
A
|
|
B
|
|
≤
a
k
p
k
-
1
|
A
|
|
B
|
≤
β
10
(
1
e
)
k
,
where the last two inequalities hold with probability at least 1
-
2
-
3
n for a given pair of sets A and B if n is sufficiently large. Since
(41)
|
∑
u
∈
A
,
v
∈
B
X
u
v
p
u
v
|
A
|
|
B
|
|
=
|
∑
k
=
1
log
⁡
⁡
n
∑
(
u
,
v
)
∈
H
k
X
u
v
p
u
v
|
A
|
|
B
|
|
≤
∑
k
=
1
log
⁡
⁡
n
|
∑
(
u
,
v
)
∈
H
k
X
u
v
p
k
-
1
|
A
|
|
B
|
|
,
∑
k
=
1
log
⁡
⁡
n
‍
1
10
(
1
e
)
k
≤
1
2
,
the claimed bound follows with high probability.Remark 8.
It is very similar to prove that with high probability|
∑
i
,
j
‍
ρ
G
(
i
,
j
)
-
(
n
2
)
|
=
o
(
n
2
), we omit the details. From this it follows that rescaling the above edge weights by a factor of (
1
+
o
(
1
)
) and letting μ
≡
1 provide us with β-quasi-random weights for most graphs from G
(
n
,
p
i
j
) such that μ
(
V
)
=
n and ρ
G
(
V
,
V
)
=
2
(
n
2
). That is, with high probability we can apply the regularity lemma for any F
⊂
G, where G
∈
G
(
n
,
p
i
j
).


### 4.2. Simple Examples for Defining Vertex and Edge Weights

When defining the notion of weighted quasirandomness and weighted regularity, we mentioned that choosingμ
≡
1 and ρ
≡
1
/
δ
G gives back the old definitions of quasirandomness and regularity. In the previous section we saw an example when we needed different edge weights, but μ was identically one.Let us consider a simple example in whichμ has to take more than one value. Let G be a star on n vertices; that is, the vertex v
1 is adjacent to the vertices v
2
,
…
,
v
n, and v
i has degree 1 for i
≥
2. We let μ
(
v
1
)
=
1
/
2 and μ
(
v
i
)
=
1
/
(
2
(
n
-
1
)
) for i
≥
2 and choose ρ
G
≡
n
/
2. With these choices G is easily seen to be a bipartite quasirandom; moreover, it is weighted regular.A more sophisticated example relates weighted regularity to(
C
,
η
,
D
) boundedness, which is the basic condition in the regularity lemma of Alon et al. [6]. Let us recall that G is (
C
,
η
,
D
) bounded with parameters C
≥
1, η
≥
0 and D is a function from V to [
1
,
n
] if for all X
,
Y
⊂
V, when D
(
X
)
,
D
(
Y
)
≥
η
D
(
V
), the inequality ρ
(
X
,
Y
)
D
(
V
)
≤
C holds, where D
(
X
)
=
∑
x
∈
X
‍
D
(
x
), and ρ
(
X
,
Y
)
:
=
e
(
X
,
Y
)
/
(
D
(
X
)
D
(
Y
)
); that is, ρ is a “generalized edge density.” Then one can obtain an ε-regular partition if η
≪
ε.It is easy to check that the following graphG is β-quasi-random, in fact belongs to G
(
n
,
p
i
,
j
) with appropriate weights, but G is not (
C
,
η
,
D
) bounded. Let V
(
G
)
=
∪
i
=
1
4
A
i, |
A
i
|
=
n
/
4 for i
=
1
,
…
,
4. All edges between A
1 and A
2 are present; there is no edge between the sets A
1
∪
A
2 and A
3
∪
A
4, while between A
3 and A
4 there is a random bipartite graph with edge probability 1
/
η. Of course, if η is small enough compared to C then G cannot be (
C
,
η
,
D
) bounded.Similarly, one can show easily that whenever a graphF is (
C
,
η
,
D
) bounded, then with μ
(
x
)
=
D
(
x
) for all x
∈
V
(
F
) and appropriately defined edge weights F is a dense subgraph of a graph G which is (
2
,
η
)-quasi-random. Hence, Theorem 6 can be applied for F. We leave the details for the reader.


### 4.3. Natural Weighting ofK
n

Assume that|
V
|
=
n. Let the vertex weight function μ
:
V
→
R
+ be defined such that μ
(
V
)
=
n. We also assume that μ
(
v
)
=
o
(
n
) for every v
∈
V, as we did earlier in the paper. Then we define thenatural weighting of the edges of
K
n (K
n can be replaced with other quasirandom graphs. Then the edge weights will be different. You can find more about this at the end of Section 4.5.)with respect to
μ as follows: we let ρ
(
u
,
v
)
=
μ
(
u
)
·
μ
(
v
) for all u
,
v
∈
V, u
≠
v. Observe that
(42)
ρ
(
V
,
V
)
=
μ
(
V
)
μ
(
V
)
-
∑
v
∈
V
‍
μ
2
(
v
)
=
2
(
n
2
)
(
1
-
o
(
1
)
)
.
We show that these weight functions determine a quasirandom weighting of K
n. Let A
,
B
⊂
V such that A
∩
B
=
∅. Then
(43)
ρ
(
A
,
B
)
μ
(
A
)
μ
(
B
)
=
∑
u
∈
A
∑
v
∈
B
μ
(
u
)
μ
(
v
)
μ
(
A
)
μ
(
B
)
=
μ
(
A
)
μ
(
B
)
μ
(
A
)
μ
(
B
)
=
1
,
independent of the weights of A and B. Recalling the definition of quasirandomness it is easy to see that the natural weighting of K
n isalways quasirandom.Note that natural weighting resembles Definition1, where the lower bounds on μ
(
A
) and μ
(
B
) are dropped. It is closely related to the random model G
(
w
); see, for example, [11]. Here w
=
(
w
1
,
…
,
w
n
) is the expected degree sequence of G
(
w
) with vertex set {
1,2
,
…
,
n
}. The edges of G
(
w
) are drawn independently, and the probability of including the edge i
j is w
i
w
j
/
∑
i
‍
w
i. Of course, the model G
(
w
) is the special case of G
(
n
,
p
i
j
), and Lemma 7 holdswithout any conditions. The results in the remainder of the paper also hold in more general weightings; for simplicity, we work out the details for natural weighting.Letu be an arbitrary vertex and A
⊂
V. Then theweighted degree of
u
into
A in the graph F
⊂
K
n is defined to be
(44)
d
w
F
(
u
,
A
)
=
∑
v
∈
A
‍
1
F
(
u
,
v
)
μ
(
v
)
=
μ
(
N
F
(
u
,
A
)
)
,
where N
F
(
u
,
A
) denotes the neighborhood of u in the set A. In particular the weighted degree of u in F is
(45)
d
w
F
(
u
)
=
∑
v
∈
V
‍
1
F
(
u
,
v
)
μ
(
v
)
=
μ
(
N
F
(
u
)
)
.
We also have that
(46)
ρ
F
(
A
,
B
)
=
∑
u
∈
A
‍
∑
v
∈
B
‍
1
F
(
u
,
v
)
ρ
(
u
,
v
)
=
∑
u
∈
A
‍
d
w
F
(
u
,
B
)
,
ρ
F
(
V
,
V
)
=
∑
u
∈
V
‍
d
w
F
(
u
)
.
We define the weighted density of a weighted ε-regular (
A
,
B
) pair to be
(47)
ρ
F
(
A
,
B
)
μ
(
A
)
μ
(
B
)
.
We have the following lemma.Lemma 9.
Let(
A
,
B
) be a weighted ε-regular pair relative to the natural weighting of K
n with weighted density γ
≫
ε. Let A
′
⊂
A contain only such vertices that have weighted degree less than (
γ
-
ε
)
μ
(
B
) in the pair. Then μ
(
A
′
)
<
ε
μ
(
A
).Proof.
Assume on the contrary that the set of “low-degree” vertices has a large weight. Observe thatε-regularity implies that
(48)
ρ
F
(
A
′
,
B
)
μ
(
A
′
)
μ
(
B
)
>
γ
-
ε
if μ
(
A
′
)
>
ε
μ
(
A
). Using our assumption we get the following:
(49)
γ
-
ε
<
ρ
F
(
A
′
,
B
)
μ
(
A
′
)
μ
(
B
)
=
∑
u
∈
A
′
μ
(
u
)
d
w
F
(
u
,
B
)
μ
(
A
′
)
μ
(
B
)
<
∑
u
∈
A
′
μ
(
u
)
(
γ
-
ε
)
μ
(
B
)
μ
(
A
′
)
μ
(
B
)
=
γ
-
ε
,
which is clearly a contradiction.LetA
,
B
1
,
B
2
,
…
,
B
k be disjoint subsets of V
(
F
), and assume that (
A
,
B
i
) is a weighted ε-regular pair relative to a natural weighting of K
n with weighted density at least γ for every i. Set δ
=
γ
-
ε. Let 0
<
s be an integer constant, and assume that δ
s
≫
ε.Lemma 10.
Assume thatA
′
⊂
A with μ
(
A
′
)
>
2
k
ε
μ
(
A
). Then there exist vertices u
1
,
u
2
,
…
,
u
s
∈
A
′ such that
(50)
μ
(
∩
1
≤
i
≤
s
N
F
(
u
i
,
B
j
)
)
≥
δ
s
μ
(
B
j
)
for every 1
≤
j
≤
k.Proof.
We find theu
i vertices one by one. For u
1 we have that the weight of vertices of A with weighted degree at most δ
μ
(
B
1
) is at most ε
μ
(
A
) using Lemma 9. Discard these low-degree vertices from A
′; then use the regularity condition again, this time for B
2. We find that the weight of vertices having small degree into B
1 or B
2 is at most 2
ε
μ
(
A
). Iterating this procedure we get that the weight of vertices that do not have large degree into at least one B
i set is at most k
ε
μ
(
A
)
<
μ
(
A
′
). Pick any of the large degree vertices from A
′; this is our choice for u
1.
Next we repeat the process for findingu
2, with the difference that we look for a vertex that has large degree into the sets N
F
(
u
1
,
B
j
) for every j. Since μ
(
N
F
(
u
1
,
B
j
)
)
≥
δ
μ
(
B
j
)
≫
ε
μ
(
B
j
), the same procedure will work. Applying Lemma 9 we can find many vertices in A
′
-
u
1 such that the weighted degree of all of them into B
j is at least δ
μ
(
N
F
(
u
1
,
B
j
)
)
≥
δ
2
μ
(
B
j
) for every j. Pick any of these; this vertex is u
2.
When it comes to findingu
i we will work with the sets A
′
-
{
u
1
,
…
,
u
i
-
1
} and ∩
t
≤
i
-
1
N
F
(
u
t
,
B
j
) for 1
≤
j
≤
k. Using induction it is easy to show that
(51)
μ
(
∩
t
≤
i
-
1
N
F
(
u
t
,
B
j
)
)
≥
δ
i
-
1
μ
(
B
j
)
for every j. Since δ
s
≫
ε, we can iterate this procedure until we find all the vertices u
1
,
…
,
u
s.Assume now that there areq clusters W
1
,
W
2
,
…
,
W
q
⊂
V
(
F
) such that μ
(
W
i
)
=
m
+
o
(
m
) for all i (here m
≫
ε
n) and all the (
W
i
,
W
j
) pairs are weighted ε-regular relative to a natural weighting of K
n with density at least γ. That is, we have a super-clique C
l
q on q clusters.Next we construct the graphK
q
s, a blown-up clique, as follows. First, we have q disjoint s-element set of vertices; this is the vertex set of K
q
s. Then we connect any two vertices if they belong to different vertex sets. Before we state an embedding result, we need a simple lemma; the proof is left for the reader.Lemma 11.
Let(
A
,
B
) be a weighted ε-regular pair with density d, and for some α let A
′
⊂
A with μ
(
A
′
)
≥
α
μ
(
A
) and B
′
⊂
B with μ
(
B
′
)
≥
α
μ
(
B
). Then (
A
′
,
B
′
) is a weighted ε
′-regular pair with ε
′
=
max
⁡
{
ε
/
α
,
2
ε
} and density d
′
≥
d
-
ε.We have the following embedding lemma.Lemma 12.
Letδ
=
γ
-
2
ε. If δ
q
s
≫
ε then K
q
s
⊂
C
l
q.Proof.
First, apply Lemma10 with A
=
W
1 and B
j
=
W
j
+
1 for 1
≤
j
≤
q
-
1. We find the vertices u
1
1
,
u
2
1
,
…
,
u
s
1
∈
W
1 such that
(52)
μ
(
∩
1
≤
i
≤
s
N
F
(
u
i
1
,
W
j
)
)
≥
δ
s
μ
(
W
j
)
.
Let W
j
2
=
∩
i
≥
1
N
F
(
u
i
1
,
W
j
); then μ
(
W
j
2
)
≥
δ
s
μ
(
W
j
)
≫
ε
μ
(
W
j
) for every j
≥
2.
Next letA
=
W
2
2 and B
j
=
W
j
+
2
2 for 1
≤
j
≤
q
-
2. Using Lemma 11 we have that the new (
A
,
B
j
) pairs are all weighted ε
/
δ
s-regular with density at least γ
-
ε. Hence, we can apply Lemma 10 again and find u
1
2
,
u
2
2
,
…
,
u
s
2
∈
W
2
2 such that
(53)
μ
(
∩
1
≤
i
≤
s
N
F
(
u
i
2
,
W
j
2
)
)
≥
δ
s
μ
(
W
j
2
)
≥
δ
2
s
μ
(
W
j
)
≫
ε
μ
(
W
j
)
for 3
≤
j
≤
q.
Continuing this process, in thekth step we will work with the W
j
k sets when applying Lemma 10. These sets are defined recursively as follows: W
j
k
=
∩
i
≥
1
N
F
(
u
i
k
-
1
,
W
j
k
-
1
) and μ
(
W
j
k
)
≥
δ
(
k
-
1
)
s
μ
(
W
j
) for every k
+
1
≤
j
≤
q. Moreover, the (
W
k
k
,
W
j
k
) pairs will be ε
/
δ
(
k
-
1
)
s-regular with density at least γ
-
ε for every k
+
1
≤
j
≤
q.
In the last step, whenk
=
q
-
1, there are only two subclusters left, W
q
-
1
q
-
1 and W
q
q
-
1. The pair (
W
q
-
1
q
-
1
,
W
q
q
-
1
) will be weighted ε
/
δ
(
q
-
2
)
s-regular with density at least γ
-
ε. It is easy to find a K
s
,
s (a complete bipartite graph) in this regular pair using Lemma 10. Clearly, we constructed the desired K
q
s graph.


### 4.4. Illustration: A Weighted Version of the Erdős-Stone Theorem

Lett
q
-
1
(
n
) be the number of edges in the Turán graph T
n
,
q
-
1 on n vertices. That is, T
n
,
q
-
1 has the largest number of edges such that it does not contain a K
q. It is well known that
(54)
lim
⁡
n
→
∞
t
q
-
1
(
n
)
(
n
2
)
=
q
-
2
q
-
1
.The Erdős-Stone theorem states that if one has at leastt
q
-
1
(
n
)
+
γ
n
2 edges (where γ
>
0 is a constant) in a graph F on n vertices then F has a K
q
s for any given natural number s. In this section we show a weighted version. We take a natural weighting of K
n and prove that if the total edge weight in F
⊂
K
n is large then F has a large blown-up clique. We remark that there are other results in the literature on the extremal theory of weighted graphs; see, for example, [13] by Bondy and Tuza and [14] by Füredi and Kündgen, although the setup of these papers is different from ours. Another version of the Erdős-Stone theorem for sparse graphs can be found in [15].Theorem 13.
For all integersq
≥
2 and s
≥
1 and every γ
>
0 there exists an integer n
0 such that the following holds. Take the natural weighting of K
n with vertex weight function μ and assume that μ
(
V
)
=
n
≥
n
0. Let F
⊂
K
n. If the total edge weight of F is at least t
q
-
1
(
n
)
+
γ
n
2 then F contains K
q
s as a subgraph.Proof.
We begin with applying the weighted regularity lemma with parametersε
≪
min
⁡
{
(
γ
-
ε
)
q
s
,
1
/
s
,
1
/
q
} and L
≫
1
/
ε. We get an ε-regular partition with clusters W
0
,
W
1
,
…
,
W
l. Let us construct thereduced graph
F
r as follows. The vertices of F
r are identified by the l nonexceptional clusters. We have an edge between two vertices of F
r if the corresponding two clusters give an ε-regular pair with density at least γ. Hence, when we construct F
r we lose edges of F as follows: (
1
) edges that are incident with some vertex of W
0, (
2
) edges that connect two vertices that belong to the same nonexceptional cluster, (
3
) edges that are in some irregular pair, and (
4
) edges that are in regular pairs with small density.
The outline of the proof is as follows. We will show that the loss in edge weight is small; hence,F
r will have many edges. By Turán’s Theorem we will have a q-clique in F
r. Then we apply Lemma 12 and conclude the existence of a K
q
s in F.(1)
The total weight of edges that are incident with some vertex ofW
0 can be estimated as follows:
(55)
ρ
F
(
W
0
,
V
)
≤
ρ
(
W
0
,
V
)
=
∑
w
∈
W
0
‍
∑
v
∈
V
‍
ρ
(
w
,
v
)
≤
μ
(
W
0
)
μ
(
V
)
≤
ε
n
2
.
(2)
The nonexceptional clusters have weight(
n
-
ε
n
)
(
1
+
o
(
1
)
)
/
l. The total weight of edges inside nonexceptional clusters is at most
(56)
1
2
∑
1
≤
i
≤
l
‍
∑
u
∈
W
i
‍
∑
v
∈
W
i
-
u
‍
ρ
(
u
,
v
)
=
1
2
∑
1
≤
i
≤
l
‍
∑
u
∈
W
i
‍
∑
v
∈
W
i
-
u
‍
μ
(
u
)
μ
(
v
)
≤
1
2
∑
1
≤
i
≤
l
‍
μ
(
W
i
)
2
=
n
2
l
(
1
+
o
(
1
)
)
.Since l
≥
L
≫
1
/
ε, we have that the total edge weight inside nonexceptional clusters is less than ε
n
2.(3)
Assume that(
W
i
,
W
j
) is an irregular pair. Then
(57)
ρ
F
(
W
i
,
W
j
)
≤
∑
u
∈
W
i
‍
∑
v
∈
W
j
‍
ρ
(
u
,
v
)
=
∑
u
∈
W
i
‍
∑
v
∈
W
j
‍
μ
(
u
)
μ
(
v
)
=
μ
(
W
i
)
μ
(
W
j
)
=
n
2
l
2
(
1
+
o
(
1
)
)
.Since the number of irregular pairs is at most ε
l
2, we get that the total edge weight in irregular pairs is at most
(58)
ε
l
2
n
2
l
2
(
1
+
o
(
1
)
)
<
2
ε
n
2
.
(4)
If the density of anε-regular pair (
W
i
,
W
j
) is small then we have the following inequality:
(59)
ρ
F
(
W
i
,
W
j
)
≤
μ
(
W
i
)
μ
(
W
j
)
γ
=
n
2
l
2
(
1
+
o
(
1
)
)
γ
.Since there can be at most (
l
2
) pairs, the total edge weight in low density pairs is less than 2
γ
n
2
/
3.
Putting together, we get that the total weight of edges that we lose when applying the weighted regularity lemma is at most(
4
ε
+
2
γ
/
3
)
n
2
<
3
γ
n
2
/
4. Hence, the total edge weight in the high-density regular pairs of F
r is at least t
q
-
1
(
n
)
+
γ
n
2
/
4. The total weight of edges in a regular pair is (
1
+
o
(
1
)
)
n
2
/
l
2. Assume that e
(
F
r
)
≤
(
(
q
-
2
)
/
(
q
-
1
)
)
(
l
2
/
2
); then the total edge weight would be at most (
(
q
-
2
)
/
(
q
-
1
)
)
(
n
2
/
2
)
(
1
+
o
(
1
)
). Since we have a larger edge weight in what is left after applying the regularity lemma, using Turán’s theorem we get that F
r contains a K
q. Every pair in this clique is a high-density ε-regular pair; hence, we can apply Lemma 12 and find the blown-up clique.Remarks. One can arrive at the same conclusion perturbing the edge weights a little. Let K
>
1 be a fixed constant. Multiply the weight of the edge e by any number c
e
∈
[
1
/
K
,
K
]. The resulting weighted graph will be quasirandom, and it is an easy exercise to show that one still has Theorem 13.One can also show the weighted version of the Erdős-Stone-Simonovits theorem, a stability version of the above. LetH be a family of forbidden subgraphs having chromatic number q. Assume that the total edge weight in F is close to t
q
-
1
(
n
), but F does not contain some graph H
∈
H. Then F
r the reduced graph cannot have a clique on q vertices, but the number of edges in it will be close to t
q
-
1
(
l
). This implies that F
r is close to a Turán graph T
l
,
q
-
1 and that in turn implies that the vertex set of F can be partitioned into q
-
1 disjoint vertex classes in the following way: the vertex classes all have weight ≈
n
/
(
q
-
1
), the total weight of edges inside vertex classes is very small, and the weighted density of edges for every pair of disjoint classes is close to one.


### 4.5. Emphasized Sets

One cannot avoid having an exceptional clusterW
0 when applying the regularity lemma. That is, a linear number of vertices could be discarded in certain cases; a well-known example is the so-called half-graph. In general we do not have control on what is put into the exceptional cluster. However, using vertex weights one can at least partly control the set of discarded vertices. In what follows we show how to use the natural weighting of K
n in order to have that the majority of some given emphasized set is put into nonexceptional clusters after applying the weighted regularity lemma, even if the set is of size o
(
n
). In fact we will do it for several emphasized sets at the same time. Notice that applying the usual regularity concept (even that of [6]) one may discard all vertices with small degrees.Assume thatk is a fixed constant and V is partitioned into the disjoint sets S
1
,
S
2
,
…
,
S
k, and let n
=
|
V
|. Further assume that s
i
→
∞ as n
→
∞. Let s
i
=
|
S
i
| for every i. Define the following weighting of the vertices of V: for v
∈
S
i we let
(60)
μ
(
v
)
=
μ
i
=
n
k
s
i
.
Observe that
(61)
∑
v
∈
S
i
‍
μ
(
v
)
=
n
k
;
thus, the total weight of the vertices is n. Let v
∈
S
i and w
∈
S
j. The weight of the pair (
v
,
w
) is
(62)
ρ
(
v
,
w
)
=
ρ
i
j
=
μ
(
v
)
μ
(
w
)
=
n
2
k
2
s
i
s
j
.
We showed above that K
n equipped with such vertex and edge weights is a quasirandom graph. We call this particular weighting thenatural weighting of
K
n
with emphasized sets
S
1
,
S
2
,
…
,
S
k
.We can apply Theorem6 for some F relative to the natural weighting of K
n. Choose ε so that k
≪
1
/
ε. Since μ
(
W
0
)
≤
ε
n
≪
n
/
k, we get that for all i the majority of the vertices of S
i are in nonexceptional clusters.We remark that it is possible to define vertex weights not only forG
=
K
n but also for much sparser quasirandom graphs when emphasizing subsets of V. For example, assume that G
∈
G
(
n
,
p
i
j
), and V is partitioned into the disjoint sets S
1
,
S
2
,
…
,
S
k. Then one will have the vertex weights of the above example, but the edge weights will be different:
(63)
ρ
(
v
i
,
v
j
)
=
μ
(
v
i
)
μ
(
v
j
)
1
p
i
j
=
n
2
k
2
s
q
s
t
p
i
j
whenever v
i
∈
S
q and v
j
∈
S
t. We leave the details for the reader.


## 4.1. Quasirandomness in theG
(
n
,
p
i
j
) Model

In this section we will prove that random graphs of theG
(
n
,
p
i
j
) model are quasirandom in the strong sense with high probability. A special case of this model is the well-known G
(
n
,
p
) model for random graphs. A regularity lemma for this case was first applied by Kohayakawa et al. [5]. They studied G
(
n
,
p
) for p
=
c
/
n in order to find arithmetic progressions of length three in dense subsets of random subsets of [
N
].TheG
(
n
,
p
i
j
) model was first considered by Bollobás [10]. Recently it was also studied by Chung and Lu [11]. In this model one takes n vertices and draws an edge between the vertices x
i and x
j with probability p
i
j, randomly and independently of each other. Note that if p
i
j
≡
p, then we get back the well-known G
(
n
,
p
) model. It is a straightforward application of the Chernoff bound that a random graph G
∈
G
(
n
,
p
) is quasirandom with high probability if p
≫
1
/
n. However, the case of G
(
n
,
p
i
,
j
) is somewhat harder.Lemma 7.
Letβ
>
0. There exists a K
=
K
(
β
) such that if G
∈
G
(
n
,
p
i
j
) and p
i
j
≥
K
/
n for every i and j, then G is weighted β-quasi-random with probability at least 1
-
2
-
n if n is sufficiently large.Proof.
First of all letμ
≡
1, and let ρ
(
i
,
j
)
=
1
/
p
i
,
j. Set K
=
4800
/
β
6. Let p
0
=
K
/
n, and let p
k
=
e
k
p
0 for 1
≤
k
≤
log
⁡
⁡
n. Let A and B be a pair of disjoint sets, both of size at least β
n. We partition the pairs (
u
,
v
), where u
∈
A and v
∈
B, into O
(
log
⁡
⁡
n
) disjoint sets H
1
,
H
2
,
…
,
H
l: if p
k
≤
p
u
v
<
p
k
+
1 then (
u
,
v
) will belong to H
k. Let a
k
=
(
β
3
/
10
)
e
k
K
n. We will denote |
H
k
| by m
k.
We will prove that the following inequality holds with probability at least1
-
2
-
3
n:
(30)
|
∑
u
∈
A
,
v
∈
B
‍
X
u
v
p
u
v
|
A
|
|
B
|
-
1
|
<
β
/
2
,
where X
u
v is a random variable which is 1 if u
v
∈
E
(
G
); otherwise it is 0. This implies the quasirandomness of G since there are less than 2
2
n pairs of disjoint subsets of V
(
G
). Observe that
(31)
∑
u
∈
A
,
v
∈
B
‍
E
X
u
v
p
u
v
|
A
|
|
B
|
=
1
.
Applying the large deviation inequalitiesA
.
1.11 and A
.
1.13 from [12], we are able to bound the number of edges in between A and B for the edges of H
k in case m
k is sufficiently large as follows. According to A
.
1.11 we have that
(32)
Pr
(
∑
(
u
,
v
)
∈
H
k
‍
(
X
u
v
-
E
X
u
v
)
>
a
k
)
<
e
-
(
a
k
2
/
2
q
k
m
k
)
+
(
a
k
3
/
2
q
k
2
m
k
2
)
,
where
(33)
p
k
≤
q
k
=
∑
(
u
,
v
)
∈
H
k
‍
p
u
v
m
k
<
p
k
+
1
.
We estimate the exponent in case m
k
=
n
2:
(34)
-
a
k
2
2
q
k
m
k
+
a
k
3
2
q
k
2
m
k
2
≤
-
β
6
200
(
e
2
e
)
k
K
n
3
e
m
k
+
β
9
2000
(
e
3
e
2
)
k
e
K
n
5
m
k
2
<
-
3
n
,
where we used the definition of K. For m
k being much less than n
2, direct substitution gives a useless bound. For this case we have the useful inequality
(35)
1
2
Pr
(
∑
i
=
1
m
k
‍
Y
i
>
a
k
)
≤
Pr
(
∑
i
=
1
n
2
‍
Y
i
>
a
k
2
)
,
where Pr
(
Y
i
=
1
-
q
k
)
=
q
k and Pr
(
Y
i
=
-
q
k
)
=
1
-
q
k. This implies that the exponent is at most -
3
n even in case m
k
<
n
2.
Indeed, letA, B, and C be the events that ∑
i
=
1
m
k
‍
Y
i
>
a
k, ∑
i
=
1
n
2
‍
Y
i
>
a
k
/
2, and ∑
i
=
m
k
+
1
n
2
‍
Y
i
<
-
a
k
/
2, respectively. Clearly A and C are independent, and A
∩
C
-
⊂
B. So we have Pr
(
B
)
≥
Pr
(
A
∩
C
-
)
=
Pr
(
A
)
Pr
(
C
-
); that is, Pr
(
A
)
≤
Pr
(
B
)
/
Pr
(
C
-
)
<
Pr
(
B
)
/
2, since by A
.
1.13
(36)
Pr
(
∑
i
=
m
k
+
1
n
2
‍
Y
i
<
-
a
k
2
)
<
e
-
a
k
2
/
8
q
k
(
n
2
-
m
k
)
<
1
2
.
With this we have proved that the sum of the weights of the edges of H
k will not be much larger than their expectation with high probability.
Now we estimate the probability that the sum of the weights is much less than their expectation. Let us useA
.
1.13 again directly to the sums over H
k’s:
(37)
Pr
(
∑
(
u
,
v
)
∈
H
k
‍
(
X
u
v
-
E
X
u
v
)
<
-
a
k
)
<
e
-
a
k
2
/
2
q
k
m
k
.
The exponent in the inequality can be estimated very similarly as before:
(38)
-
a
k
2
2
q
k
m
k
≤
-
β
6
200
(
e
2
e
)
k
K
n
3
e
m
k
<
-
3
n
;
moreover, this bound applies for an arbitrary m
k.
Putting these together we have that(39)
Pr
(
|
∑
(
u
,
v
)
∈
H
k
‍
(
X
u
v
-
E
X
u
v
)
|
>
a
k
)
<
2
-
3
n
.
This implies that
(40)
|
∑
(
u
,
v
)
∈
H
k
X
u
v
-
E
X
u
v
p
u
v
|
A
|
|
B
|
|
≤
|
∑
(
u
,
v
)
∈
H
k
X
u
v
-
E
X
u
v
p
k
-
1
|
A
|
|
B
|
|
≤
a
k
p
k
-
1
|
A
|
|
B
|
≤
β
10
(
1
e
)
k
,
where the last two inequalities hold with probability at least 1
-
2
-
3
n for a given pair of sets A and B if n is sufficiently large. Since
(41)
|
∑
u
∈
A
,
v
∈
B
X
u
v
p
u
v
|
A
|
|
B
|
|
=
|
∑
k
=
1
log
⁡
⁡
n
∑
(
u
,
v
)
∈
H
k
X
u
v
p
u
v
|
A
|
|
B
|
|
≤
∑
k
=
1
log
⁡
⁡
n
|
∑
(
u
,
v
)
∈
H
k
X
u
v
p
k
-
1
|
A
|
|
B
|
|
,
∑
k
=
1
log
⁡
⁡
n
‍
1
10
(
1
e
)
k
≤
1
2
,
the claimed bound follows with high probability.Remark 8.
It is very similar to prove that with high probability|
∑
i
,
j
‍
ρ
G
(
i
,
j
)
-
(
n
2
)
|
=
o
(
n
2
), we omit the details. From this it follows that rescaling the above edge weights by a factor of (
1
+
o
(
1
)
) and letting μ
≡
1 provide us with β-quasi-random weights for most graphs from G
(
n
,
p
i
j
) such that μ
(
V
)
=
n and ρ
G
(
V
,
V
)
=
2
(
n
2
). That is, with high probability we can apply the regularity lemma for any F
⊂
G, where G
∈
G
(
n
,
p
i
j
).


## 4.2. Simple Examples for Defining Vertex and Edge Weights

When defining the notion of weighted quasirandomness and weighted regularity, we mentioned that choosingμ
≡
1 and ρ
≡
1
/
δ
G gives back the old definitions of quasirandomness and regularity. In the previous section we saw an example when we needed different edge weights, but μ was identically one.Let us consider a simple example in whichμ has to take more than one value. Let G be a star on n vertices; that is, the vertex v
1 is adjacent to the vertices v
2
,
…
,
v
n, and v
i has degree 1 for i
≥
2. We let μ
(
v
1
)
=
1
/
2 and μ
(
v
i
)
=
1
/
(
2
(
n
-
1
)
) for i
≥
2 and choose ρ
G
≡
n
/
2. With these choices G is easily seen to be a bipartite quasirandom; moreover, it is weighted regular.A more sophisticated example relates weighted regularity to(
C
,
η
,
D
) boundedness, which is the basic condition in the regularity lemma of Alon et al. [6]. Let us recall that G is (
C
,
η
,
D
) bounded with parameters C
≥
1, η
≥
0 and D is a function from V to [
1
,
n
] if for all X
,
Y
⊂
V, when D
(
X
)
,
D
(
Y
)
≥
η
D
(
V
), the inequality ρ
(
X
,
Y
)
D
(
V
)
≤
C holds, where D
(
X
)
=
∑
x
∈
X
‍
D
(
x
), and ρ
(
X
,
Y
)
:
=
e
(
X
,
Y
)
/
(
D
(
X
)
D
(
Y
)
); that is, ρ is a “generalized edge density.” Then one can obtain an ε-regular partition if η
≪
ε.It is easy to check that the following graphG is β-quasi-random, in fact belongs to G
(
n
,
p
i
,
j
) with appropriate weights, but G is not (
C
,
η
,
D
) bounded. Let V
(
G
)
=
∪
i
=
1
4
A
i, |
A
i
|
=
n
/
4 for i
=
1
,
…
,
4. All edges between A
1 and A
2 are present; there is no edge between the sets A
1
∪
A
2 and A
3
∪
A
4, while between A
3 and A
4 there is a random bipartite graph with edge probability 1
/
η. Of course, if η is small enough compared to C then G cannot be (
C
,
η
,
D
) bounded.Similarly, one can show easily that whenever a graphF is (
C
,
η
,
D
) bounded, then with μ
(
x
)
=
D
(
x
) for all x
∈
V
(
F
) and appropriately defined edge weights F is a dense subgraph of a graph G which is (
2
,
η
)-quasi-random. Hence, Theorem 6 can be applied for F. We leave the details for the reader.


## 4.3. Natural Weighting ofK
n

Assume that|
V
|
=
n. Let the vertex weight function μ
:
V
→
R
+ be defined such that μ
(
V
)
=
n. We also assume that μ
(
v
)
=
o
(
n
) for every v
∈
V, as we did earlier in the paper. Then we define thenatural weighting of the edges of
K
n (K
n can be replaced with other quasirandom graphs. Then the edge weights will be different. You can find more about this at the end of Section 4.5.)with respect to
μ as follows: we let ρ
(
u
,
v
)
=
μ
(
u
)
·
μ
(
v
) for all u
,
v
∈
V, u
≠
v. Observe that
(42)
ρ
(
V
,
V
)
=
μ
(
V
)
μ
(
V
)
-
∑
v
∈
V
‍
μ
2
(
v
)
=
2
(
n
2
)
(
1
-
o
(
1
)
)
.
We show that these weight functions determine a quasirandom weighting of K
n. Let A
,
B
⊂
V such that A
∩
B
=
∅. Then
(43)
ρ
(
A
,
B
)
μ
(
A
)
μ
(
B
)
=
∑
u
∈
A
∑
v
∈
B
μ
(
u
)
μ
(
v
)
μ
(
A
)
μ
(
B
)
=
μ
(
A
)
μ
(
B
)
μ
(
A
)
μ
(
B
)
=
1
,
independent of the weights of A and B. Recalling the definition of quasirandomness it is easy to see that the natural weighting of K
n isalways quasirandom.Note that natural weighting resembles Definition1, where the lower bounds on μ
(
A
) and μ
(
B
) are dropped. It is closely related to the random model G
(
w
); see, for example, [11]. Here w
=
(
w
1
,
…
,
w
n
) is the expected degree sequence of G
(
w
) with vertex set {
1,2
,
…
,
n
}. The edges of G
(
w
) are drawn independently, and the probability of including the edge i
j is w
i
w
j
/
∑
i
‍
w
i. Of course, the model G
(
w
) is the special case of G
(
n
,
p
i
j
), and Lemma 7 holdswithout any conditions. The results in the remainder of the paper also hold in more general weightings; for simplicity, we work out the details for natural weighting.Letu be an arbitrary vertex and A
⊂
V. Then theweighted degree of
u
into
A in the graph F
⊂
K
n is defined to be
(44)
d
w
F
(
u
,
A
)
=
∑
v
∈
A
‍
1
F
(
u
,
v
)
μ
(
v
)
=
μ
(
N
F
(
u
,
A
)
)
,
where N
F
(
u
,
A
) denotes the neighborhood of u in the set A. In particular the weighted degree of u in F is
(45)
d
w
F
(
u
)
=
∑
v
∈
V
‍
1
F
(
u
,
v
)
μ
(
v
)
=
μ
(
N
F
(
u
)
)
.
We also have that
(46)
ρ
F
(
A
,
B
)
=
∑
u
∈
A
‍
∑
v
∈
B
‍
1
F
(
u
,
v
)
ρ
(
u
,
v
)
=
∑
u
∈
A
‍
d
w
F
(
u
,
B
)
,
ρ
F
(
V
,
V
)
=
∑
u
∈
V
‍
d
w
F
(
u
)
.
We define the weighted density of a weighted ε-regular (
A
,
B
) pair to be
(47)
ρ
F
(
A
,
B
)
μ
(
A
)
μ
(
B
)
.
We have the following lemma.Lemma 9.
Let(
A
,
B
) be a weighted ε-regular pair relative to the natural weighting of K
n with weighted density γ
≫
ε. Let A
′
⊂
A contain only such vertices that have weighted degree less than (
γ
-
ε
)
μ
(
B
) in the pair. Then μ
(
A
′
)
<
ε
μ
(
A
).Proof.
Assume on the contrary that the set of “low-degree” vertices has a large weight. Observe thatε-regularity implies that
(48)
ρ
F
(
A
′
,
B
)
μ
(
A
′
)
μ
(
B
)
>
γ
-
ε
if μ
(
A
′
)
>
ε
μ
(
A
). Using our assumption we get the following:
(49)
γ
-
ε
<
ρ
F
(
A
′
,
B
)
μ
(
A
′
)
μ
(
B
)
=
∑
u
∈
A
′
μ
(
u
)
d
w
F
(
u
,
B
)
μ
(
A
′
)
μ
(
B
)
<
∑
u
∈
A
′
μ
(
u
)
(
γ
-
ε
)
μ
(
B
)
μ
(
A
′
)
μ
(
B
)
=
γ
-
ε
,
which is clearly a contradiction.LetA
,
B
1
,
B
2
,
…
,
B
k be disjoint subsets of V
(
F
), and assume that (
A
,
B
i
) is a weighted ε-regular pair relative to a natural weighting of K
n with weighted density at least γ for every i. Set δ
=
γ
-
ε. Let 0
<
s be an integer constant, and assume that δ
s
≫
ε.Lemma 10.
Assume thatA
′
⊂
A with μ
(
A
′
)
>
2
k
ε
μ
(
A
). Then there exist vertices u
1
,
u
2
,
…
,
u
s
∈
A
′ such that
(50)
μ
(
∩
1
≤
i
≤
s
N
F
(
u
i
,
B
j
)
)
≥
δ
s
μ
(
B
j
)
for every 1
≤
j
≤
k.Proof.
We find theu
i vertices one by one. For u
1 we have that the weight of vertices of A with weighted degree at most δ
μ
(
B
1
) is at most ε
μ
(
A
) using Lemma 9. Discard these low-degree vertices from A
′; then use the regularity condition again, this time for B
2. We find that the weight of vertices having small degree into B
1 or B
2 is at most 2
ε
μ
(
A
). Iterating this procedure we get that the weight of vertices that do not have large degree into at least one B
i set is at most k
ε
μ
(
A
)
<
μ
(
A
′
). Pick any of the large degree vertices from A
′; this is our choice for u
1.
Next we repeat the process for findingu
2, with the difference that we look for a vertex that has large degree into the sets N
F
(
u
1
,
B
j
) for every j. Since μ
(
N
F
(
u
1
,
B
j
)
)
≥
δ
μ
(
B
j
)
≫
ε
μ
(
B
j
), the same procedure will work. Applying Lemma 9 we can find many vertices in A
′
-
u
1 such that the weighted degree of all of them into B
j is at least δ
μ
(
N
F
(
u
1
,
B
j
)
)
≥
δ
2
μ
(
B
j
) for every j. Pick any of these; this vertex is u
2.
When it comes to findingu
i we will work with the sets A
′
-
{
u
1
,
…
,
u
i
-
1
} and ∩
t
≤
i
-
1
N
F
(
u
t
,
B
j
) for 1
≤
j
≤
k. Using induction it is easy to show that
(51)
μ
(
∩
t
≤
i
-
1
N
F
(
u
t
,
B
j
)
)
≥
δ
i
-
1
μ
(
B
j
)
for every j. Since δ
s
≫
ε, we can iterate this procedure until we find all the vertices u
1
,
…
,
u
s.Assume now that there areq clusters W
1
,
W
2
,
…
,
W
q
⊂
V
(
F
) such that μ
(
W
i
)
=
m
+
o
(
m
) for all i (here m
≫
ε
n) and all the (
W
i
,
W
j
) pairs are weighted ε-regular relative to a natural weighting of K
n with density at least γ. That is, we have a super-clique C
l
q on q clusters.Next we construct the graphK
q
s, a blown-up clique, as follows. First, we have q disjoint s-element set of vertices; this is the vertex set of K
q
s. Then we connect any two vertices if they belong to different vertex sets. Before we state an embedding result, we need a simple lemma; the proof is left for the reader.Lemma 11.
Let(
A
,
B
) be a weighted ε-regular pair with density d, and for some α let A
′
⊂
A with μ
(
A
′
)
≥
α
μ
(
A
) and B
′
⊂
B with μ
(
B
′
)
≥
α
μ
(
B
). Then (
A
′
,
B
′
) is a weighted ε
′-regular pair with ε
′
=
max
⁡
{
ε
/
α
,
2
ε
} and density d
′
≥
d
-
ε.We have the following embedding lemma.Lemma 12.
Letδ
=
γ
-
2
ε. If δ
q
s
≫
ε then K
q
s
⊂
C
l
q.Proof.
First, apply Lemma10 with A
=
W
1 and B
j
=
W
j
+
1 for 1
≤
j
≤
q
-
1. We find the vertices u
1
1
,
u
2
1
,
…
,
u
s
1
∈
W
1 such that
(52)
μ
(
∩
1
≤
i
≤
s
N
F
(
u
i
1
,
W
j
)
)
≥
δ
s
μ
(
W
j
)
.
Let W
j
2
=
∩
i
≥
1
N
F
(
u
i
1
,
W
j
); then μ
(
W
j
2
)
≥
δ
s
μ
(
W
j
)
≫
ε
μ
(
W
j
) for every j
≥
2.
Next letA
=
W
2
2 and B
j
=
W
j
+
2
2 for 1
≤
j
≤
q
-
2. Using Lemma 11 we have that the new (
A
,
B
j
) pairs are all weighted ε
/
δ
s-regular with density at least γ
-
ε. Hence, we can apply Lemma 10 again and find u
1
2
,
u
2
2
,
…
,
u
s
2
∈
W
2
2 such that
(53)
μ
(
∩
1
≤
i
≤
s
N
F
(
u
i
2
,
W
j
2
)
)
≥
δ
s
μ
(
W
j
2
)
≥
δ
2
s
μ
(
W
j
)
≫
ε
μ
(
W
j
)
for 3
≤
j
≤
q.
Continuing this process, in thekth step we will work with the W
j
k sets when applying Lemma 10. These sets are defined recursively as follows: W
j
k
=
∩
i
≥
1
N
F
(
u
i
k
-
1
,
W
j
k
-
1
) and μ
(
W
j
k
)
≥
δ
(
k
-
1
)
s
μ
(
W
j
) for every k
+
1
≤
j
≤
q. Moreover, the (
W
k
k
,
W
j
k
) pairs will be ε
/
δ
(
k
-
1
)
s-regular with density at least γ
-
ε for every k
+
1
≤
j
≤
q.
In the last step, whenk
=
q
-
1, there are only two subclusters left, W
q
-
1
q
-
1 and W
q
q
-
1. The pair (
W
q
-
1
q
-
1
,
W
q
q
-
1
) will be weighted ε
/
δ
(
q
-
2
)
s-regular with density at least γ
-
ε. It is easy to find a K
s
,
s (a complete bipartite graph) in this regular pair using Lemma 10. Clearly, we constructed the desired K
q
s graph.


## 4.4. Illustration: A Weighted Version of the Erdős-Stone Theorem

Lett
q
-
1
(
n
) be the number of edges in the Turán graph T
n
,
q
-
1 on n vertices. That is, T
n
,
q
-
1 has the largest number of edges such that it does not contain a K
q. It is well known that
(54)
lim
⁡
n
→
∞
t
q
-
1
(
n
)
(
n
2
)
=
q
-
2
q
-
1
.The Erdős-Stone theorem states that if one has at leastt
q
-
1
(
n
)
+
γ
n
2 edges (where γ
>
0 is a constant) in a graph F on n vertices then F has a K
q
s for any given natural number s. In this section we show a weighted version. We take a natural weighting of K
n and prove that if the total edge weight in F
⊂
K
n is large then F has a large blown-up clique. We remark that there are other results in the literature on the extremal theory of weighted graphs; see, for example, [13] by Bondy and Tuza and [14] by Füredi and Kündgen, although the setup of these papers is different from ours. Another version of the Erdős-Stone theorem for sparse graphs can be found in [15].Theorem 13.
For all integersq
≥
2 and s
≥
1 and every γ
>
0 there exists an integer n
0 such that the following holds. Take the natural weighting of K
n with vertex weight function μ and assume that μ
(
V
)
=
n
≥
n
0. Let F
⊂
K
n. If the total edge weight of F is at least t
q
-
1
(
n
)
+
γ
n
2 then F contains K
q
s as a subgraph.Proof.
We begin with applying the weighted regularity lemma with parametersε
≪
min
⁡
{
(
γ
-
ε
)
q
s
,
1
/
s
,
1
/
q
} and L
≫
1
/
ε. We get an ε-regular partition with clusters W
0
,
W
1
,
…
,
W
l. Let us construct thereduced graph
F
r as follows. The vertices of F
r are identified by the l nonexceptional clusters. We have an edge between two vertices of F
r if the corresponding two clusters give an ε-regular pair with density at least γ. Hence, when we construct F
r we lose edges of F as follows: (
1
) edges that are incident with some vertex of W
0, (
2
) edges that connect two vertices that belong to the same nonexceptional cluster, (
3
) edges that are in some irregular pair, and (
4
) edges that are in regular pairs with small density.
The outline of the proof is as follows. We will show that the loss in edge weight is small; hence,F
r will have many edges. By Turán’s Theorem we will have a q-clique in F
r. Then we apply Lemma 12 and conclude the existence of a K
q
s in F.(1)
The total weight of edges that are incident with some vertex ofW
0 can be estimated as follows:
(55)
ρ
F
(
W
0
,
V
)
≤
ρ
(
W
0
,
V
)
=
∑
w
∈
W
0
‍
∑
v
∈
V
‍
ρ
(
w
,
v
)
≤
μ
(
W
0
)
μ
(
V
)
≤
ε
n
2
.
(2)
The nonexceptional clusters have weight(
n
-
ε
n
)
(
1
+
o
(
1
)
)
/
l. The total weight of edges inside nonexceptional clusters is at most
(56)
1
2
∑
1
≤
i
≤
l
‍
∑
u
∈
W
i
‍
∑
v
∈
W
i
-
u
‍
ρ
(
u
,
v
)
=
1
2
∑
1
≤
i
≤
l
‍
∑
u
∈
W
i
‍
∑
v
∈
W
i
-
u
‍
μ
(
u
)
μ
(
v
)
≤
1
2
∑
1
≤
i
≤
l
‍
μ
(
W
i
)
2
=
n
2
l
(
1
+
o
(
1
)
)
.Since l
≥
L
≫
1
/
ε, we have that the total edge weight inside nonexceptional clusters is less than ε
n
2.(3)
Assume that(
W
i
,
W
j
) is an irregular pair. Then
(57)
ρ
F
(
W
i
,
W
j
)
≤
∑
u
∈
W
i
‍
∑
v
∈
W
j
‍
ρ
(
u
,
v
)
=
∑
u
∈
W
i
‍
∑
v
∈
W
j
‍
μ
(
u
)
μ
(
v
)
=
μ
(
W
i
)
μ
(
W
j
)
=
n
2
l
2
(
1
+
o
(
1
)
)
.Since the number of irregular pairs is at most ε
l
2, we get that the total edge weight in irregular pairs is at most
(58)
ε
l
2
n
2
l
2
(
1
+
o
(
1
)
)
<
2
ε
n
2
.
(4)
If the density of anε-regular pair (
W
i
,
W
j
) is small then we have the following inequality:
(59)
ρ
F
(
W
i
,
W
j
)
≤
μ
(
W
i
)
μ
(
W
j
)
γ
=
n
2
l
2
(
1
+
o
(
1
)
)
γ
.Since there can be at most (
l
2
) pairs, the total edge weight in low density pairs is less than 2
γ
n
2
/
3.
Putting together, we get that the total weight of edges that we lose when applying the weighted regularity lemma is at most(
4
ε
+
2
γ
/
3
)
n
2
<
3
γ
n
2
/
4. Hence, the total edge weight in the high-density regular pairs of F
r is at least t
q
-
1
(
n
)
+
γ
n
2
/
4. The total weight of edges in a regular pair is (
1
+
o
(
1
)
)
n
2
/
l
2. Assume that e
(
F
r
)
≤
(
(
q
-
2
)
/
(
q
-
1
)
)
(
l
2
/
2
); then the total edge weight would be at most (
(
q
-
2
)
/
(
q
-
1
)
)
(
n
2
/
2
)
(
1
+
o
(
1
)
). Since we have a larger edge weight in what is left after applying the regularity lemma, using Turán’s theorem we get that F
r contains a K
q. Every pair in this clique is a high-density ε-regular pair; hence, we can apply Lemma 12 and find the blown-up clique.Remarks. One can arrive at the same conclusion perturbing the edge weights a little. Let K
>
1 be a fixed constant. Multiply the weight of the edge e by any number c
e
∈
[
1
/
K
,
K
]. The resulting weighted graph will be quasirandom, and it is an easy exercise to show that one still has Theorem 13.One can also show the weighted version of the Erdős-Stone-Simonovits theorem, a stability version of the above. LetH be a family of forbidden subgraphs having chromatic number q. Assume that the total edge weight in F is close to t
q
-
1
(
n
), but F does not contain some graph H
∈
H. Then F
r the reduced graph cannot have a clique on q vertices, but the number of edges in it will be close to t
q
-
1
(
l
). This implies that F
r is close to a Turán graph T
l
,
q
-
1 and that in turn implies that the vertex set of F can be partitioned into q
-
1 disjoint vertex classes in the following way: the vertex classes all have weight ≈
n
/
(
q
-
1
), the total weight of edges inside vertex classes is very small, and the weighted density of edges for every pair of disjoint classes is close to one.


## 4.5. Emphasized Sets

One cannot avoid having an exceptional clusterW
0 when applying the regularity lemma. That is, a linear number of vertices could be discarded in certain cases; a well-known example is the so-called half-graph. In general we do not have control on what is put into the exceptional cluster. However, using vertex weights one can at least partly control the set of discarded vertices. In what follows we show how to use the natural weighting of K
n in order to have that the majority of some given emphasized set is put into nonexceptional clusters after applying the weighted regularity lemma, even if the set is of size o
(
n
). In fact we will do it for several emphasized sets at the same time. Notice that applying the usual regularity concept (even that of [6]) one may discard all vertices with small degrees.Assume thatk is a fixed constant and V is partitioned into the disjoint sets S
1
,
S
2
,
…
,
S
k, and let n
=
|
V
|. Further assume that s
i
→
∞ as n
→
∞. Let s
i
=
|
S
i
| for every i. Define the following weighting of the vertices of V: for v
∈
S
i we let
(60)
μ
(
v
)
=
μ
i
=
n
k
s
i
.
Observe that
(61)
∑
v
∈
S
i
‍
μ
(
v
)
=
n
k
;
thus, the total weight of the vertices is n. Let v
∈
S
i and w
∈
S
j. The weight of the pair (
v
,
w
) is
(62)
ρ
(
v
,
w
)
=
ρ
i
j
=
μ
(
v
)
μ
(
w
)
=
n
2
k
2
s
i
s
j
.
We showed above that K
n equipped with such vertex and edge weights is a quasirandom graph. We call this particular weighting thenatural weighting of
K
n
with emphasized sets
S
1
,
S
2
,
…
,
S
k
.We can apply Theorem6 for some F relative to the natural weighting of K
n. Choose ε so that k
≪
1
/
ε. Since μ
(
W
0
)
≤
ε
n
≪
n
/
k, we get that for all i the majority of the vertices of S
i are in nonexceptional clusters.We remark that it is possible to define vertex weights not only forG
=
K
n but also for much sparser quasirandom graphs when emphasizing subsets of V. For example, assume that G
∈
G
(
n
,
p
i
j
), and V is partitioned into the disjoint sets S
1
,
S
2
,
…
,
S
k. Then one will have the vertex weights of the above example, but the edge weights will be different:
(63)
ρ
(
v
i
,
v
j
)
=
μ
(
v
i
)
μ
(
v
j
)
1
p
i
j
=
n
2
k
2
s
q
s
t
p
i
j
whenever v
i
∈
S
q and v
j
∈
S
t. We leave the details for the reader.



---

*Source: 602657-2014-06-19.xml*