SERIE A — MATHEMATIK

The local density of triangle-free graphs

Stephan Brandt*

Preprint No. A 95–14 June 1995

Abstract

How dense can every induced subgraph of ⌊αn⌋ vertices (0 < α ≤ 1) of a triangle-free graph of order n be? Tools will be developed to estimate the local density of graphs, based on the spectrum of the graph and on a fractional viewpoint. These tools are used to refute a conjecture of Erdős et.al. about the local density of triangle-free graphs for a certain range of α, by estimating the local density of the Higman-Sims graph. Moreover, the local density will be related to a long-standing conjecture of Erdős, saying that every triangle-free graph can be made bipartite by the omission of at most n^{2}/25 edges. Finally, a conjecture about the spectrum of regular triangle-free graphs is raised, which can be seen as a common generalization of the two previous questions.

*FB Mathematik, Freie Universität Berlin, Graduiertenkolleg ‘Alg. Diskr. Mathematik’, Arnimallee 2–6, 14195 Berlin, Germany

e-mail: brandt@math.fu-berlin.de

Supported by Deutsche Forschungsgemeinschaft, Grant We 1265

1 Introduction and main results

It is an easy exercise to verify that every graph on n vertices can be made bipartite by the omission of \binom{⌈n/2⌉}{2} + \binom{⌊n/2⌋}{2} < n^{2}/4 edges. According to an old conjecture of Erdős (see Erdős [4]) the deletion of n^{2}/25 edges suffices to make a triangle-free graph bipartite.

Conjecture 1 (Erdős) Every triangle-free graph can be made bipartite by the omission of at most n^{2}/25 edges.

This would be best possible, as that many edges are needed to make the 5-cycle bipartite (the lexicographic product C_{5}[\overline{K}_{r}] is an infinite family for which this bound is tight). The current record is that the deletion of n^{2}/18 edges suffices to make triangle-free graphs bipartite [5].

How dense can a triangle-free graph be locally? More precisely, our objective is to determine the smallest real number β(α) with the following property:

If G is a graph of order n where every subset of ⌊αn⌋ vertices spans more than β(α)n^{2} edges, then G contains a triangle.

Generalizing an older question of Erdős [4] the following conjecture was raised.

Conjecture 2 (Erdős, Faudree, Rousseau and Schelp [6])

