Nested cycles with no geometric crossings

Autor:	Fern��ndez, Irene Gil, Kim, Jaehoon, Kim, Younjin, Liu, Hong
Rok vydání:	2022
Předmět:	Mathematics::Algebraic Geometry Algebra and Number Theory FOS: Mathematics Mathematics - Combinatorics 05C38 05C35 05C48 Discrete Mathematics and Combinatorics Combinatorics (math.CO) Geometry and Topology Analysis
Zdroj:	Proceedings of the American Mathematical Society, Series B. 9:22-32
ISSN:	2330-1511
DOI:	10.1090/bproc/107
Popis:	In 1975, Erd\H{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. Comment: 10 pages, 2 figures
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2e244ce07408c353039d9c613ca3641d https://doi.org/10.1090/bproc/107 Zobrazit plný text záznamu Plný text ve formátu PDF