A generalized Turán problem in random graphs

DOI10.1002/RSA.20873zbMATH Open1436.05099arXiv1806.06609OpenAlexW2963403279MaRDI QIDQ5113940FDOQ5113940

Authors: Wojciech Samotij, Clara Shikhelman 

Publication date: 19 June 2020

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

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.

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

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

zbMATH Keywords

thresholdsrandom graphsTurán's theorem

Mathematics Subject Classification ID

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

Cited In (10)

• 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 graph theorem, measures and probability theory
• A generalization of Turán's theorem
• The Turn Theorem for Random Graphs
• A Spectral Turán Theorem
• Inequalities in probability theory and turán-type problems for graphs with colored vertices
• Generalized Turán densities in the hypercube
• 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)