A generalized Turán problem in random graphs

DOI10.1002/RSA.20873MaRDI QIDQ5113940zbMATH OpenOpenAlexFDO

Authors Wojciech Samotij, Clara Shikhelman

Publication date 19 June 2020

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

random graphsthresholdsTurán's theorem

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We study the following generalization of the Tur'an problem in sparse random graphs. Given graphs $T$ and $H$, let $$ be the random variable that counts the largest number of copies of $T$ in a subgraph of $G(n,p)$ that does not contain $H$. We study the threshold phenomena arising in the evolution of the typical value of this random variable, for every $H$ and an arbitrary $2$-balanced $T$. Our results in the case when $m_2(H)>m_2(T)$ are a natural generalization of the ErdH{o}s--Stone theorem for $G(n,p)$, which was proved several years ago by Conlon and Gowers and by Schacht; the case $T=K_m$ has been recently resolved by Alon, Kostochka, and Shikhelman. More interestingly, the case when $m_2(H)le{m}_2(T)$ exhibits a more complex and subtle behavior. Namely, the location(s) of the (possibly multiple) threshold(s) are determined by densities of various coverings of $H$ with copies of $T$ and the typical value(s) of $$ are given by solutions to deterministic hypergraph Tur'an-type problems that we are unable to solve in full generality.

Recommendations

• The Turn Theorem for Random Graphs
• Turán‐type problems for long cycles in random and pseudo‐random graphs
• Turán's theorem in sparse random graphs
• Turán's theorem for pseudo-random graphs
• Turán's extremal problem in random graphs: Forbidding even cycles
• Turán's extremal problem in random graphs: Forbidding odd cycles
• Tuza's conjecture for random graphs
• Turán's graph theorem, measures and probability theory

Cited in

(13)

• Generalized Turán densities in the hypercube
• Turán's graph theorem, measures and probability theory
• Note on a problem of M. Talagrand
• Extremal results for random discrete structures
• Inequalities in probability theory and turán-type problems for graphs with colored vertices
• The Turn Theorem for Random Graphs
• The structure of typical eye-free graphs and a Turán-type result for two weighted colours
• A generalization of Turán's theorem
• A Spectral Turán Theorem
• Triangles in C5‐free graphs and hypergraphs of girth six
• Random polynomial graphs for random Turán problems
• Many triangles in \(C_5\)-free graphs
• Turán's theorem for pseudo-random graphs

This page was built for publication: A generalized Turán problem in random graphs

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