Cyclic Subsets in Regular Dirac Graphs

Journal article

In 1996, in his last paper, Erdős asked the following question that he formulated together with Faudree: is there a positive such that any -regular graph on vertices contains at least distinct vertex-subsets that are cyclic, meaning that there is a cycle in using precisely the vertices in . We answer this question in the affirmative in a strong form by proving the following exact result: if is sufficiently large and minimises the number of cyclic subsets then is obtained from the complete bipartite graph by adding a -factor (a spanning collection of vertex-disjoint cycles) within the part of size . In particular, for large, this implies that the optimal in the problem is precisely .

Authors: Draganić, N; Keevash, P; Müyesser, A

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Oxford University Press
• Journal: International Mathematics Research Notices
• Volume: 2025
• Issue: 14
• Article number: rnaf215
• Publication date: 2025-07-22
• Acceptance date: 2025-06-27
• DOI: 10.1093/imrn/rnaf215
• EISSN: 1687-0247
• ISSN: 1073-7928
• Language: English