An improved bound on Seymour's second neighborhood conjecture
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915083962023936 |
|---|---|
| author | Huang, Hao Peng, Fei |
| author_facet | Huang, Hao Peng, Fei |
| contents | Seymour's celebrated second neighborhood conjecture, now more than thirty years old, states that in every oriented digraph, there is a vertex $u$ such that the size of its second out-neighborhood $N^{++}(u)$ is at least as large as that of its first out-neighborhood $N^+(u)$. In this paper, we prove the existence of $u$ for which $|N^{++}(u)| \ge 0.715538 |N^+(u)|$. This result provides the first improvement to the best known constant factor in over two decades. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_20234 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An improved bound on Seymour's second neighborhood conjecture Huang, Hao Peng, Fei Combinatorics 05C20 (Primary) 05C35, 05C12 (Secondary) Seymour's celebrated second neighborhood conjecture, now more than thirty years old, states that in every oriented digraph, there is a vertex $u$ such that the size of its second out-neighborhood $N^{++}(u)$ is at least as large as that of its first out-neighborhood $N^+(u)$. In this paper, we prove the existence of $u$ for which $|N^{++}(u)| \ge 0.715538 |N^+(u)|$. This result provides the first improvement to the best known constant factor in over two decades. |
| title | An improved bound on Seymour's second neighborhood conjecture |
| topic | Combinatorics 05C20 (Primary) 05C35, 05C12 (Secondary) |
| url | https://arxiv.org/abs/2412.20234 |