Cyclic subsets in regular Dirac graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910899482132480 |
|---|---|
| author | Draganić, Nemanja Keevash, Peter Müyesser, Alp |
| author_facet | Draganić, Nemanja Keevash, Peter Müyesser, Alp |
| contents | In 1996, in his last paper, Erdős asked the following question that he formulated together with Faudree: is there a positive $c$ such that any $(n+1)$-regular graph $G$ on $2n$ vertices contains at least $c 2^{2n}$ distinct vertex-subsets $S$ that are cyclic, meaning that there is a cycle in $G$ using precisely the vertices in $S$. We answer this question in the affirmative in a strong form by proving the following exact result: if $n$ is sufficiently large and $G$ minimises the number of cyclic subsets then $G$ is obtained from the complete bipartite graph $K_{n-1,n+1}$ by adding a $2$-factor (a spanning collection of vertex-disjoint cycles) within the part of size $n+1$. In particular, for $n$ large, this implies that the optimal $c$ in the problem is precisely $1/2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_01826 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cyclic subsets in regular Dirac graphs Draganić, Nemanja Keevash, Peter Müyesser, Alp Combinatorics 05C35, 05C65, 05C70 In 1996, in his last paper, Erdős asked the following question that he formulated together with Faudree: is there a positive $c$ such that any $(n+1)$-regular graph $G$ on $2n$ vertices contains at least $c 2^{2n}$ distinct vertex-subsets $S$ that are cyclic, meaning that there is a cycle in $G$ using precisely the vertices in $S$. We answer this question in the affirmative in a strong form by proving the following exact result: if $n$ is sufficiently large and $G$ minimises the number of cyclic subsets then $G$ is obtained from the complete bipartite graph $K_{n-1,n+1}$ by adding a $2$-factor (a spanning collection of vertex-disjoint cycles) within the part of size $n+1$. In particular, for $n$ large, this implies that the optimal $c$ in the problem is precisely $1/2$. |
| title | Cyclic subsets in regular Dirac graphs |
| topic | Combinatorics 05C35, 05C65, 05C70 |
| url | https://arxiv.org/abs/2503.01826 |