A Jump of the Saturation Number in Random Graphs?

Abstract: For graphs

G

and

F

, the saturation number

e x t i t s a t (G, F)

is the minimum number of edges in an inclusion-maximal

F

-free subgraph of

G

. In 2017, Kor'andi and Sudakov initiated the study of saturation in random graphs. They showed that for constant

p i n (0, 1)

, whp

e x t i t s a t l e f t (G (n, p), K_{s} i g h t) = l e f t (1 + o (1) i g h t) n l o g_{f r a c 1 1 - p} n

. We show that for every graph

F

and every constant

p i n (0, 1)

, whp

e x t i t s a t l e f t (G (n, p), F i g h t) = O (n l n n)

. Furthermore, if every edge of

F

belongs to a triangle, then the above is the right asymptotic order of magnitude, that is, whp

e x t i t s a t l e f t (G (n, p), F i g h t) = T h e t a (n l n n)

. We further show that for a large family of graphs

m a t h c a l F

with an edge that does not belong to a triangle, which includes all the bipartite graphs, for every

F i n m a t h c a l F

and constant

p i n (0, 1)

, whp

e x t i t s a t l e f t (G (n, p), F i g h t) = O (n)

. We conjecture that this sharp transition from

O (n)

to

T h e t a (n l n n)

depends only on this property, that is, that for any graph

F

with at least one edge that does not belong to a triangle, whp

e x t i t s a t l e f t (G (n, p), F i g h t) = O (n)

. We further generalise the result of Kor'andi and Sudakov, and show that for a more general family of graphs

m a t h c a l F^{'}

, including all complete graphs

K_{s}

and all complete multipartite graphs of the form

K_{1, 1, s_{3}, l d o t s, s_{e l l}}

, for every

F i n m a t h c a l F^{'}

and every constant

p i n (0, 1)

, whp

e x t i t s a t l e f t (G (n, p), F i g h t) = l e f t (1 + o (1) i g h t) n l o g_{f r a c 1 1 - p} n

. Finally, we show that for every complete multipartite graph

K_{s_{1}, s_{2}, l d o t s, s_{e l l}}

and every

p i n l e f t [f r a c 12, 1 i g h t)

,

e x t i t s a t l e f t (G (n, p), K_{s_{1}, s_{2}, l d o t s, s_{e l l}} i g h t) = l e f t (1 + o (1) i g h t) n l o g_{f r a c 1 1 - p} n

.

This page was built for publication: A Jump of the Saturation Number in Random Graphs?