Two problems on cycles in random graphs

We prove three results. First, an old conjecture of Zs. Tuza says that for any graph G, the ratio of the minimum size, τ3(G), of a set of edges meeting all triangles to the maximum size, ν3(G), of an edge-disjoint triangle packing is at most 2. Disproving a conjecture of R. Yuster [40], we show that for any fixed, positive α there are arbitrarily large graphs G of positive density satisfying τ3(G) > (1 − o(1))|G|/2 and ν3(G) < (1 + α)|G|/4. Second, write C(G) for the cycle space of a graph G, Cκ(G) for the subspace of C(G) spanned by the copies of Cκ in G, Tκ for the class of graphs satisfying Cκ(G) = C(G), and Qκ for the class of graphs each of whose edges lies in a Cκ. We prove that for every odd κ ≥ 3 and G = Gn,p, max p Pr(G ∈ Qκ Tκ) → 0; so the Cκ’s of a random graph span its cycle space as soon as they cover its edges. For κ = 3 this was shown in [12]. Third, we extend the seminal van den Berg–Kesten Inequality [9] on disjoint occurrence of two events to a setting with arbitrarily many events, where the quantity of interest is the maximum number that occur disjointly. This provides a handy tool for bounding upper tail probabilities for event counts in a product probability space.Ph.D.Includes bibliographical referencesby Jacob D. Baro