Inverse Turán numbers

DOI10.1016/J.DISC.2021.112779MaRDI QIDQ2113336zbMATH OpenOpenAlexFDO

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

Publication date 14 March 2022

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

forbidden subgraphTurán number

Mathematics Subject Classification ID

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

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$.

Recommendations

• Turán's theorem inverted
• Inverting the Turán problem
• scientific article; zbMATH DE number 3841893
• 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

Cites work

• scientific article; zbMATH DE number 3869331 (Why is no real title available?)
• scientific article; zbMATH DE number 3652374 (Why is no real title available?)
• scientific article; zbMATH DE number 3232670 (Why is no real title available?)
• scientific article; zbMATH DE number 3285073 (Why is no real title available?)
• scientific article; zbMATH DE number 3342002 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• A Note on Bipartite Graphs Without 2 k -Cycles
• A new series of dense graphs of high girth
• An extremal problem for paths in bipartite graphs
• Connected graphs without long paths
• Existence of spanning \(\mathcal{F}\)-free subgraphs with large minimum degree
• Extremal \(C_{4}\)-free/\(C_{5}\)-free planar graphs
• Inverting the Turán problem
• Large subgraphs without short cycles
• Large triangle-free subgraphs in graphs without \(K_ 4\)
• Norm-graphs and bipartite Turán numbers
• Norm-graphs: Variations and applications
• On Graphs that do not Contain a Thomsen Graph
• On a problem of K. Zarankiewicz
• On maximal paths and circuits of graphs
• On the structure of linear graphs
• Some Theorems on Abstract Graphs
• The history of degenerate (bipartite) extremal graph problems

Cited in

(5)

• Random polynomial graphs for random Turán problems
• Inverting the Turán problem
• 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)