Nested cycles with no geometric crossings

DOI10.1090/BPROC/107MaRDI QIDQ5030154zbMATH OpenOpenAlexFDO

Authors Irene Gil Fernández, Younjin Kim, Hong Liu, Jaehoon Kim

Publication date 16 February 2022

Published in Proceedings of the American Mathematical Society, Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

edge-disjoint cyclessublinear expanders

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Expander graphs (05C48)

Abstract: In 1975, ErdH{o}s asked the following question: what is the smallest function $f(n)$ for which all graphs with $n$ vertices and $f(n)$ edges contain two edge-disjoint cycles $C_1$ and $C_2$, such that the vertex set of $C_2$ is a subset of the vertex set of $C_1$ and their cyclic orderings of the vertices respect each other? We prove the optimal linear bound $f(n)=O(n)$ using sublinear expanders.

Recommendations

• Proof of a conjecture of Bollobás on nested cycles
• On a problem of Duke-Erdős-Rödl on cycle-connected subgraphs
• scientific article; zbMATH DE number 1151856
• On maximum cycle-distributed graphs
• An old problem of Erdős: a graph without two cycles of the same length

Cites work

• A Note on Vertex-Disjoint Cycles
• A proof of Mader's conjecture on large clique subdivisions in \(C_4\)-free graphs
• Extremal density for sparse minors and subdivisions
• Graph decomposition with constraints on the connectivity and minimum degree
• scientific article; zbMATH DE number 3933112 (Why is no real title available?)
• scientific article; zbMATH DE number 3523543 (Why is no real title available?)
• scientific article; zbMATH DE number 3639679 (Why is no real title available?)
• scientific article; zbMATH DE number 944226 (Why is no real title available?)
• On the maximal number of independent circuits in a graph
• Partition of graphs with condition on the connectivity and minimum degree
• Partitions of graphs with high minimum degree or connectivity.
• Proof of a conjecture of Bollobás on nested cycles
• Topological cliques in graphs II
• Vertex-disjoint cycles of the same length

Cited in

(16)

• Proof of a conjecture of Bollobás on nested cycles
• scientific article; zbMATH DE number 54786 (Why is no real title available?)
• Well-mixing vertices and almost expanders
• Crux and Long Cycles in Graphs
• Disjoint isomorphic balanced clique subdivisions
• How to build a pillar: a proof of Thomassen's conjecture
• Towards the Erdős-Gallai cycle decomposition conjecture
• Towards the Erdős-Gallai cycle decomposition conjecture
• Immersion of complete digraphs in Eulerian digraphs
• Separating path systems of almost linear size
• The extremal number of cycles with all diagonals
• Many Hamiltonian subsets in large graphs with given density
• Cycles with many chords
• Crux, space constraints and subdivisions
• Essentially tight bounds for rainbow cycles in proper edge-colourings
• Edge-disjoint cycles with the same vertex set

This page was built for publication: Nested cycles with no geometric crossings

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