Minimum number of edges that occur in odd cycles

DOI10.1016/J.JCTB.2018.12.003MaRDI QIDQ2312602zbMATH OpenOpenAlexWikidataFDO

Authors A. Grzesik, Ping Hu, Jan Volec

Publication date 17 July 2019

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

edges in cyclesextremal graph theoryflag algebras

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Grassmannians, Schubert varieties, flag manifolds (14M15)

Abstract: If a graph has $nge4k$ vertices and more than $n^2/4$ edges, then it contains a copy of $C_{2k+1}$. In 1992, ErdH{o}s, Faudree and Rousseau showed even more, that the number of edges that occur in a triangle is at least $2lfloorn/2floor+1$, and this bound is tight. They also showed that the minimum number of edges that occur in a $C_{2k+1}$ for $kge2$ is at least $11n^2/144-O(n)$, and conjectured that for any $kge2$, the correct lower bound should be $2n^2/9-O(n)$. Very recently, F"uredi and Maleki constructed a counterexample for $k=2$ and proved asymptotically matching lower bound, namely that for any $varepsilon>0$ graphs with $(1+varepsilon)n^2/4$ edges contain at least $(2+sqrt2)n^2/16approx0.2134n^2$ edges that occur in $C_5$. In this paper, we use a different approach to tackle this problem and obtain the following stronger result: Any $n$-vertex graph with at least $lfloor{n}^2/4floor+1$ edges has at least $(2+sqrt2)n^2/16-O(n^{15/8})$ edges that occur in $C_5$. Next, for all $kge3$ and $n$ sufficiently large, we determine the exact minimum number of edges that occur in $C_{2k+1}$ for $n$-vertex graphs with more than $n^2/4$ edges, and show it is indeed equal to $lfloorfrac{n}^{2}4floor+1-lfloorfracn+46floorlfloorfracn+16floor=2n^2/9-O(n)$. For both results, we give a structural description of the extremal configurations as well as obtain the corresponding stability results, which answer a conjecture of F"uredi and Maleki. The main ingredient is a novel approach that combines the flag algebras together with ideas from finite forcibility of graph limits. This approach allowed us to keep track of the extra edge needed to guarantee an existence of a $C_{2k+1}$. Also, we establish the first application of semidefinite method in a setting, where the set of tight examples has exponential size, and arises from different constructions.

Recommendations

• scientific article; zbMATH DE number 867704
• Cycle-saturated graphs with minimum number of edges
• scientific article; zbMATH DE number 1824729
• Min-max relations for odd cycles in planar graphs
• Cycle lengths and minimum degree of graphs
• Edge-disjoint odd cycles in graphs with small chromatic numbers
• The number of edges in a maximum cycle-distributed graph
• A Bound on the Number of Edges in Graphs Without an Even Cycle
• On the maximum number of odd cycles in graphs without smaller odd cycles
• Number of cycles of small length in a graph

Cites work

• A new bound for the 2/3 conjecture
• A new lower bound based on Gromov's method of selecting heavily covered points
• A problem of Erdős on the minimum number of k-cliques
• A Solution to the 2/3 Conjecture
• Applications of the Semi-Definite Method to the Turán Density Problem for 3-Graphs
• Asymptotic structure of graphs with the minimum number of triangles
• CSDP, A C library for semidefinite programming
• Extremal problems involving vertices and edges on odd cycles
• Flag algebras
• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• scientific article; zbMATH DE number 2123255 (Why is no real title available?)
• Hypergraphs do jump
• Minimum Number of Monotone Subsequences of Length 4 in Permutations
• Minimum Number ofk-Cliques in Graphs with Bounded Independence Number
• Monochromatic triangles in three-coloured graphs
• Non-three-colourable common graphs exist
• On extremal problems of graphs and generalized graphs
• On the Caccetta-Häggkvist conjecture with a forbidden transitive tournament
• On the Caccetta-Häggkvist conjecture with forbidden subgraphs
• On the maximum number of five-cycles in a triangle-free graph
• On the Minimal Density of Triangles in Graphs
• On the number of pentagons in triangle-free graphs
• Some recent problems and results in graph theory
• Testability and repair of hereditary hypergraph properties
• The clique density theorem
• The codegree threshold for 3-graphs with independent neighborhoods
• The inducibility of graphs on four vertices
• The Minimum Number of Triangular Edges and a Symmetrization Method for Multiple Graphs
• The minimum size of 3-graphs without a 4-set spanning no or exactly three edges
• The number of cliques in graphs of given order and size
• Turán \(H\)-densities for 3-graphs
• Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube

Cited in

(10)

• Maximum number of almost similar triangles in the plane
• Minimizing the number of triangular edges
• Minimizing the number of 5-cycles in graphs with given edge-density
• On the Caccetta-Häggkvist conjecture with a forbidden transitive tournament
• The Minimum Number of Triangular Edges and a Symmetrization Method for Multiple Graphs
• C5 ${C}_{5}$ is almost a fractalizer
• Solving Turán's tetrahedron problem for the ℓ2$\ell _2$‐norm
• A spectral Erdős-Faudree-Rousseau theorem
• The dimension of the region of feasible tournament profiles
• The dimension of the feasible region of pattern densities

Describes a project that uses

Uses Software

• CSDP
• SageMath
• Flagmatic

This page was built for publication: Minimum number of edges that occur in odd cycles

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