β(α) = \{ \begin{matrix}(2α − 1)/4 if & 17/30 ≤ α ≤ 1, \\ (5α − 2)/25 if & 53/120 ≤ α < 17/30. \end{matrix}

Krivelevich [8] verified Conjecture 2 for α ≥ 3/5. We will refute Conjecture 2 for .442 ≃ 53/120 ≤ α < 474/1000 by showing

Theorem 1

β(α) ≥ (1000α − 326)/10000 if α ≤ 1.

It is easily checked that (1000α − 326)/10000 > (5α − 2)/25 if α < 474/1000. Theorem 1 is proved by estimating the local density of the Higman-Sims graph [7] via its eigenvalues. Although the estimation is probably not best possible, the Higman-Sims graph is definitely no counterexample to Conjecture 2 at α = 1/2. Using a (not verified) computer program we have refuted Conjecture 2 for α < 2062/4305 ≃ .479, but we perform here the disproof only for α < .474.

The case α = 1/2 of Conjecture 2 is of particular interest. Slightly generalizing an observation due to Krivelevich [8] we will show, that the truth of Conjecture 2 for α = 1/2 verifies Conjecture 1, restricted to regular graphs. It is conceivable that the extremal triangle-free graphs for both problems are regular or almost regular. If both conjectures were true this would indeed be the case.

As we will see in the sequel, the precise determination of β(α) might be very hard, since it depends heavily on the individual structure of certain triangle-free graphs. Therefore we offer a weaker conjecture which might have a closer relation to common features of triangle-free graphs.

Let λ_{1} ≥ λ_{2} ≥ … ≥ λ_{n} be the spectrum of a graph G of order n. Call the function

Ξ(G) = (λ_{1} + λ_{n})/n  (1)

the spectral ratio. The investigation of the second largest and the smallest eigenvalue of a graph has attracted considerable attention in the last years, as a graph is a good expander and has pseudo-random properties if the absolute value of both is small (for a survey see [1, Section 9.2]). If the spectral ratio of a graph is large, this means that the graph is dense and its least eigenvalue is relatively large at the same time. For triangle-free graphs (or, more generally, for graphs with bounded clique number) these concepts seem to be opposed.

Conjecture 3 If G is a regular triangle-free graph then

Ξ(G) ≤ 4/25.

It will be shown that Conjecture 1 holding for regular graphs would imply Conjecture 3. As the truth of Conjecture 2 for α = 1/2 verifies Conjecture 1 restricted to regular graphs, Conjecture 3 can be viewed as a common generalization of the two former conjectures. In contrast to the to other conjectures, the bound of Conjecture 3 is perhaps not tight. The largest spectral ratio of a triangle-free graph known to the author is 7/50, attained by the Higman-Sims graph. Anyway, it would be hazardous speculation to conjecture that this bound is optimal.

Generalizing this concept it might be worthwhile to determine the function

ξ(s) = sup_{G} Ξ(G),

where the supremum extends over all regular graphs G which do not contain K_{s+1}. It is not difficult to obtain the following estimates:

Theorem 2

.14 ≤ ξ(2) ≤ 3 − 2\sqrt{2} ≃ .1715
(s − 2)/s ≤ ξ(s) < (s − 2)/(s − 1) for s ≥ 3.

If another conjecture of Erdős would hold, saying that every K_{4}-free graph can be made bipartite by the omission of at most n^{2}/9 edges (see [5]), then ξ(3) ≤ 4/9 improving our upper bound of 1/2 for s = 3.

2 Fractional subgraphs

For a finite, simple, and undirected graph G let V (G) denote the vertex set and E(G) the edge set. Their cardinalities, the order and size of G, are |G| and e(G), respectively. For a vertex v ∈ V (G) and a subset V′ ⊆ V (G) the neighborhood N_{V′}(v) is the set of neighbors of v in V′, and if V′ = V (G) we simply write N(v). By ⟨V′⟩ we denote the subgraph of G induced by V′ and if a graph H is isomorphic to an induced subgraph of G we write H ≤ G.

Our aim is to estimate the function

Ψ(G, k) = min{e(H) : |H| = k, H ≤ G}.

This function can be made continuous in a natural way by allowing subgraphs to have fractional parts of vertices. The density of these fractional subgraphs can be reinterpreted as limits of the (integral) subgraph density of lexicographic products G[\overline{K_{r}}]. It should be mentioned that several of these concepts are implicitly used by Krivelevich [8].

Let G be a graph and w : V (G) → [0, 1] be a real-valued function, assigning a weight w(x) = w_{x} to each vertex x. We call the tuple (G, w) a fractional subgraph of G, and we define the order of (G, w) by

|(G, w)| = ∑_{x∈V (G)} w_{x},

and the size (number of edges) by

e(G, w) = ∑_{xy∈E(G)} w_{x}w_{y}.

Note that if all weights are integral, then the order and size of (G, w) correspond to the order and size of the subgraph induced by the vertices of weight 1.

Proposition 1 Let G be a graph of order n and let Ψ(G, αn) be the smallest size of a fractional subgraph of order αn (0 ≤ α ≤ 1). Then G contains a fractional subgraph (G, w) of order αn and size Ψ(G, αn), where n − 1 vertices have integral weights.

Proof. Assume, to the contrary, that (G, w) is a fractional subgraph of order αn and size Ψ(G, αn) where two vertices x and y have fractional weights. We will show that we can change the weights of x and y to make one of their weights integral, without changing the order and without increasing the size. This, indeed, implies that in a fractional subgraph of size Ψ(G, αn) with the largest number of integral vertices, the weights of all but at most one vertices are integral.

For a vertex v define the fractional degree by d(u) = ∑_{v∈N(u)} w_{v}. We may assume that d(x) − w_{y} ≤ d(y) − w_{x}. Let ε = min(1 − w_{x}, w_{y}). Certainly, (G, w′) where w′_{x} = w_{x} + ε and w′_{y} = w_{y} − ε and w′ = w otherwise, is a fractional subgraph of the same order as (G, w), where x or y has integral weight. Moreover, e(G, w′) = e(G, w) − ε(d(y) − w_{x}) + ε(d(x) − w_{y}) − w_{x}w_{y} + (w_{x} + ε)(w_{y} − ε) ≤ e(G, w), which completes the proof. □

So looking for fractional subgraphs with small density we can restrict our attention to (integral) induced subgraphs, where just one suitable vertex is chosen fractionally.

Define the local density function of G by β(G, α) = Ψ(G, αn)/n^{2}. We can express β(G, α) in terms of the integral subgraph density of lexicographic products of G with \overline{K}_{r}. Recall that the lexicographic product G[H] has vertex set V (G) × V (H) and (u, x) and (v, y) are adjacent, if and only if uv ∈ E(G) or u = v and xy ∈ E(H).

Proposition 2 If G is a graph of order n, then

β(G, α) = sup_{r→∞} Ψ(G[\overline{K}_{r}], ⌊αrn⌋)/(rn)^{2}.

Proof. For integers k and r let H be an induced subgraph of G[\overline{K}_{r}] of order k. For a vertex u ∈ V (G) let s_{u} be the number of vertices (u, x), x ∈ V (\overline{K}_{r}), contained in H. Then the density e(H)/(rn)^{2} equals the density e(G, w)/n^{2} of (G, w), where w_{u} = s_{u}/r. This follows from the fact that the contribution of an edge uv in E(G) to the density of (G, w) equals the contribution of all the edges (u, x)(v, y) ∈ E(H) to the density of H.

On the other hand, by Proposition 1 there is a fractional subgraph of G of order k/r and size Ψ(G, k/r) with at most one fractional vertex, so Ψ(G[\overline{K}_{r}], k)/(rn)^{2} = β(G, k/rn). As β(G, α) is continuous and ⌊αrn⌋/rn → α for r → ∞ we get

β(G, α) = sup_{r→∞} Ψ(G[\overline{K}_{r}], ⌊αrn⌋)/(rn)^{2}.

□

In particular, we have

β(α) = sup_{G triangle-free} β(G, α).

The original form of Conjecture 2 in [6] had the additional requirement of the order n being sufficiently large, and in [8] this requirement was given globally throughout the paper. Concerning the investigation of β(α) this restriction is not necessary. Any small order counterexample G would give rise to an infinite sequence of counterexamples G[\overline{K}_{r}], r ∈ ℕ, by Proposition 2.

3 Local density via eigenvalues

As it appears to be difficult to determine the exact minimum density of subgraphs of larger order graphs we need tools that provide reasonable estimates. For regular graphs we get an estimate from the least eigenvalue of the graph. Let λ_{1} ≥ λ_{2} ≥ … ≥ λ_{n} be the spectrum of an r-regular graph G. Then λ_{1} = r and λ_{n} ≥ −r with equality if and only if G is bipartite.

Theorem 3 (Bussemaker, Cvetković, Seidel [2]) Let G be an r-regular graph of order n with least eigenvalue λ_{n} and let k be an integer satisfying 0 ≤ k ≤ n. Then

Ψ(G, k) ≥ k(kr + (n − k)λ_{n})/2n.

Note that for k = n/2, we get Ψ(G, k) ≥ \frac{n^{2}}{8} Ξ(G). The following lemma will bound the size of a fractional subgraph from below based on values at consecutive integral points.

Lemma 1 If k is an integer and t a real number satisfying 0 ≤ k ≤ t ≤ k + 1 ≤ n then for every graph G of order n > k

Ψ(G, t) ≥ (t − k)Ψ(G, k + 1) + (k + 1 − t)Ψ(G, k).

Proof. Let (G, w) be a fractional subgraph of order t and size Ψ(G, t), where all but possibly one vertex u have integral weights. Such a fractional subgraph exists by Proposition 1. If t = k or t = k+1 then the result is an immediate consequence. So assume k < t < k+1 whence 0 < w_{u} < 1. Let V′ ⊂ V (G) be the subset of vertices of weight > 0. As e(⟨V′ \ {u}⟩) ≥ Ψ(G, k) and e(⟨V′⟩) ≥ Ψ(G, k + 1) and e(G, w) = e(⟨V′ \ {u}⟩) + w_{u}|N_{V′}(u)| = (t − k)e(⟨V′⟩) + (k + 1 − t)e(⟨V′ \ {u}⟩) the result immediately follows. □

More precisely, the function is concave between consecutive integral points.

Next we estimate the local density of the Higman-Sims graph [7] (denoted H_{100}). Proof of Theorem 1. It is well-known (see e.g. [3, Chapter 8]) that the Higman-Sims graph H_{100} is 22-regular on 100 vertices, and its least eigenvalue is −8. So we obtain by Theorem 3 that

Ψ(H_{100}, k) ≥ ⌈k(22k − 8(100 − k))/200⌉ = ⌈3k^{2}/20⌉ − 4k  (2)

for 0 ≤ k ≤ 100. It is easy to check that 10k − 326 ≤ ⌈3k^{2}/20⌉ − 4k for every integer k with 0 ≤ k ≤ 100. Therefore, by Lemma 1

β(α) ≥ β(H_{100}, α) ≥ (1000α − 326)/10000.

□

We conclude this section with the simple proof of Theorem 2. Proof of Theorem 2. The lower bounds are obtained from the Higman-Sims graph for s = 2 and for s ≥ 3 from K_{s}.

For the upper bound of ξ(2) let G be an r-regular triangle-free graph of order n. We have 0 = Ψ(G, r) ≥ r(r^{2} + (n − r)λ_{n})/2n by Theorem 3 as the neighborhood of every vertex forms an independent set. We get λ_{n} ≤ −r^{2}/(n − r) which implies Ξ(G) = (r + λ_{n})/n ≤ r(1 − \frac{r}{n−r})/n. Replacing r = αn we get Ξ(G) ≤ α(1− \frac{α}{1−α}) ≤ 3−2\sqrt{2}, as it is easily determined that the function has its maximum at α = 1 − 1/\sqrt{2}.

Finally, for s ≥ 3 let G be a regular K_{s+1}-free graph of order n. Erdős et.al. [6, Theorem 2.1] observed that Ψ(G, αn) < (s − 2)α^{2}n^{2}/(2s − 2) and combined with the lower bound from Theorem 3 and solved at α = 1/2 we obtain Ξ(G) < (s − 2)/(s − 1). □

4 Final remarks

Conjecture 2 is probably false for a larger range of α. By a (not verified) computer program we have discovered that the Cayley graph H_{41} of ℤ_{41} with respect to the generators {±1, ±4, ±10, ±16, ±18} satisfies β(H_{41}, α) > β(C_{5}, α) for 10/41 ≤ α < 2062/4305 ≃ .479. Anyway, it is not unlikely, that H_{100} is still a counterexample for α = .48, but it is definitely no counterexample for α = 1/2. This can be derived from the well-known fact that the vertices of the Higman-Sims graph can be partitioned into two sets each of which induces a Hoffman-Singleton graph [3, Chapter 8, Ex. 1]. This implies, together with the lower bound of (2), β(H_{100}, 1/2) = .0175.

While the estimate for β(G, α) derived from Theorem 3 is a convex function, the function itself is not necessarily convex. This is, e.g., the case for the local density function of the Clebsch graph (cf. [3, Chapter 8]), which is not difficult to compute by hand.

A surprising consequence is that the local density function of the Clebsch graph exceeds the density function of C_{5} within two intervals of α, namely .313 ≃ 5/16 < α < 103/220 ≃ .468 and .588 ≃ 47/80 < α < 29/48 ≃ .604. The dependence of the local density function on the structure of the graph seems to indicate that a precise calculation of β(α) might be very hard when α is significantly smaller than 3/5, because many graphs are potential candidates to determine β(α).

Computing the local density of regular graphs can be simplified by the observation of a certain symmetry around 1/2.

Lemma 2 If G is an r-regular graph of order n then

Ψ(G, αn) = Ψ(G, (1 − α)n) + rn(α − 1/2). □

The simple proof depends on the fact, that Ψ(G, k) is attained by a set S ⊆ V (G) where the number of edges joining S to G − S is maximal among all subsets S of cardinality k (the same idea works from the fractional viewpoint). Exploiting this idea, which is due to Krivelevich [8], we can express the minimum number of edges needed to make a regular graph bipartite (cf. Conjecture 1) in terms of the function Ψ.

Lemma 3 The minimum number of edges which need to be deleted to make a regular graph G of order n bipartite equals

min_{0≤k≤n/2} Ψ(G, k) + Ψ(G, n − k). □

Together with Lemma 1 we obtain that the validity of Conjecture 2 for α = 1/2 verifies Conjecture 1, restricted to regular graphs. As the lower bound in Theorem 3 is a convex function we obtain for every regular triangle-free graph G, assuming that Conjecture 1 is valid, that

n^{2}/25 ≥ Ψ(G, k) + Ψ(G, n − k) ≥ n^{2}(r + λ_{n})/4n = n^{2}Ξ(G)/4,

for a suitable k ≤ n/2, which would imply that Conjecture 3 was valid.

An appendix containing details about density functions of certain triangle-free graphs and the current records for β(α) is available and can be requested directly from the author.

Acknowledgments: I thank Barbara Baumeister for helpful discussions concerning strongly regular graphs, and several people at our department, who helped me to overcome the computational difficulties.

References

[1] N. Alon and J. H. Spencer, The probabilistic method, Wiley, New York, 1992.

[2] F. C. Bussemaker, D. M. Cvetković and J. J. Seidel, Graphs related to exceptional root systems, in: Combinatorics Vol. I (Proc. Conf. Keszthely 1976, A. Hajnal and V. Sós, Eds.), pp. 185–191, Colloq. Math. Soc. J. Bolyai 18, North Holland, Amsterdam/New York, 1978.

[3] P. J. Cameron and J. H. van Lint, Designs, graphs, codes and their links, London Math. Soc. Student Texts 22, Cambridge Univ. Press, 1991.

[4] P. Erdős, Some unsolved problems in graph theory and combinatorial analysis, in: Combinatorial Mathematics and its Applications (Proc. Conf. Oxford 1969, Ed. D. J. A. Welsh), pp. 97–109, Acad. Press, London, 1971.

[5] P. Erdős, R. Faudree, J. Pach and J. Spencer, How to make a graph bipartite, J. Comb. Theory Ser. B 45 (1988), 86–98.

[6] P. Erdős, R. J. Faudree, C. C. Rousseau and R. H. Schelp, A local density condition for triangles, Discr. Math. 127 (1994), 153–161.

[7] D. G. Higman and C. C. Sims, A simple group of order 44,352,000, Math. Z. 105 (1968), 110–113.

[8] M. Krivelevich, On the edge distribution in triangle-free graphs, J. Comb. Theory Ser. B 63 (1995), 245–260.

5 Appendix

This part is not meant to be published. I intend to summarize the spectral ratio and bounds for the local density functions of several triangle-free graphs which I obtained by hand or by computer search, and my current records for the function β(α) where 3/10 ≤ α ≤ 1/2. These results could serve as a starting point to people who want to estimate β(α) in further detail. This information is supplied without liability, as it depends heavily on the correctness of my programs and calculations. Please send me an information if you have any corrections or improvements to β(α) or ξ(i), or graphs with interesting properties in this context.

5.1 Local density functions and spectral ratios of certain graphs

We offer the exact non-zero values of the local density function only for four graphs, namely K_{2}, C_{5}, the Petersen graph P_{10} and the Clebsch graph H_{16}.

β(K_{2}, α) = (2α − 1)/4 if 1/2 ≤ α ≤ 1.

β(C_{5}, α) = \{ \begin{matrix}(5α − 2)/25 if & 2/5 ≤ α ≤ 3/5 \\ (2α − 5)/4 if & 3/5 ≤ α ≤ 1. \end{matrix}

β(P_{10}, α) = \{ \begin{matrix}(5α − 2)/25 if & 2/5 ≤ α ≤ 1/2 \\ (10α − 3)/100 if & 1/2 ≤ α ≤ 3/5 \\ (6α − 3)/20 if & 3/5 ≤ α ≤ 1. \end{matrix}

β(H_{16}, α) = \{ \begin{matrix}(32α − 10)/16^{2} if & 5/16 ≤ α ≤ 6/16 \\ (16α − 4)/16^{2} if & 6/16 ≤ α ≤ 8/16 \\ (64α − 28)/16^{2} if & 8/16 ≤ α ≤ 10/16 \\ (48α − 18)/16^{2} if & 10/16 ≤ α ≤ 11/16 \\ (80α − 40)/16^{2} if & 11/16 ≤ α ≤ 1. \end{matrix}

For the following graphs we offer estimates of β(G, α) which are tight if α|G| is integral: the (3, 9)-Ramsey graph H_{35}, the Cayley graph H_{41} of ℤ_{41} with respect to the generators {±1, ±4, ±10, ±16, ±18} and the Cayley graph H_{51} of ℤ_{51} with respect to the generators {±1, ±4, ±6, ±13, ±16, ±24}. For simplicity, we concentrate on the range of α, where we are interested in.

β(H_{35}, α) ≥ \{ \begin{matrix}(35α − 8)/35^{2} if & 8/35 ≤ α ≤ 12/35 \\ (70α − 20)/35^{2} if & 12/35 ≤ α ≤ 13/35 \\ (35α − 7)/35^{2} if & 13/35 ≤ α ≤ 14/35 \\ (105α − 35)/35^{2} if & 14/35 ≤ α ≤ 15/35 \\ (140α − 50)/35^{2} if & 15/35 ≤ α ≤ 16/35 \\ (105α − 34)/35^{2} if & 16/35 ≤ α ≤ 17/35 \\ (140α − 51)/35^{2} if & 17/35 ≤ α ≤ 18/35. \end{matrix}

β(H_{41}, α) ≥ \{ \begin{matrix}(82α − 20)/41^{2} if & 10/41 ≤ α ≤ 15/41 \\ (123α − 35)/41^{2} if & 15/41 ≤ α ≤ 17/41 \\ (164α − 52)/41^{2} if & 17/41 ≤ α ≤ 20/41 \\ (205α − 72)/41^{2} if & 20/41 ≤ α ≤ 21/41 \\ (246α − 93)/41^{2} if & 21/41 ≤ α ≤ 24/41 \\ (287α − 117)/41^{2} if & 24/41 ≤ α ≤ 26/41. \end{matrix}

β(H_{51}, α) ≥ (102α − 24)/51^{2} if 12/51 ≤ α ≤ 15/51.

The Higman-Sims graph H_{100} and the Cayley graph H_{101} of ℤ_{101} with respect to the generators {±1, ±6, ±10, ±14, ±17, ±32, ±36, ±39, ±41, ±44} are particularly interesting graphs in this context. Anyway, we only have the density bounds via their eigenvalues, which are not good enough. But the spectral ratio justifies, that they are potentially good candidates.

A table of spectral ratios follows:

graph  K_{2} C_{5} P H_{16} H_{35} H_{41} H_{51} H_{100} H_{101}
spectral ratio  0 .078 .1 .125 .102 .1251 .112 .14 .121

5.2 The current records of the local density

We have the following lower bound for β(α) for .3 ≤ α ≤ 1. Our bounds for smaller values of α do not seem to be reasonable, so we omit them. Surprisingly, only few graphs determine the current optimum, namely K_{2}, C_{5}, H_{16} and H_{41}. Note that except K_{2} and C_{5} no Ramsey-graph contributes to the current optimum, and my guess is that no further Ramsey-graph will determine β(α). We have checked that the (3, 4)-, (3, 5)- and (3, 9)-Ramsey-graph cannot contribute to the optimum (though the latter one – H_{35} – seemed to me particularly suitable).

β(α) ≥  range  witness graph
(2α − 1)/4  1 ≥ α ≥ 17/30 ≃ .567  K_{2}
(5α − 2)/25  17/30 ≥ α ≥ 1/2 = .5  C_{5}
(5α − 2)/25  1/2 ≥ α ≥ 2062/4305 ≃ .479 C_{5}, P_{10}
(164α − 52)/41^{2} 2062/4305 ≥ α ≥ 1647/3772 ≃ .437 H_{41}
(16α − 4)/16^{2} 1647/3772 ≥ α ≥ 3/8 = .375 H_{16}
(32α − 10)/16^{2}  3/8 ≥ α ≥ 1169/3280 ≃ .356 H_{16}
(82α − 20)/41^{2} 1169/3280 ≥ α ≥ 973/3485 ≃ .279 H_{41}

The next witness graph would be H_{51} but most likely the bounds are not even close to the optimum within this range. The required graphs are likely to have larger order. It should be mentioned that it might even be the case that H_{41} and H_{16} are superseded by H_{100} and H_{101} for the whole range .279 ≤ α ≤ .479