ISSN 0001-4346, Mathematical Notes, 2015, Vol. 97, No. 5, pp. 709–724. © Pleiades Publishing, Ltd., 2015. Original Russian Text © A. A. Kokotkin, A. M. Raigorodskii, 2015, published in Matematicheskie Zametki, 2015, Vol. 97, No. 5, pp. 699–717.

On the Realization of Subgraphs of a Random Graph by Diameter Graphs in Euclidean Spaces A. A. Kokotkin1* and A. M. Raigorodskii1, 2** 1

Moscow Institute of Physics and Technology, Dolgoprudnyi, Moscow Region, Russia 2 Lomonosov Moscow State University, Moscow, Russia Received May 25, 2014; in final form, October 26, 2014

Abstract—The present paper is motivated by Borsuk’s classical problem of the partition of sets in spaces into parts of smaller diameter. We obtain sharp estimates for the maximal number of vertices of the induced subgraph of a random graph that, with high probability, is isomorphic to the diameter graph with given chromatic number in a space of any fixed dimension. DOI: 10.1134/S0001434615050065 Keywords: random graph, diameter graph, Euclidean space, Borsuk problem, chromatic number, independence number.

1. INTRODUCTION The present paper is devoted to the study of certain probability characteristics related to Borsuk’s classical problem. Recall that this problem is to find the Borsuk number f (d), which is the minimal number of parts of smaller diameter into which an arbitrary set of diameter 1 in the space Rd can be partitioned:   f (d) = min f : ∀ Ω ⊂ Rd , diam Ω = 1, ∃Ω1 , . . . , Ωf : Ω = Ω1 ∪ · · · ∪ Ωf , ∀ i diam Ωi < 1 . The Borsuk conjecture proposed in 1933 (see [1]), is stated as the equality f (d) = d + 1; this conjecture was neither validated nor refuted for exactly 60 years until, in 1993, Kahn and Kalai found counterexamples to the conjecture for dimensions d ≥ 2015. Now it is known that the Borsuk conjecture is valid for d ≤ 3 and false for d ≥ 64 (see [2]–[8]). The Borsuk problem is closely related the notion of diameter graph. By a diameter graph in Rd we mean an arbitrary graph G = (V, E) whose vertices are points of Rd and edges are pairs of vertices removed from one another by the maximum distance in the vertex set:   E = {x, y} : |x − y| = diam V := max |x − y| . V ⊂ Rd , |V | < ∞, x,y∈V

Obviously, the minimal number of parts of smaller diameter into which V is partitiond (the Borsuk number of the set V ) is the chromatic number χ(G) of the graph G, i.e., the least number of colors that can be used to color the vertices so that the endpoints of any edge are of different color. However, it would be wrong to say that f (d) is the maximum of such chromatic numbers. The fact is that the chromatic number is equal to the Borsuk number only in the case of finite sets; for infinite sets, in general, such an equality no longer holds: for example, if for V we take a sphere in Rd , then, obviously, the chromatic number of its diameter graph (which is a matching) is equal to 2, while its Borsuk number is d + 1 in view of the classical theorem of Borsuk, Ulam, Lyusternik, and Shnirelman (see [9]). As noted above, the Borsuk conjecture has been proved in the plane and in space. Moreover, there exist sufficiently many examples of diameter graphs in R2 and R3 with chromatic numbers 3 and 4, * **

E-mail: [email protected] E-mail: [email protected]

709

710

KOKOTKIN, RAIGORODSKII

respectively. It is of interest to estimate how often these examples occur. One of the tools for such an ˝ ´ estimation is the random Erdos–R enyi graph (see [10]). Namely, let Vn = {1, . . . , n}, p = p(n) ∈ [0, 1], and let G(n, p) = (Ωn , Fn , Pn,p ) be a probability space in which Ωn is the set of all nonoriented graphs 2 on Vn free of loops and multiple edges (so that |Ωn | = 2Cn ), Fn = 2Ωn , and1 Pn,p (G) = p|E| (1 − p)Cn −|E| . 2

In other words, we consider random graphs with n vertices that are joined by edges drawn independently with the same probability p. Set  ud (n, p) = max k : Pn,p (∃H = (W, F ) ⊂ G : |W | = k, H = G|W ,  1 d , H is a diameter graph in R , χ(H) = d + 1) > 2  ud (n, p) = max k : Pn,p (∃H = (W, F ) ⊂ G : |W | = k, H = G|W ,  1 d . H is a connected diameter graph in R , χ(H) = d + 1) > 2 Thus, we search for the maximal number of vertices in an induced (connected) subgraph of a random graph that is simultaneously realized by the diameter graph in space and has, for d ≤ 3, the greatest possible (in this case) chromatic number (for d ≥ 64, such a setting becomes rather arbitrary, but still meaningful as before). If, for any k,  Pn,p ∃H = (W, F ) ⊂ G : 1 |W | = k, H = G|W , H is a diameter graph in Rd , χ(H) = d + 1 ≤ , 2  then we set ud (n, p) = 0 and, similarly, ud (n, p) = 0. The quantity u2 (n, p) was introduced in [11], while similar quantities for so-called distance graphs were considered in [13]–[15]. In the following section, we formulate old and new results. 2. FORMULATION OF THE RESULTS In [11], as well as in [12], we proved a number of statements, which will be formulated below. In those papers, the quantities u and u were not introduced separately. However, connectivity was implicitly assumed and, therefore, the theorems were formulated there and proved formally for u, remaining simultaneously valid for u . With a view to present a clear picture of the old and new results, we write u∗ instead of u and u in the cases in which the theorems are valid for both these quantities. But if a theorem is stated for one of the quantities, say, u, then this means that, as a minimum, we do not know how to extend this result to u . Thus, the following Theorems 1–11 were proved by us earlier. Theorem 1. Let p = o(1/n). Then, for all sufficiently large n ∈ N, u∗2 (n, p) = 0. Theorem 2. Let q := 1 − p = o(1/n1.5 ). Then, for all sufficiently large n ∈ N, u∗2 (n, p) = 3. Theorem 3. Let q = o(1/n), but qn1.5 → ∞. Then, for all sufficiently large n ∈ N, u∗2 (n, p) = 4. Theorem 4. Set τ (n) = pn and σ(n) = q ln n. Let τ (n) and σ(n) tend to infinity as n increases. Then, for any ε > 0, there exists an n0 such that, for n ≥ n0 , the following inequality holds: u∗2 (n, p) ≤ (2 + ε) log1/(1−p) (np). 1

