A Note on Sparse Random Graphs and Cover

Graphs^{∗}

Tom Bohman^{†}  Alan Frieze^{‡}  Miklós Ruszinkó^{§}

Lubos Thoma^{¶} Department of Mathematical Sciences Carnegie Mellon University Pittsburgh, PA 15213, USA

         tbohman@andrew.cmu.edu, alan@random.math.cmu.edu
         ruszinko@andrew.cmu.edu, thoma@qwes.math.cmu.edu

Submitted: December, 1999; Accepted: March 24, 2000.

Abstract

It is shown in this note that with high probability it is enough to destroy all triangles in order to get a cover graph from a random graph G_{n,p} with p ≤ κ log n/n for any constant κ < 2/3. On the other hand, this is not true for somewhat higher densities: If p ≥ λ(log n)^{3}/(n log log n) with λ > 1/8 then with high probability we need to delete more edges than one from every triangle. Our result has a natural algorithmic interpretation.

∗Keywords: random graph, cover graph, poset Proposed running head: Sparse Cover Graphs 1991 Mathematics Subject Classification: 05C80, 06A07 †Supported in part by NSF Grant DMS-9627408.

‡Supported in part by NSF grant CCR-9530974.

§Permanent Address Computer and Automation Research Institute of the Hungarian Academy of Sciences, Budapest, P.O.Box 63, Hungary-1518. Supported in part by OTKA Grants T 030059 and T 29074 FKFP 0607/1999.

¶Supported in part by NSF grant DMS-9970622.

1 Cover Graphs

The (Hasse) diagram of the finite poset P = (V, ≺) is the directed graph G⃗ = (V, A), where (u, v) ∈ A iff u ≺ v and there is no z ∈ V such that u ≺ z ≺ v. The finite undirected graph G = (V, E) is a cover graph iff there exists an orientation of its edges E⃗ such that G⃗ = (V, E⃗) is a diagram of some poset P = (V, ≺). Clearly, G⃗ = (V, A) is the diagram of a poset iff it contains no directed cycles and no directed quasicycles. A directed quasicycle is a cycle with oriented edges in which the reversal of the orientation of a single edge creates a directed cycle.

The relationship between cover graphs and graph parameters has been investigated in several papers. B. Descartes [5] (as noted in [2]) showed that there are cover graphs with arbitrarily large chromatic number and this was strenghtened by B. Bollobás [2] who showed that for every integer k there is a lattice whose diagram has chromatic number at least k. Furthermore, it was proved by Nešetřil and Rödl [9] that there exist graphs which are not cover graphs and have arbitrarily large girth.

The triangle is not a cover graph, since every orientation of its edges results in either a directed cycle or quasicycle. However, after deleting an edge from it, we get a path of length two, which is already a cover graph. Obviously, if we delete sufficiently many edges from an arbitrary graph G it will become a cover graph. Therefore, it is reasonable to ask, what is the minimum number c(G) such that after deleting c(G) edges from G it will be a cover graph. This parameter was introduced by Bollobás, Brightwell, and Nešetřil [4].

First consider dense random graphs. It is shown in [4] that for arbitrary integer l ≥ 2 and p = p(n) = o (n^{(l−2)/(l−1)}), c(G_{n,p}) ≤ (1 + δ)pn^{2}/2l whp^{1}. Moreover, if p = p(n) = n^{−1+η(n)}, where 0 < η_{0} ≤ η(n) ≤ 1, then whp one needs to delete a positive proportion of edges from G_{n,p} in order to get a cover graph. The auhors of [4] also conjectured that if pn^{(l−2)/(l−1)} → 0 and pn^{(l−1)/l} → ∞, then their upper bound gives the right constant, i.e., whp c(G_{n,p}) ∼ pn^{2}/2l. This has been recently proved by Rödl and Thoma [10].

For sparse random graphs, the authors of [4] show that whp c(G_{n,p}) = o(e(G_{n,p})). Namely they prove the following two bounds. For every c ≥ 1 there is a b, b > c log(1 + b), such that if p = p(n) ≤ \frac{c log n}{n}, then c(G_{n,p}) ≤ \frac{pn^{2}}{2} · \frac{b}{c log n}. Further, for every δ > 0 and for every function ω = ω(n), with ω → ∞ and ω = o(n^{ν}) for every ν > 0, if p = p(n) ≤ \frac{ω log n}{n}, then c(G_{n,p}) ≤ (1 + δ) · \frac{pn^{2}}{2} · \frac{log ω}{log n}.

1A sequence of events E_{n} occurs with high probability, whp, if Pr(E_{n}) = 1 − o(1) as n → ∞

