On the cycle space of a random graph

Publication date 20 February 2019

Abstract: Write

m a t h c a l C (G)

for the cycle space of a graph

G

,

m a t h c a l C_{k} a p p a (G)

for the subspace of

m a t h c a l C (G)

spanned by the copies of the

k a p p a

-cycle

C_{k} a p p a

in

G

,

m a t h c a l T_{k} a p p a

for the class of graphs satisfying

m a t h c a l C_{k} a p p a (G) = m a t h c a l C (G)

, and

m a t h c a l Q_{k} a p p a

for the class of graphs each of whose edges lies in a

C_{k} a p p a

. We prove that for every odd

k a p p a g e q 3

and

G = G_{n, p}

, [max_p , Pr(G in mathcal{Q}_kappa setminus mathcal{T}_kappa) ightarrow 0;] so the

C_{k} a p p a

's of a random graph span its cycle space as soon as they cover its edges. For

k a p p a = 3

this was shown by DeMarco, Hamm and Kahn (2013).

Recommendations

Cites work

Cited in

(10)

This page was built for publication: On the cycle space of a random graph