Translator’s note. Here and elsewhere, Cnm stands for the binomial coefficient

n . m

MATHEMATICAL NOTES

Vol. 97 No. 5 2015

REALIZATION OF SUBGRAPHS OF A RANDOM GRAPH BY DIAMETER GRAPHS

711

√ 4

Theorem 5. Set τ (n) = p n/ ln n and σ(n) = q ln n. Let τ (n) and σ(n) tend to infinity as n increases. Then, for any ε > 0, there exists an n0 such that, for n ≥ n0 , the following inequality holds: 

4 ln p ∗ u2 (n, p) ≥ 2 − ε + log1/(1−p) (np). ln(np) Theorem 6. Let us fix a number α ∈ (0, 1/2) and set τ (n) = pnα . Suppose that, beginning with some n, 1 < τ (n) < C, where C > 0. Then, for any ε > 0, there exists an n0 such that, for n ≥ n0 , the following inequality holds: u∗2 (n, p) ≥ (2 − 2α − ε)

ln n . p

Theorem 7. Let there exist a c < 1 such that p < c/n. Then, for all sufficiently large n ∈ N, u∗3 (n, p) = 0. Theorem 8. Let q = o(1/n1.5 ). Then, for all sufficiently large n ∈ N, u∗3 (n, p) = 4. Theorem 9. Set τ (n) = pn and σ(n) = q ln n. Let τ (n) and σ(n) tend to infinity as n increases. Then, for any ε > 0, there exists an n0 such that, for n ≥ n0 , u∗3 (n, p) ≤ (2 + ε) log1/(1−p) (np). Theorem 10. Let, for any α > 0, pnα → ∞ and q ln n → ∞ as n → ∞. Then, for any ε > 0, there exists an n0 such that, for n ≥ n0 , u∗3 (n, p) ≥ (2 − ε) log1/(1−p) (np). Theorem 11. Let us fix an α ∈ (0, 1/4) and set τ (n) = pnα . Suppose that, beginning with some n, 1 < τ (n) < C, where C > 0. Then, for any ε > 0, there exists an n0 such that, for n ≥ n0 , the following inequality holds: u∗3 (n, p) ≥ (2 − 4α − ε)

ln n . p

It is seen that, under reasonable conditions on the asymptotics of the edge probability, Theorems 4 and 5 provide an asymptotics of the quantity u∗2 (n, p), and this asymptotics is of the form 2 log1/(1−p) (np). Moreover, if p tends to zero, then, under the assumptions of Theorem 5, 2 log1/(1−p) (np) ∼ 2

ln n . p

Therefore, Theorem 6 simply yields an analog of the estimate from Theorem 5, which is only worse by a constant factor, but can be used for a greater range of values of p. A similar pattern occurs in Theorems 9–11. Further, the assertions of Theorems 4 and 9 are quite identical; in Theorem 10, we have practically the same estimate as in Theorem 5, but a narrower range of admissible edge probabilities, while, in Theorem 11, and the range is narrower than in Theorem 6 and the estimate is less sharp. We have succeeded in obtaining analogs of Theorems 1–11 for any fixed d. However, beginning with d = 4, we obtain lower bounds only for ud (n, p). But the upper bounds are valid for both quantities u and u . Theorem 12. Let, for any α > 0, pnα → ∞, and let q ln n → ∞ as n → ∞. Then, for any d ≥ 4 and for any ε > 0, there exists an n0 such that, for n ≥ n0 , ud (n, p) ≥ (2 − ε) log1/(1−p) (np). MATHEMATICAL NOTES

Vol. 97

No. 5 2015

712

KOKOTKIN, RAIGORODSKII

Theorem 12 differs from Theorem 10 only in that its proof, essentially, does not require the connectivity of the subgraph. Also the analogs of Theorems 6 and 11 do not require the connectivity condition. Moreover, these analogs for d < 4 even strengthen the assertions of Theorems 6 and 11. But we repeat that this circumstance is a distinctive feature of the quantity u. Theorem 13. Let us fix an α ∈ (0, 1/d) and set τ (n) = pnα . Suppose that, beginning with some n, 1 < τ (n) < C, where C > 0. Then, for any d and any ε > 0, there exists an n0 such that, for n ≥ n0 , the following inequality holds: ud (n, p) ≥ (2 − 2α − ε)

ln n . p

As indicated above, this result is stronger than that of Theorem 11, because the range of admissible values of α is wider and 2α, not 4α, is subtracted in the estimate. However, Theorem 6 is just a simple particular case of the new Theorem 13. On the other hand, it will be seen from the proof that, for d > 2, the bound 1/d can be moved to the right up to 2/(d + 1). Let us pass to the upper bounds. They are again valid for both u, and u . Theorem 14. Let p be either a constant or an arbitrary function tending to zero as n → ∞, but bounded below by c/n, where c > 1. Then, for any d and for any ε > 0, there exists an n0 such that, for n ≥ n0 , u∗d (n, p) ≤ (2 + ε)(d + 1) log1/(1−p) (np). Theorem 14 provides an absolutely universal upper bound that can be used even in a wider range than that associated with Theorem 4. This reflects its big advantage. However, for d = 2, 3, its estimate is less sharp than the corresponding estimates obtained earlier. The following theorem removes this deficiency by narrowing the range of admissible edge probabilities. Theorem 15. Let p be a constant. Then, for any d and for any ε > 0, there exists an n0 such that, for n ≥ n0 , d ∗ log1/(1−p) (np). ud (n, p) ≤ (2 + ε) 2 Theorem 15 is in perfect agreement with Theorems 4 and 9. Nevertheless, in it, p is a constant. The point is that the proof of Theorem 15 is based on a number of delicate assertions, many of which can be generalized to cases of nonconstant probabilities only with great difficulty (cf. [16]). In addition, note that, for d ≥ 4, the lower and upper bounds begin to differ, so that it is no longer possible to find the asymptotics. At the same time, it is important to stress (and this will be seen from the proof of Theorem 15) that Theorem 15 holds for all induced subgraphs that are diameter graphs and not only for those of them whose chromatic number is d + 1. Finally, Theorems 1 and 7 can be generalized and even strengthened by the following theorem. Theorem 16. Let d ≥ 3, and let there exist a c < 2(d − 1) ln(d − 1) such that p < c/n. Then, for all sufficiently large n ∈ N, u∗d (n, p) = 0. For d = 3, Theorem 16 refines Theorem 7, because here we have the constraint c < 4 ln 2, which is weaker than the inequality c < 1. In the following section, we prove Theorems 14 and 16. In Sec. 4, we present the proofs of Theorems 12 and 13. The proof of Theorem 15 is carried out in the last, fifth, section of this paper. MATHEMATICAL NOTES

