|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Minimizing the number of copies of $K_r$ in an $F$-saturated graph | | Debsoumya Chakraborti
; Po-Shen Loh
; | | Date: |
2 Jul 2019 | | Abstract: | This paper considers two important questions in the well-studied theory of
graphs that are $F$-saturated. A graph $G$ is called $F$-saturated if $G$ does
not contain a subgraph isomorphic to $F$, but the addition of any edge creates
a copy of $F$. We first resolve the most fundamental question of minimizing the
number of cliques of size $r$ in a $K_s$-saturated graph for all sufficiently
large numbers of vertices, confirming a conjecture of Kritschgau, Methuku,
Tait, and Timmons. We also go further and prove a corresponding stability
result. We then move on to a central and longstanding conjecture in graph
saturation made by Tuza, which states that for every graph $F$, the limit
$lim_{n
ightarrow infty} frac{sat(n, F)}{n}$ exists, where $sat(n, F)$
denotes the minimum number of edges in an $n$-vertex $F$-saturated graph.
Pikhurko made progress in the negative direction by considering families of
graphs instead of a single graph, and proved that there exists a graph family
$mathcal{F}$ of size $4$ for which $lim_{n
ightarrow infty} frac{sat(n,
mathcal{F})}{n}$ does not exist (for a family of graphs $mathcal{F}$, a graph
$G$ is called $mathcal{F}$-saturated if $G$ does not contain a copy of any
graph in $mathcal{F}$, but the addition of any edge creates a copy of a graph
in $mathcal{F}$, and $sat(n, mathcal{F})$ is defined similarly). We make the
first improvement in 15 years by showing that there exist infinitely many graph
families of size $3$ where this limit does not exist. Our construction also
extends to the generalized saturation problem when we minimize the number of
fixed-size cliques. | | Source: | arXiv, 1907.1603 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER