An analogue of the Erdős-Gallai theorem for random graphs

DOI10.1016/J.EJC.2020.103200MaRDI QIDQ2225403zbMATH OpenOpenAlexFDO

Authors József Balogh, Andrzej Dudek, Lina Li

Publication date 8 February 2021

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.00214

zbMATH Keywords

size-Ramsey number of paths

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Generalized Ramsey theory (05C55)

Abstract: Recently, variants of many classical extremal theorems have been proved in the random environment. We, complementing existing results, extend the ErdH{o}s-Gallai Theorem in random graphs. In particular, we determine, up to a constant factor, the maximum number of edges in a $P_n$-free subgraph of $G(N,p)$, practically for all values of $N,n$ and $p$. Our work is also motivated by the recent progress on the size-Ramsey number of paths.

Recommendations

• Hypergraph extensions of the Erdős-Gallai theorem
• Hypergraph extensions of the Erdős-Gallai theorem
• An Erdős-Gallai type theorem for uniform hypergraphs
• Structure of the largest subgraphs of \(G_{n , p}\) with a given matching number
• Extremal results in random graphs

Cites work

• A note on the Turán function of even cycles
• An extremal problem for random graphs and the number of graphs with large even-girth
• Coloring the edges of a random graph without a monochromatic giant component
• Combinatorial theorems in sparse random sets
• Expanders -- how to find them, and what to find in them
• Extremal results for random discrete structures
• Extremal subgraphs of random graphs
• Factors in random graphs
• Hypergraph containers
• Independent sets in hypergraphs
• Large triangle-free subgraphs in graphs without \(K_ 4\)
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Long cycles in locally expanding graphs, with applications
• Note on the multicolour size-Ramsey number for paths
• On \(K^ 4\)-free subgraphs of random graphs
• On large matchings and cycles in sparse random graphs
• On maximal paths and circuits of graphs
• On size Ramsey number of paths, trees, and circuits. I
• On some multicolor Ramsey properties of random graphs
• On the resilience of long cycles in random graphs
• Ramsey games with giants
• The Turn Theorem for Random Graphs
• The longest path in a random graph
• The size Ramsey number
• The size Ramsey number of a directed path
• Turán's extremal problem in random graphs: Forbidding even cycles
• Turán's extremal problem in random graphs: Forbidding odd cycles
• Turán's theorem in sparse random graphs

Cited in

(15)

• Analytic combinatorics on random graphs
• On a Conjecture of Godsil Concerning Controllable Random Graphs
• Goldberg's conjecture is true for random multigraphs
• scientific article; zbMATH DE number 1943957 (Why is no real title available?)
• Turán‐type problems for long cycles in random and pseudo‐random graphs
• Ergodic theory on stationary random graphs
• scientific article; zbMATH DE number 17680 (Why is no real title available?)
• Erdös-Gallai-type problems for distance-edge-monitoring numbers
• New lower bounds on the size-Ramsey number of a path
• scientific article; zbMATH DE number 1552204 (Why is no real title available?)
• scientific article; zbMATH DE number 5130735 (Why is no real title available?)
• scientific article; zbMATH DE number 5375038 (Why is no real title available?)
• A Berry-Esseen bound with applications to vertex degree counts in the Erdős-Rényi random graph
• The Grothendieck constant of random and pseudo-random graphs
• scientific article; zbMATH DE number 1019391 (Why is no real title available?)

This page was built for publication: An analogue of the Erdős-Gallai theorem for random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2225403)