Vol. 97 No. 5 2015

REALIZATION OF SUBGRAPHS OF A RANDOM GRAPH BY DIAMETER GRAPHS

713

3. PROOFS OF THEOREMS 14 AND 16

3.1. Proof of Theorem 14 For an arbitrary graph G, let α(G) denote its independence number, i.e., the number of elements in the largest set of vertices not pairwise joined by the edges (such sets are said to be independent). Clearly, χ(G) ≥ |V |/α(G). Let us fix ε > 0. Set k = [(2 + ε)(d + 1) log1/(1−p) (np)]. It is well known (see [10]) that, for the functions p from the assertion of Theorem 14 and for any δ > 0, Pn,p (α(G) ≤ (2 + δ) log 1/(1−p) (np)) → 1,

n → ∞.

Hence, for any l ≥ k, we have  Pn,p ∀ H = (W, F ) ⊂ G : |W | = l, H = G|W , α(H) ≤ (2 + δ) log 1/(1−p) (np) → 1, n → ∞, i.e.,

Pn,p

l ∀ H = (W, F ) ⊂ G : |W | = l, H = G|W , χ(H) ≥ (2 + δ) log1/(1−p) (np)

 → 1, n → ∞.

Choosing δ sufficiently small, we obtain k > d + 1, (2 + δ) log1/(1−p) (np) whence

 Pn,p ∃H = (W, F ) ⊂ G : |W | = l, H = G|W , H is a diameter graph in Rd , χ(H) = d + 1  n → ∞. ≤ Pn,p ∃H = (W, F ) ⊂ G : |W | = l, H = G|W , χ(H) = d + 1 → 0,

Therefore, for large n, we have u∗d (n, p) ≤ k, and the theorem is proved.

3.2. Proof of Theorem 16 Here the argument is similar to that used in the previous section. This time we invoke the remarkable Achlioptas–Naor theorem (see [17]). Theorem 17. Let p = c/n, where c > 0. Let kc be the least k satisfying the inequality c < 2k ln k. Then Pn,p (χ(G) ∈ {kc , kc + 1}) → 1,

n → ∞.

In our case, c < 2(d − 1) ln(d − 1). Hence, by Theorem 17, we have Pn,p (χ(G) ≤ d) → 1,

n → ∞,

whence, for any l, the following estimate holds:  Pn,p ∃H = (W, F ) ⊂ G : |W | = l, H = G|W , H is a diameter graph in Rd , χ(H) = d + 1  n → ∞. ≤ Pn,p ∃H = (W, F ) ⊂ G : |W | = l, H = G|W , χ(H) = d + 1 → 0, Therefore, for large n, we have u∗d (n, p) = 0, and the theorem is proved. MATHEMATICAL NOTES

Vol. 97

No. 5 2015

714

KOKOTKIN, RAIGORODSKII

4. PROOFS OF THEOREMS 12 AND 13

4.1. Proof of Theorem 12 Consider a k-vertex graph H = Hd,k = K ∪ T which is the union of a clique K of dimension d + 1 and an independent set T of dimension k − (d + 1); the vertices of the subgraph T are also not joined by edges with the vertices of the graph K. We call such a graph a comet. Obviously, a comet is a diameter graph in Rd : for its realization, it suffices to put the nucleus of the comet K at the vertices of a regular simplex and its tail T inside it. Let us fix ε > 0 and set

ln n , q = 1 − p. k = (2 − ε) − ln q Obviously, under the assumptions of the theorem, k → ∞ and k ∼ (2 − ε) log 1/(1−p) (np) as n → ∞. Therefore, it suffices to show that, for a large n, ud (n, p) ≥ k. In what follows, some inequalities will hold only for n ≥ n0 , but this will not be mentioned each time. Denote by Yk the random variable equal to the number of induced k-vertex subgraphs of a random graph G that are comets with nucleus of dimension d + 1. If we prove that, for all large n, Pn,p (Yk > 0) > 1/2, then, for the same n, we obtain ud (n, p) ≥ k. We shall prove an even more stringent result Pn,p (Yk > 0) → 1. By Chebyshev’s inequality, we have Pn,p (Yk > 0) = Pn,p (Yk ≥ 1) ≥ 1 −

DYk . (MYk )2

To prove the theorem, it remains to establish two asymptotics: MYk → ∞ and M2f Yk ∼ (MYk )2 (here M2f Yk is the second factorial moment). In view of the linearity of the expectation, we have MYk = Cnk Ckd+1 pCd+1 q Ck −Cd+1 . 2

2

2

It is easy to see that since p−1 does not exceed any positive power of n, it follows that, at least 

√ ln n = o( n ). k=O p Therefore, Cnk ∼ nk /k! as n → ∞ and 2 2 2 nk d+1 Cd+1 nk 2 2 1 Ck p q Ck −Cd+1 > k pd q k /2 > d2 MYk ∼ k! k k



n k/2 q k

k

1 ≥ d2 k



npq k/2 2 ln n

k .

Since k → ∞ and d is a constant, it follows that, to prove the asymptotics MYk → ∞, it suffices to show that npq k/2 / ln n → ∞. For some ε = ε + o(1), substituting the explicit expression for k, we obtain 







npe(2−ε )(ln n/(−2 ln q)) ln q npe(− ln n)(1−ε /2) npn−(1−ε /2) nε /2 p npq k/2 = = = = . ln n ln n ln n ln n ln n 



Finally, taking into account the fact that pnε /4 → ∞, and the inequality ln n < nε /4 , we see that 



nε /4 ε /4 nε /2 p = (n p) → ∞, ln n ln n as required. Let us now verify the asymptotics M2f Yk ∼ (MYk )2 . Of course,  MYC1 ,C2 , M2f Yk = C1 ,C2

MATHEMATICAL NOTES

Vol. 97 No. 5 2015

REALIZATION OF SUBGRAPHS OF A RANDOM GRAPH BY DIAMETER GRAPHS

715

where the summation is taken over over all ordered pairs of different k-vertex comets C1 , C2 ⊂ Kn and YC1 ,C2 is the indicator of the simultaneous occurrence of the comets C1 , C2 as induced subgraphs in the random graph G. Consider the summands with V (C1 ) ∩ V (C2 ) = ∅ and the summands with V (C1 ) ∩ V (C2 ) = ∅ separately. In the first case, we obtain the expression k (Ckd+1 pCd+1 q Ck −Cd+1 )2 ∼ (Cnk Ckd+1 pCd+1 q Ck −Cd+1 )2 = (MYk )2 . S1 = Cnk Cn−k √ The last-but-one passage was made in view of k = o( n ). If we now show that  YC1 ,C2 − S1 = o((MYk )2 ), S2 = 2