For a graph G let τ(G) denote the minimum number of edges that must be deleted in order to get a triangle-free graph. In this note we focus on the graph property c(G) = τ(G). Since a cover graph may contain no triangles τ(G) ≤ c(G) always holds. We will show in this note, that for any constant κ < 2/3 and p ≤ κ log n/n, c(G_{n,p}) = τ(G_{n,p}) whp (Theorem 1.1) while for any constant λ > 1/8 and p ≥ λ(log n)^{3}/(n log log n), c(G_{n,p}) > τ(G_{n,p}) whp (Theorem 1.2).

We may interpret our results in an algorithmic way. Consider a simple algorithm which takes a graph G as input and deletes edges in copies of triangles as long as G is not triangle-free. Then Theorem 1.1 implies that if the algorithm takes as input G_{n,p}, p ≤ κ log n/n for a constant κ < 2/3, then it outputs a cover graph whp. Note that the output graph will have whp girth equal to 4. On a related note we point to [8] which surveys constructions of non cover graphs with a given girth. It is an open problem to construct small examples of non cover graphs with girth greater then 4.

We will prove the following theorems:

Theorem 1.1 If κ < 2/3 is constant and p ≤ κ log n/n then c(G) = τ(G) whp.

Theorem 1.2 If λ > 1/8 is constant and p ≥ λ(log n)^{3}/(n log log n) then c(G_{n,p}) > τ(G_{n,p}) whp.

For p = c/n, c constant we know that the distribution of the number of triangles in G_{n,p} is asymptotically Poisson with mean c^{3}/6, [6]. So as an immediate corollary we get that if p = c_{n}/n then

Corollary 1.3

