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

DOI10.1016/J.EJC.2020.103200zbMATH Open1458.05236arXiv1909.00214OpenAlexW3080426545MaRDI QIDQ2225403FDOQ2225403

Authors: József Balogh, Andrzej Dudek, Lina Li 

Publication date: 8 February 2021

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

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.

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• Turán‐type problems for long cycles in random and pseudo‐random graphs
• Erdös-Gallai-type problems for distance-edge-monitoring numbers
• Ergodic theory on stationary random graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• New lower bounds on the size-Ramsey number of a path
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)

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)