2

2

2

2

2

C1 ,C2

then the proof of the theorem is concluded. For each pair of comets C1 = K1 ∪ T1 , C2 = K2 ∪ T2 , let us note the number of vertices in the intersection of their parts: 1) |K1 ∩ K2 | = k1 ∈ {0, . . . , d + 1}; 2) |T1 ∩ K2 | = k2 ∈ {0, 1}; 3) |K1 ∩ T2 | = k3 ∈ {0, 1}; 4) |T1 ∩ T2 | = k4 ∈ {0, . . . , k − (d + 1)}. In this notation,  k1 k2 k3 (Cnk Ckd+1 )(Cd+1 Ck−(d+1) Cd+1−k C k4 ) S2 = 1 k−(d+1)−k2 k−(d+1)−(k3 +k4 )

× (Cn−k

(d+1)−(k +k )

1 2 Cn−2k+(d+1)+(k )p 3 +k4 )

2 2Cd+1 −Ck2

1

q

2 2(Ck2 −Cd+1 )−Ck2

4

,

where the sum is taken over all admissible ordered collections (k1 , k2 , k3 , k4 ). Here the first parenthesis corresponds to for the first comet, the second to the common vertices of the comets, and the third to the remaining vertices of the second comet. Let us verify that S2 /S1 = o(1), and thus conclude the proof of the theorem. So we have S2  (Cn Ck = S1 k

d+1

k1 k2 k3 )(Cd+1 Ck−(d+1) Cd+1−k C k4 ) 1 k−(d+1)−k2 k (C d+1 )2 Cnk Cn−k k

k−(d+1)−(k3 +k4 )

×

(Cn−k

(d+1)−(k +k )

1 2 Cn−2k+(d+1)+(k )p 3 +k4 )

(p

2 Cd+1

q

2 2Cd+1 −Ck2

2 Ck2 −Cd+1

1

q

2 2(Ck2 −Cd+1 )−Ck2 −k2 −k3 4

.

)2

We are only concerned with the convergence to zero of the given quantity; therefore, in what follows, we shall neglect the constants in its upper bounds. The corresponding inequalities will be denoted by the symbol “”. In particular, d is a constant, and hence we use the above agreement, obtaining  (kC k4 )(Cn S2 k  S1

k−(d+1)−(k3 +k4 )

(d+1)−(k1 +k2 )

Cn

Cnk Ckd+1

)

p

−Ck2

1

q

−Ck2 −2 4

.

Let us partition the last sum into two parts: Σ1 , the part in which k4 = 0, and Σ2 , the part in which k4 ≥ 1. Let us estimate each part by the maximal summand multiplied by the number (of order k) of all summands. We have (with the optimal k1 , k2 , k3 ) Σ1  =

k2 nk−(d+1)−k3 n(d+1)−(k1 +k2 ) k! −Ck2 −2 n−k1 −k2 −k3 kd+1+k3 −Ck2 −2 1q 1q p · ≤ p kd+1 nk (k − (d + 1) − k3 )! kd−1 k2+k3 nk1 +k2 +k3

p

−Ck2

MATHEMATICAL NOTES

1

q −2 ≤

Vol. 97

k3 nk1 +k2 +k3

No. 5 2015

p

−Ck2

1

q −2 .

716

KOKOTKIN, RAIGORODSKII

