Inverse Turán numbers

DOI10.1016/J.DISC.2021.112779zbMATH Open1484.05104arXiv2007.07042OpenAlexW4205114494MaRDI QIDQ2113336FDOQ2113336

Authors: Nika Salia, Casey Tompkins, Oscar Zamora, Ervin Győri 

Publication date: 14 March 2022

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: For given graphs $G$ and $F$, the Tur'an number $ex(G,F)$ is defined to be the maximum number of edges in an $F$-free subgraph of $G$. Foucaud, Krivelevich and Perarnau and later independently Briggs and Cox introduced a dual version of this problem wherein for a given number $k$, one maximizes the number of edges in a host graph $G$ for which $ex(G,H)<k$. Addressing a problem of Briggs and Cox, we determine the asymptotic value of the inverse Tur'an number of the paths of length $4$ and $5$ and provide an improved lower bound for all paths of even length. Moreover, we obtain bounds on the inverse Tur'an number of even cycles giving improved bounds on the leading coefficient in the case of $C_4$. Finally, we give multiple conjectures concerning the asymptotic value of the inverse Tur'an number of $C_4$ and $P_{ell}$, suggesting that in the latter problem the asymptotic behavior depends heavily on the parity of $ell$.

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

Recommendations

• Turán's theorem inverted
• Inverting the Turán problem
• scientific article
• Induced Turán numbers
• Regular Tur\'an numbers
• Problème inverse de Galois et nombres réciproques
• Inversions in compositions of integers
• Turán numbers of extensions
• scientific article; zbMATH DE number 4045750
• scientific article; zbMATH DE number 1315267

zbMATH Keywords

forbidden subgraphTurán number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30)

Cites Work

• On maximal paths and circuits of graphs
• The History of Degenerate (Bipartite) Extremal Graph Problems
• Title not available (Why is that?)
• On the structure of linear graphs
• An extremal problem for paths in bipartite graphs
• Title not available (Why is that?)
• Some Theorems on Abstract Graphs
• Norm-graphs and bipartite Turán numbers
• On Graphs that do not Contain a Thomsen Graph
• On a problem of K. Zarankiewicz
• Norm-graphs: Variations and applications
• Title not available (Why is that?)
• A new series of dense graphs of high girth
• Large Subgraphs without Short Cycles
• Title not available (Why is that?)
• Large triangle-free subgraphs in graphs without \(K_ 4\)
• A Note on Bipartite Graphs Without 2 k -Cycles
• Existence of Spanning ℱ-Free Subgraphs with Large Minimum Degree
• Title not available (Why is that?)
• Title not available (Why is that?)
• Connected graphs without long paths
• Inverting the Turán problem
• Extremal \(C_{4}\)-free/\(C_{5}\)-free planar graphs

Cited In (4)

• Random polynomial graphs for random Turán problems
• LARGE -FREE SUBGRAPHS IN -CHROMATIC GRAPHS
• Inverting the Turán problem with chromatic number
• How connectivity affects the extremal number of trees

This page was built for publication: Inverse Turán numbers

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