A Proof of the $(n,k,t)$-Conjectures
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913840018489344 |
|---|---|
| author | Baumann, Stacie Briggs, Joseph |
| author_facet | Baumann, Stacie Briggs, Joseph |
| contents | An \emph{$(n,k,t)$-graph} is a graph on $n$ vertices in which every set of $k$ vertices contains a clique on $t$ vertices. Turán's Theorem, rephrased in terms of graph complements, states that the unique minimum $(n,k,2)$-graph is an equitable disjoint union of cliques. We prove that minimum $(n,k,t)$-graphs are always disjoint unions of cliques for any $t$ (despite \allowbreak nonuniqueness of extremal examples), thereby generalizing Turán's Theorem and confirming two conjectures of Hoffman et al. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2210_08370 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | A Proof of the $(n,k,t)$-Conjectures Baumann, Stacie Briggs, Joseph Combinatorics 05C35 An \emph{$(n,k,t)$-graph} is a graph on $n$ vertices in which every set of $k$ vertices contains a clique on $t$ vertices. Turán's Theorem, rephrased in terms of graph complements, states that the unique minimum $(n,k,2)$-graph is an equitable disjoint union of cliques. We prove that minimum $(n,k,t)$-graphs are always disjoint unions of cliques for any $t$ (despite \allowbreak nonuniqueness of extremal examples), thereby generalizing Turán's Theorem and confirming two conjectures of Hoffman et al. |
| title | A Proof of the $(n,k,t)$-Conjectures |
| topic | Combinatorics 05C35 |
| url | https://arxiv.org/abs/2210.08370 |