Since k4 = 0, it follows that the sum k1 + k2 + k3 is nonzero, because we consider intersecting comets. 2 In addition, k1 ≤ d + 1, and hence our expression has the upper bound k3 /(npd q 2 ); using this fact and substituting the explicit expression for k, we obtain

 (2 ln n)3 2 ln n 3 1 k3 = 2 2 ≤ 2 2 )) 3+d2 → 0, 1/6 2/3 d 3+d 2 1/(2(3+d n q np q p nq (pn ) because both multipliers tend to zero. In the case k4 ≥ 1, we similarly obtain Σ2 

k2k4 +3 nk1 +k2 +k3 +k4

p

−Ck2

1

q

−Ck2 −2 4

≤



1 2

pk1 n k1

k5k4 −k42/2−2 q n k4

 =

1 2

pk1 n k1



k5 −k4 /2−2/k4 q n

k4 .

Note that the multiplier 1 2 pk1 n k1

=

1 2 (pn1/k1 )k1

tends to zero if k1 > 0, and is equal to 1 in the case k1 = 0. Therefore, to complete the proof, it suffices to verify that the expression in the last parenthesis tends to zero. Since k4 < k = (2 − ε )

ln n ln n ≤2 , − ln q p

we have 

k5 e−(2−ε )(ln n/(−2 ln q)) ln q k5 ln5 n k 5 q −k4 /2−2/k4 ≤ = ≤ 32  n nq 2 nε /2 q 2 p5 q 2 nε /2 ln5 n 1 = 32 2 ε /4 → 0, q n (pnε /20 )5 and everything is proved.

4.2. Proof of Theorem 13 Just as in Theorem 12, we consider comets with

ln n . k = (2 − 2α − ε) p Obviously, k → ∞. Moreover,



ln n k=Θ p



√ = Θ(nα ln n) = o( n ),

because α < 1/d ≤ 1/2. The bound 1/d is needed only here. In what follows, the bound 2/(d + 1) will suffice. Just as in Sec. 4.1, we must first verify that, as npq k/2 / ln n → ∞, 

n1−α −(1−α−ε /2) ln n nε /2 npq k/2 ≥ e → ∞. = ln n ln n ln n And again it remains to verify that, in the notation of Sec. 4.1, S2 /S1 → 0. Using a finer estimation technique, we obtain  kk2 +k3 +2k4 2 S2 −k12 /2 −Ck4 p  q . k +k +k +k S1 n 1 2 3 4 k4 ! Each summand can be written as the product of three factors: 2

k2 +k3 2k4 q −Ck4 k k1 /2 −k1 k . · (np ) · n nk4 k4 ! MATHEMATICAL NOTES

Vol. 97 No. 5 2015

REALIZATION OF SUBGRAPHS OF A RANDOM GRAPH BY DIAMETER GRAPHS

717

Let us fix arbitrary k1 , k2 , k3 and consider the sum of such summands over k4 (denoting them by Lk1 ,k2,k3 (k4 )). First, let k4 = 0. Then either k1 > 0 or k2 + k3 > 0 (the comets intersect). But we have k/n → 0 and npk1 /2 ≥ n · n−αk1 /2 ≥ n1−α(d+1)/2 → ∞, because α < 2/(d + 1). Hence, in any case, Lk1 ,k2 ,k3 (0) → 0. Now let k4 ≤ nα . Let us show that the quantities Lk1 ,k2 ,k3 (k4 ) decrease as functions of k4 : Lk1 ,k2 ,k3 (k4 ) n(k4 + 1) k4 n(k4 + 1) −(1+o(1))pnα n(k4 + 1) −C+o(1) = q ≥ e ≥ e → ∞. 2 2 Lk1 ,k2 ,k3 (k4 + 1) k k k2 Hence, for any k1 , k2 , k3 , the sum of the quantities Lk1 ,k2 ,k3 (k4 ) over k4 from zero to nα tends to zero, just as the first summand. There is also a portion of the sum in which k4 > nα . In this portion, we always have

2 −k4 /2 k4 −C 2 ek q k 2k4 q k4 ≤ . k 4 n k4 ! nk4 In turn, n2α (ln n)2 e(1+o(1))pk/2   ek 2 q −k4 /2  = nα−1 (ln n)2 e(1−α−ε /2) ln n = (ln n)2 n−ε /2 → 0. 1+α nk4 n Thus, for k4 > nα , each of the summands can be estimated, for example, by the quantity 2−n . Since the number of these summands is of order k, it follows that their sum also tends to zero. To summarize, for any k1 , k2 , k3 , the sum of the quantities Lk1 ,k2 ,k3 (k4 ) over k4 tends to zero. But the number of different collections of the numbers k1 , k2 , k3 is not greater than a constant, whence we also find that the whole sum tends to zero. The theorem is proved. α

5. PROOF OF THEOREM 15 The proof is rather cumbersome. Therefore, to make the exposition maximally clear, we first consider the case d = 4 and p = const, and only then, in the second subsection, we argue for the case d > 4, p = const. Finally, in Sec. 5.3, we discuss how to extend the results obtained to slowly decreasing functions of p.

5.1. The Case d = 4, p = const Let us fix an arbitrary ε ∈ (0, 2) and set   ln n . k = k(n) = (4 + ε) − ln q Denote by cl(G, r) the number of r-cliques in the given graph G. It is known (see [16]) that there exist numbers δ > 0 and n0 ∈ N such that, for any n ≥ n0 and any n-vertex diameter graph G in R4 , the following inequality holds: cl(G, 3) ≤ n3−δ , i.e., in any sufficiently large diameter graph in four-dimensional space, the number of triangles is considerably less than in the complete graph. We wish to prove that u∗4 (n, p) ≤ k. To do this, it suffices to show that, only with probability tending to zero, does there exist a induced k-vertex subgraph in G(n, p) in which the number of triangles is at most k 3−δ , i.e., P(∃Hk ⊂ G(n, p) : cl(Hk , 3) ≤ k3−δ ) → 0. We shall gradually estimate this quantity from above. Of course, P(∃Hk ⊂ G(n, p) : cl(Hk , 3) ≤ k3−δ ) ≤ Cnk P(cl(G(k, p), 3) ≤ k3−δ ). ¨ theorem (see [18], [19]). Further, we shall use the following particular case of the Rodl MATHEMATICAL NOTES

Vol. 97

No. 5 2015

718

KOKOTKIN, RAIGORODSKII

Theorem 18. Fix an arbitrary number t and consider a k-vertex complete graph Kk . Denote by Sis(k, t) an arbitrary family (of maximal cardinality) of subgraphs of the graph Kk isomorphic to Kt in which no two subgraphs have common edges. Then, as k → ∞, a := |Sis(k, t)| ∼

Ck2 k2 = (1 + o(1)). t(t − 1) Ct2

Let us now return to our random graph G(k, p). Let σ be a permutation of the set of its vertices. Let F3 (σ, G(k, p), t) be the number of triangles in G(k, p) such that, in the permutation σ, each of them is a subgraph in exactly one clique Kt from Sis(k, t). In [16], the following result was obtained. Theorem 19. If Hk is a k-vertex graph and, in it, the number of triangles is at most k3−δ , then, for any fixed t, there exists a permutation σ of the set of its vertices such that F3 (σ, Hk , t) ≤ k2−δ (t − 2)(1 + ζt (k)), where ζt (k) = o(1) as k → ∞. Let us denote z = k2−δ (t − 2)(1 + ζt (k)) and continue to estimate the probability as follows:

  k 3−δ k (F3 (σ, G(k, p), t) ≤ z) Cn P(cl(G(k, p), 3) ≤ k ) ≤ Cn P σ

≤

Cnk k!P(F3 (e, G(k, p), t)

≤ z) =

Cnk k!

z 

P(F3 (e, G(k, p), t) = i),

i=0

where e is the identity permutation. Now denote by P3 (t, p) the probability that there are no triangles in the random graph G(t, p). Then Cnk k!

z 

P(F3 (e, G(k, p), t) = i)) ≤ Cnk k!

i=0

i z  

Caj (P3 (t, p))a−j (1 − P3 (t, p))j .

i=0 j=0

Estimating this quantity by the number of summands multiplied by the the largest one, we obtain Cnk k!

z  i 

Caj (P3 (t, p))a−j (1 − P3 (t, p))j ≤ nk (z + 1)2 az (P3 (t, p))a−z = nk (P3 (t, p))a(1+o(1)) . (1)

i=0 j=0

The last equality holds, because, first, z = o(a) as k → ∞, and hence a − z = a(1 + o(1)), and, second, 2

(z + 1)2 az = eo(k ) ,

(P3 (t, p))a(1+o(1)) ≤ e−Ω(k ) . 2

Let us estimate the quantity P3 (t, p). To do this, we shall use the following theorem from [20]. Theorem 20. If p satisfies the constraints of Theorem 15, then ln(P3 (t, p)) = (1 + ξ(t)) ln(P(the graph G(t, p) is two-partite)), where ξ(t) → 0 as t → ∞. We now pass to the estimate of the probability that the random t-vertex graph G = (V, E) is two-partite: t 1  P(G), P(the graph G(t, p) is two-partite) = 2 m=0 W

G

where the first summation is over the cardinality of the first part (which defines the cardinality of the second part), the second summation is over over all parts of cardinality m, and the third summation is MATHEMATICAL NOTES

Vol. 97 No. 5 2015

REALIZATION OF SUBGRAPHS OF A RANDOM GRAPH BY DIAMETER GRAPHS

719

over all two-partite graphs G = (W  (V \ W ), E). Let l be the number of edges between the parts. Then t t   1  P(G) ≤ 2 m=0 W

m=0 W

G



m(t−m) 2

2

l q Cm +Ct−m Cm(t−m) pl q m(t−m)−l .

l=0

2 +C 2 Cm t−m

The multiplier q is independent of l, we take it out of the sum, transforming the formula into the Newton binomial formula for (p + q)m(t−m) = 1, and hence the whole expression is estimated from above by the quantity t  

2

2

q Cm +Ct−m =

m=0 W

t 

2

2

Ctm q Cm +Ct−m .

m=0

In what follows, we shall choose t in a suitable way; therefore, we can now assume that t is even. In this case, the maximal summand is the one in which m = t/2. Indeed, for such an m, the binomial coefficient is also the greatest, and the sum in the exponent of q is minimal in view of the fact that the binomial coefficient is convex. The number of summands in our sum is t + 1, and hence, it can be estimated from above by the expression t 

2

2

Ctm q Cm +Ct−m ≤ (t + 1)

m=0

t! 2C 2 · q t/2 . 2 ((t/2)!)

Further, using trivial estimates, we obtain 2 te(t/e)t t! 2Ct/2 · q ≤ (t + 1) q t(t−2)/4 ≤ t2 2t q t(t−2)/4 ((t/2)!)2 (e(t/(2e))t/2 )2     t(t − 2) t(t − 2) ln q ≤ exp 4t + ln q = exp 2 ln t + t ln 2 + 4 4

  16 t(t − 2) (− ln q) −1 . = exp 4 (t − 2)(− ln q)

(t + 1)

Now it is time to choose the constant t. Set it equal to any even number not less than      24 192 + 1 ,2 +1 max 2 (− ln q)ε ε  and such that the function ξ(t) from Theorem 20 satisfies the inequality 1 + ξ(t) ≥ 1 − ε/24 . In this case, at least, 

192 +1 , t≥2 (− ln q)ε and the expression in parentheses can be estimated as 16(− ln q)ε ε 16 −1≤ −1= − 1. (t − 2)(− ln q) 384(− ln q) 24 Because of this, we finally obtain



P(the graph G(t, p) is two-partite) ≤ exp

  ε t(t − 2) ln q . 1− 24 4

Thus, we have obtained an upper bound for the probability of the random graph G(t, p) to be two-partite, and hence also the probability that G(t, p) does not contain any triangles. Returning to our estimate (1) and using Theorem 20, we can write nk (P3 (t, p))a(1+o(1)) = exp{k ln n + a(1 + o(1)) ln P3 (t, p)} MATHEMATICAL NOTES

Vol. 97

No. 5 2015

720

KOKOTKIN, RAIGORODSKII

  ε t(t − 2) k2 (1 + o(1))(1 + ξ(t)) 1 − (− ln q) t(t − 1) 24 4

   ε 3/2 t(t − 2) k2 (1 + o(1)) 1 − (− ln q) . ≤ exp k ln n − t(t − 1) 24 4  ≤ exp k ln n −

Here we have substituted the explicit expression for a. In it, o(1) is a function of k. Since k increases as n → ∞, it follows that an n such that 1 + o(1) ≥ 1 − ε/24 can be chosen, and hence the exponential does not exceed

  

ε 2 t(t − 2) k 1− (− ln q) . exp k ln n 1 − (ln n)t(t − 1) 24 4 We must verify that this exponential tends to zero as n increases. To do this, it suffices to prove that, e.g.,

 k ε 2 t(t − 2) ε 1− (− ln q) > 1 + . (ln n)t(t − 1) 24 4 16 We substitute the explicit expression for k:



 ε 2 t(t − 2) (4 + ε) ln n ε 2t − 2 k 1− (− ln q) = 1− (− ln q) (ln n)t(t − 1) 24 4 4(− ln q)(ln n) 24 t − 1 





ε 2 1 ε 1− . 1− = 1+ 4 24 t−1 Recall that t ≥ 24/ε + 1, and hence 1 − 1/(t − 1) ≥ 1 − ε/24. Finally, we have 

 





ε 3 ε ε ε2 ε ε ε 1− 1− =1+ − >1+ , ≥ 1+ 1+ 4 24 4 8 8 32 16 because ε < 2. The theorem is proved. Note that, in the course of calculations, we proved the following statement, which is of interest in itself. Theorem 21. If p = const, then, for any δ > 0, P(the number the triangles in G(k, p) is less than k3−δ ) < e−Ω(k ) , 2

k → ∞.

5.2. The Case d > 4, p = const Let us fix an arbitrary ε ∈ (0, 2), denote s = [d/2] + 1, and set   d ln n . k = k(n) = (2 + ε) 2 − ln q It is known (see [16]) that there exist numbers δ > 0 and n0 ∈ N such that, for any n ≥ n0 and any n-vertex diameter graph G in Rd , the following inequality holds: cl(G, s) ≤ ns−δ , i.e., in any sufficiently large diameter graph in d-dimensional space, the number of s-cliques is strongly less than in the complete graph. Note that, for d = 4, we have s = 3, and this is in agreement with the result we used in the previous section. Just as in the previous section, the proof of the estimate u∗d (n, p) ≤ k can be reduced to the verification of the fact that the quantity Cnk P(cl(G(k, p), s) ≤ ks−δ ) MATHEMATICAL NOTES

Vol. 97 No. 5 2015

REALIZATION OF SUBGRAPHS OF A RANDOM GRAPH BY DIAMETER GRAPHS

721

tends to zero. Just as above, we consider the system Sis(k, t) (the quantity t will be chosen in what follows). As before, Theorem 18 implies the equality k2 (1 + o(1)). t(t − 1)

a := |Sis(k, t)| =

Let Fs (σ, G(k, p), t) be the number of s-cliques in G(k, p) such that, in the permutation σ, each of them is a subclique in exactly one clique Kt from Sis(k, t). Theorem 22, which was essentially proved in [16], serves as the analog of Theorem 19. Theorem 22. If Hk is a k-vertex graph and, in it, the number of s-cliques does not exceed ks−δ , then, for any fixed t, there exists a permutation σ of the set of its vertices such that Fs (σ, Hk , t) ≤ k2−δ

(t − 2)! (1 + ζt,s (k)), (t − s)!

where ζt,s (k) = o(1) as k → ∞. In view of Theorem 22, the calculations preceding inequality (1) can be repeated almost word for word. Only we must introduce the quantity Ps (t, p), the probability that, in G(t, p), there are no s-cliques: Cnk P(cl(G(k, p), s) ≤ ks−δ ) ≤ nk (Ps (t, p))a(1+o(1)) .

(2)

Theorem 20 also admits a generalization (see [20]). Theorem 23. If p obeys the constraints of Theorem 15, then ln(Ps (t, p)) = (1 + ξs (t)) ln(P(the graph G(t, p) (s − 1)-partite)), where ξs (t) → 0 as t → ∞. We now try to estimate the probability that the t-vertex random graph G = (V, E) is s − 1-partite:    1 P(G), P(the graph G(t, p) is (s − 1)-partite) = (s − 1)! (m1 ,...,ms−1 ) W1 ,...,Ws−1

G

where the first summation is over all possible cardinalities of the corresponding parts, i.e., mi = |Wi | and s−1 i=1 mi = t, the second summation is over all parts of the chosen cardinality, and the third summation is over all (s − 1)-partite graphs G = (W1  · · ·  Ws−1 , E). Now, denote, for all i, j ∈ {1, . . . , s − 1}, the number of edges between the corresponding parts Wi and Wj by li,j ∈ {0, . . . , mi mj }. Then our sum takes the form  2     1 l q Cmr Cmi,ji mj pli,j q mi mj −li,j . (s − 1)! (m1 ,...,ms−1 ) W1 ,...,Ws−1 (l1,2 ,...,ls−2,s−1 )



i,j

2

The multiplier q Cmr is independent of li,j ; we take it out of the sum and then. since all the summands are positive, we can estimate the sum of the products from above by the product of the sums:  2     1 l q Cmr Cmi,ji mj pli,j q mi mj −li,j (s − 1)! m W1 ,...,Ws−1

≤





l



q

2 Cm r

m W1 ,...,Ws−1

=





 

Cmi,ji mj pli,j q mi mj −li,j l

i,j li,j =0



q

m W1 ,...,Ws−1

i,j

mi mj

2 Cm r

 i,j

1=

 m

 2 t! q Cmr . m1 !m2 ! · · · · · ms−1 !

The last expression contains a polynomial coefficient, which is the number of ways to partition the vertex set of cardinality t into subsets of given cardinality. Let t be divisible by s − 1. In this case, the maximal MATHEMATICAL NOTES

Vol. 97

No. 5 2015

722

KOKOTKIN, RAIGORODSKII

summand is the one in which mr = t/(s −1) for all r. Indeed, for such values of mr , the polynomial 2 is minimal because the binomial coefficient is convex. coefficient is also the greatest, and the sum Cm r s−2 The number of summands in our sum is Ct+s−2 , and hence it can be estimated from above by the expression  2  2 t! t! (s−1)Ct/(s−1) s−2 q Cmr ≤ Ct+s−2 ·q . s−1 m1 !m2 ! · · · · · ms−1 ! ((t/(s − 1))!) m Further, using the trivial estimates and the assumption t > s, we obtain 2 t! (s−1)Ct/(s−1) · q ((t/(s − 1))!)s−1 te(t/e)t ≤ (t + s)s−2 q t(t−s+1)/(2(s−1)) (e(t/(e(s − 1)))t/(s−1) )s−1

s−2 Ct+s−2

≤ (t + s)s−1 (s − 1)t q t(t−s+1)/(2(s−1)) ≤ (2t)s−1 (s − 1)t q t(t−s+1)/(2(s−1))   t(t − s + 1) ln q = exp (s − 1) ln(2t) + t ln(s − 1) + 2(s − 1)   t(t − s + 1) (− ln q) ≤ exp 3(s − 1)t − 2(s − 1)

  6(s − 1)2 t(t − s + 1)(− ln q) −1 . ≤ exp 2(s − 1) (t − s + 1)(− ln q) Let



144(s − 1) +1 . t ≥ (s − 1) (− ln q)(ε)

Then 6(s − 1)2 (− ln q)ε ε 6(s − 1)2 −1≤ −1= − 1. 2 (t − s + 1)(− ln q) 144(s − 1) (− ln q) 24 In view of this result, we can write



P(the graph G(t, p) (s − 1)-partite) ≤ exp

  ε t(t − s + 1) ln q . 1− 24 2(s − 1)

Thus, we have found an upper bound for the probability that the random graph G(t, p) is (s − 1)-partite, and hence also the probability that there is no Ks in G(t, p). Returning to our estimate (2) and using Theorem 23, we obtain nk (Ps (t, p))a(1+o(1)) = exp{k ln n + a(1 + o(1)) ln Ps (t, p)}  

 ε t(t − s + 1) k2 (1 + o(1))(1 + ξs (t)) 1 − (− ln q) . ≤ exp k ln n − t(t − 1) 24 2(s − 1)  Again, we can also assume that 1 + ξs (t) ≥ 1 − ε/24 and, beginning with some n, we have  1 + o(1) ≥ 1 − ε/24 and, therefore, the exponential does not exceed the expression

  

ε 2 t(t − s + 1) k 1− (− ln q) . exp k ln n 1 − (ln n)t(t − 1) 24 2(s − 1) Now, to prove the theorem, it suffices to prove that

 ε 2 t(t − s + 1) ε k 1− (− ln q) > 1 + . (ln n)t(t − 1) 24 2(s − 1) 16 MATHEMATICAL NOTES

Vol. 97 No. 5 2015

REALIZATION OF SUBGRAPHS OF A RANDOM GRAPH BY DIAMETER GRAPHS

723

We substitute the expression for k, obtaining

 k ε 2 t(t − s + 1) 1− (− ln q) (ln n)t(t − 1) 24 2(s − 1)

 ε 2 t(t − s + 1) (2 + ε)(s − 1)(ln n) 1− (− ln q) ≥ (− ln q)(ln n)t(t − 1) 24 2(s − 1) 









ε 2 ε ε 3 ε s−2 ε 1− ≥ 1+ 1− , >1+ 1− = 1+ 2 24 t−1 2 24 16 because t ≥ 24(s − 2)/ε + 1, and ε < 2. The theorem is proved. Just as in the previous section, we note that, in the course of our calculations, we have proved the following statement, which is of interest in itself. Theorem 24. If p = const and d = const, then, for s = [d/2] + 1 and any δ > 0, P(the number of s-cliques in G(k, p) is less than ks−δ ) < e−Ω(k ) , 2

k → ∞.

5.3. The Problem Involving the Case p → 0 It is seen from the proofs given in the previous sections that one of the main conditions for their successful termination is the condition that the quantity t does not tend to infinity. While, in Theorems 19 and 22, one can dispense easily with this condition (cf. [16]), the situation with Theorem 18, is much more complicated. However, there is a hope that one may circumvent this difficulty. Namely, Kuzyurin ¨ theorem in [21]. proved the following strengthened Rodl √ Theorem 25. Let t = t(k) → ∞ as k → ∞, but let t < c k for some constant c < 1. Then |Sis(k, t)| ∼

Ck2 k2 (1 + o(1)). = t(t − 1) Ct2

We have several constraints on the value of t. First, t  1/p, and if p → 0, then √ t is not a constant. Nevertheless, in view√of Theorem 25, it suffices to have the asymptotics 1/p = o( k ). This is equivalent to the convergence p k → ∞, i.e., to   ln n → ∞ ⇐⇒ p ln n → ∞ ⇐⇒ p ln n → ∞. p p This seems to be a success, but,  unfortunately, the condition t  1/p is not the only one. There is also the requirement 1 + ξs (t) ≥ 1 − ε/24 . The quantity ξs (t) appears in Theorem 23 and, of course, it, in general, depends on p. When p is a constant, this dependence, just as the dependence on s, is of no consequence. However, as p → 0, we must examine all the details. From [20], we could not obtain an explicit dependence on p. Apparently, under the condition p ln n → ∞, this dependence is small and, as before, t will satisfy Theorem 25. However, we were unable to verify this and state it as a conjecture. It is not clear at all what the case p ln n = O(1) involves. ACKNOWLEDGMENTS The authors wish to express gratitude to the referee for valuable remarks and the reference to the paper in ArXiv that can be useful for solving the problem indicated in the last section. This work was supported by the Russian Foundation for Basic Research (grant no. 12-01-00683), by the Grant of the President of the Russian Federation MD-6277.2013.1, and by the program “Leading Scientific Schools” (grant no. NSh-2519.2012.1). MATHEMATICAL NOTES

Vol. 97

No. 5 2015

724

KOKOTKIN, RAIGORODSKII

REFERENCES ¨ ¨ ¨ 1. K. Borsuk, “Drei Satze uber die n-dimensionale euklidische Sphare,” Fundam. Math. 20, 177–190 (1933). 2. A. M. Raigorodskii, “On the dimension in Borsuk’s problem,” Uspekhi Mat. Nauk 52 (6), 181–182 (1997) [Russian Math. Surveys 52 (6), 1324–1325 (1997)]. 3. A. M. Raigorodskii, “On a bound in Borsuk’s problem,” Uspekhi Mat. Nauk 54 (2), 185–186 (1999) [Russian Math. Surveys 54 (2), 453–454 (1999)]. 4. A. M. Raigorodskii, “Borsuk’s problem and the chromatic numbers of some metric spaces,” Uspekhi Mat. Nauk 56 (1), 107–146 (2001) [Russian Math. Surveys 56 (1), 103–139 (2001)]. 5. A. M. Raigorodskii, “Counterexamples to Borsuk’s conjecture on spheres of small radius,” Dokl. Ross. Akad. Nauk 434 (2), 161–163 (2010) [Dokl. Math. 82 (2), 719–721 (2010)]. 6. A. M. Raigorodskii, “Coloring distance graphs and diameter graphs,” in Thirty Essays on Geometric Graph Theory (Springer, New York, 2013), pp. 429–460. 7. A. M. Raigorodskii, “On the chromatic numbers of spheres in Rn ,” Combinatorica 32 (1), 111–123 (2012). 8. V. Boltyanski, H. Martini, and P. S. Soltan, Excursions into Combinatorial Geometry, in Universitext (Springer-Verlag, Berlin, 1997). ˇ 9. J. Matousek, Using the Borsuk–Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry, in Universitext (Springer-Verlag, Berlin, 2003). ´ Random Graphs, in Cambridge Stud. Adv. Math. (Cambridge Univ. Press, Cambridge, 2001), 10. B. Bollobas, Vol. 73. 11. A. A. Kokotkin and A. M. Raigorodskii, “On the realization of random graphs by diameter graphs,” Trudy MFTI 4 (1), 19–28 (2012). 12. A. A. Kokotkin and A. M. Raigorodskii, “On the realization of subgraphs of a random graph by diameter graphs on the semiaxis and in space,” Trudy MFTI 6 (2), 44–60 (2014). ˝ 13. A. M. Raigorodskii, “The Nelson–Erdos–Hadwiger problem and a space realization of a random graph,” Uspekhi Mat. Nauk 61 (4 (370)), 195–196 (2006) [Russian Math. Surveys 61 (4), 783–785 (2006)]. 14. S. V. Nagaeva and A. M. Raigorodskii, “On the embedding of finite distance graphs with large chromatic number in random graphs,” in Itogi Nauki i Tekhniki. Ser. Sovrem. Mat. VINITI, Moscow, 2009, Vol. 62, pp. 47–66 [in Russian]. 15. S. V. Nagaeva and A. M. Raigorodskii, “On the realization of random graphs as distance graphs in spaces of fixed dimension,” Dokl. Ross. Akad. Nauk 424 (3), 315–317 (2009) [Dokl. Math. 79 (1), 63–65 (2009)]. 16. A. B. Kupavskii, A. M. Raigorodskii, and M. V. Titova, “New bounds for the distance Ramsey number,” Discrete Math. 313 (22), 2566–2574 (2013). 17. D. Achlioptas and A. Naor, “The two possible values of the chromatic number of a random graph,” Ann. of Math. (2) 162 (3), 1335–1351 (2005). ¨ 18. V. Rodl, “On a packing and covering problem,” Eur. J. Combin. 6 (1), 69–78 (1985). 19. N. Alon and J. H. Spencer, Probabilistic Method, in Wiley-Intersci. Ser. Discrete Math. Optim. (John Wiley and Sons, New York, 2000). ¨ 20. H. J. Promel and A. Steger, “On the asymptotic structure of sparse triangle free graphs,” J. Graph Theory 21 (2), 137–151 (1996). 21. N. N. Kuzjurin (Kuzyurin), “On the difference between asymptotically good packings and coverings,” Eur. J. Combin. 16 (1), 35–40 (1995).

MATHEMATICAL NOTES

Vol. 97 No. 5 2015