lim_{n→∞} Pr(G_{n,p} is a cover graph) = \{ \begin{matrix}1 & c_{n} → −∞ \\ e^{−c^{3}/6} & c_{n} → c \\ 0 & c_{n} → ∞ \end{matrix}

Theorem 1.2 follows from the following stronger theorem:

Theorem 1.4 Suppose λ > 1/8 is constant and p ≥ λ(log n)^{3}/(n log log n) and g ≤ \frac{log n}{4 log log n}. Let H be obtained from G_{n,p} by deleting all vertices which lie on a cycle of length at most g. Then whp H is not a cover graph.

Remark 1.5 Part of the results of [10] is based on a detailed analysis of the expansion properties of the random graph G_{n,p}. Using the same analysis of the expansion properties provides the same bound on p in Theorem 1.4.

2 Triangle-free graphs: proof of Theorem 1.1

We will need the following lemma. Let χ = χ(G) be the chromatic number of G. We will call a cycle of G short if it contains ≤ χ(G) vertices and long otherwise. As usual the distance between two sets V_{1} and V_{2} of vertices in G is the length of the shortest path between u ∈ V_{1} and v ∈ V_{2}.

Lemma 2.1 Let G having the following properties:

(a) The distance between any two short cycles is at least χ + 1.

(b) No short cycle shares an edge with a cycle of length ≤ 2χ.

Then c(G) = τ(G).

Proof Let G′ = (V, E′) be a triangle-free subgraph of G which we get after deleting one edge of each triangle of G. Let V_{1}, …, V_{χ} be a proper coloring of G′ with χ colours. Define the orientation G⃗′ = (V, E⃗′) as follows. If u ∈ V_{i}, v ∈ V_{j} and i < j then orient the edge {u, v} from u to v. Notice that G⃗′ is acyclic, i.e., there are no oriented cycles in G⃗′. Also there are no long oriented quasicycles. Indeed, take an arbitrary long cycle C in G′. Let k = max{i : C ∩ V_{i} ≠ ∅} and let v ∈ C ∩ V_{k}. Both edges of C incident to v are oriented in G⃗′ towards v. So in order to get an oriented cycle we must change the orientation of at least one of the arcs (u_{1}, v), (u_{2}, v) of C which are incident with v. Assume we get an oriented cycle by reversing the arc (u_{1}, v), say. Then the remaining edges of the cycle form an oriented path from u_{1} to v in G⃗′ of length at least χ, a contradiction.

Of course, we still may have short oriented quasicycles. We will change the above orientation as follows. If G⃗′ contains no short quasicycles, then stop. If G⃗′ contains a short quasicycle C⃗ then reverse an arc (u, v) in C⃗ such that the resulting C⃗′ is neither a directed cycle, nor a directed quasicycle. (Since G′ is triangle-free, we can always do this.) Since G satisfies (a), i.e., in particular it contains vertex disjoint short cycles only, this process will terminate in at most n/χ steps and in the end there will be no short quasicycles.

We show now that we have created neither long cycles nor long quasicycles. Indeed, by (b), during the edge reversing process, we did not touch any long cycle having ≤ 2χ vertices. So take a long cycle C having ≥ 2χ + 1 vertices. Let an edge e ∈ C be short if it also lies on a short cycle and long otherwise. Long edges are unaffected by the reversing process of the previous paragraph. Label each short edge with the short cycle that produces it. Short edges with the same label form subpaths of C. By (a) the distance between any two short edges of C with distinct labels is at least χ and there will be two paths in C of length ≥ χ, made up long edges only. But the longest oriented path in G⃗′ is of length χ − 1. So if there are two short edges with distinct labels then there are at least two long edges in C⃗ in both directions along the cycle. If the short edges of C all have the same label and they make up more than one subpath then the paths of long edges in C between these subpaths are of length at least χ, else (b) is violated. Hence, again, there are at least two long edges in C⃗ in both directions along the cycle. Finally, suppose that the short edges of C all have the same label and they make up one subpath P. If none of the edges of P are reversed then by its length C will have at least three edges oriented in each direction around C. In any case, at most one will be reversed and so we will create neither a directed cycle nor a directed quasicycle by the reversing process. □

We complete the proof of Theorem 1.1 with

Lemma 2.2 If κ < 2/3 is constant and p ≤ κ log n/n then G_{n,p} whp satisfies the conditions of Lemma 2.1.

Proof It follows from Łuczak [7] that whp

χ(G_{n,p}) ≤ k_{0} = (\frac{κ}{2} + o(1))\frac{log n}{log log n}.

Assuming this we see that if the conditions of Lemma 2.1 are violated then there exists a set of k ≤ 3k_{0} vertices which contain at least k + 1 edges. The probability of this is at most

∑_{k=4}^{3k_{0}} \binom{n}{k}\binom{\binom{k}{2}}{k + 1} (\frac{κ log n}{n})^{k+1} ≤ ∑_{k=4}^{3k_{0}} (\frac{ne}{k})^{k} (\frac{ke}{2} · \frac{κ log n}{n})^{k+1}
≤ \frac{eκ log n}{2n} ∑_{k=4}^{3k_{0}} k((e^{2}κ/2) log n)^{k}
≤ \frac{3k_{0}((e^{2}κ/2) log n)^{3k_{0}+1}}{n}
= o(1).
□

2.1 Sparse Non Cover Graphs: proof of Theorem 1.4

For positive integers a, b, a partition V_{0}, V_{1}, …, V_{a} of an n-set is called an (a, b)- partition if |V_{0}| = b and |V_{i}| = |V_{j}| for all i ≠ j; i, j ∈ [a]. Thus we can only have an (a, b)-partition if a divides |V | − b.

We choose functions d = d(n), ω = ω(n), and N = N(n) such that

N = n − γ = n − o(n)
(\frac{d}{ω} )^{ω} = 2N log ω
d = ω^{3}(log ω)^{2}

where γ is the smallest integer larger than gd^{g} such that n − γ is divisible by ω. Note that this choice implies ω = (1 + o(1))\frac{log n}{2 log log n} and d = (1 + o(1))\frac{(log n)^{3}}{8 log log n}.

Let p = d/n. Since the property in Theorem 1.4 is monotone decreasing it is enough to prove Theorem 1.4 just for this choice of p.

We need the following lemma.

Lemma 2.3 Whp for every (ω, γ)-partition V_{0}, V_{1}, …, V_{ω} of the vertex set of G_{n,p}, there is a cycle C in G_{n,p} such that V (C) ∩ V_{0} = ∅ and |V (C) ∩ V_{i}| = 1, i = 1, …, ω.

Proof To prove the lemma we are going to use the Janson inequality, cf. [1] for notation. Note that the number of choices of (ω, γ)-partitions of an n-set is at most \binom{n}{γ}(eω)^{N}.

Let V_{0}, V_{1}, …, V_{ω} be a fixed (ω, γ)-partition. Let C_{1}, …, C_{l} be an enumeration of cycles satisfying V (C_{i}) ∩ V_{0} = ∅ and |V (C_{i}) ∩ V_{j}| = 1, i = 1, …, l, j = 1, …, ω, in the complete graph K_{n} with the partition V_{0}, V_{1}, …, V_{ω}. Set B_{i}, i = 1, …, l, to be the event that C_{i} exists in G_{n,p}. The expected number μ of such cycles in G_{n,p} satisfies

μ = ∑_{j=1}^{l} Pr (B_{j}) = (1 + o(1)) (\frac{N}{ω} )^{ω} (\frac{d}{N} )^{ω} = (1 + o(1)) (\frac{d}{ω} )^{ω} = (1 + o(1))2N log ω .

and

Δ = ∑_{|E(C_{i})∩E(C_{j})|≥1} Pr (B_{i} ∧ B_{j})
≤ ∑_{{t≥1 \atop 2≤L<ω}} ∑_{{l_{1}+···+l_{t}=L \atop l_{i}≥2}} (1 + o(1))ω^{t} (\frac{N}{ω} )^{L} (\frac{N}{ω} )^{2ω−2L} (\frac{d}{N} )^{2ω−(L−t)}  (1)
= (1 + o(1))μ · ∑_{t,L} ∑_{l_{1},...,l_{t}} (\frac{d}{ω} )^{ω} \frac{ω^{L+t}}{d^{L−t}N^{t}}
≤ (1 + o(1))μ · ∑_{t,L} \binom{L − 1}{t − 1}2N log ω · (\frac{ω}{d} )^{L} (\frac{ωd}{N})^{t}
= (1 + o(1))μ · ∑_{2≤L<ω} 2N log ω · (\frac{ω}{d} )^{L} \frac{ωd}{N} (1 + \frac{ωd}{N})^{L−1}
= o(μ) .

Note that the dominant term in the last sum is the term for L = 2.

Explanation of (1): The common edges of cycles C_{i}, C_{j} are asumed to form t paths of lengths l_{1}, l_{2}, …, l_{t}. ω^{t} estimates the number of choices for the start vertices of these paths. (N/ω)^{L} estimates the choices for the vertices of these paths and (N/ω)^{2ω−2L} estimates the choices for the vertices in C_{i}, C_{j} which are not on any common path. (d/N)^{2ω−(L−t)} is the probability that C_{i}, C_{j} exist.

Applying the Janson inequality we see that

Pr(∃ an (ω, γ)-partition without a cycle) ≤ \binom{n}{γ}(eω)^{N}e^{−(1−o(1))μ} ≤ \binom{n}{n^{3/4}}ω^{−(1−o(1))N} = o(1).

□

We can assume g = ⌊\frac{log n}{4 log log n}⌋ and that the condition in Lemma 2.3 holds. Now the expected number of vertices ν on cycles of length g or less in G_{n,p} is given by

∑_{k=3}^{g} \binom{n}{k}(k − 1)!p^{k} ≤ d^{g} ∑_{k=3}^{g} \frac{1}{k} ≤ d^{g} log g.

So whp ν ≤ gd^{g}.

Let V̂_{0} be the set of vertices of G incident to cycles of length g or less and V_{0} ⊇ V̂_{0} be arbitrarily chosen of size γ. Then G′ := G \ V_{0} is not a cover graph. Suppose it is. Let \overrightarrow{G}′ be its orientation as a diagram of some poset. Thus, we can embed \overrightarrow{G}′ into a linear ordering π. Let V_{1}, …, V_{ω}, |V_{i}| = N/ω, be the partition of the vertex set of G′ such that all vertices of V_{i} precede all vertices of V_{i+1} in the linear ordering π, i = 1, …, ω − 1. We have constructed an (ω, γ)-partition V_{0}, V_{1}, …, V_{ω} of the vertex set of G. By the lemma above we can assume that there is a cycle C such that V (C) ∩ V_{0} = ∅ and |V (C) ∩ V_{i}| = 1, i = 1, …, ω. The cycle C induces a quasicycle in \overrightarrow{G}′ – contradiction. This completes the proof of Theorem 1.4. □

References

[1] N. Alon, J. Spencer, The Probabilistic Method, John Wiley & Sons Inc., New York, 1992.

[2] B. Bollobás, Colouring lattices, Alg. Universalis 7 (1977), 313–314.

[3] B. Bollobás, Random Graphs, Academic Press 1985.

[4] B. Bollobás, G. Brightwell and J. Nešetřil, Random Graphs and Covering Graphs of Posets, Order 3 (1986) 245–255.

[5] B. Descartes, A Three Color Problem, Eureka, April 1947. Solution March 1948.

[6] P.Erdős and A.Rényi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960) 17-61.

[7] T.Łuczak, The chromatic number of random graphs, Combinatorica 11 (1991) 45-54.

[8] O. Pretzel, Orientations and Edge Functions on Graphs, in: A. D. Keedwell (ed.), Surveys in Combinatorics, London Math. Soc. Lecture Notes 66, 1991, 161–185.

[9] J. Nešetřil and V. Rödl, On a Probabilistic Graph-Theoretical Method, Proceedings AMS 72(2) (1978), 417–421.

[10] V. Rödl, L. Thoma, On Cover Graphs and Dependent Arcs in Acyclic Orientations, submitted.