PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
March 10, 2026Random Structures and Algorithms0 citationsOpen Access

Cyclic Subsets of Tournaments

View Full Paper
ZHZach HunterTLTeng LiuAMAleksa Milojević

Key Points

  • This research explores the likelihood of a random induced subtournament being Hamiltonian in Dirac graphs.
  • Analyzed tournaments with high minimum degree.
  • Investigated random vertex subset selection methods.
  • Determined probability bounds for induced subtournaments.
  • Provided an optimal bound on the probability of Hamiltonian induced subtournaments.
  • Extended findings to non-uniformly sampled vertex subsets.

Abstract

ABSTRACT Let be a Dirac graph, and let be a vertex subset of , chosen uniformly at random. How likely is the induced subgraph to be Hamiltonian? This question, proposed by Erdős and Faudree in 1996, was recently resolved by Draganić, Keevash, and Müyesser, in the setting of graphs. In this paper, we study a similar question for tournaments: If is a tournament of high minimum degree, how likely is it for a random induced subtournament of to be Hamiltonian? We prove an optimal bound on this probability, and extend the results to the regime where the subset is not sampled uniformly at random, but according to a ‐biased measure.

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Hunter et al. (2026) studied this question.

synapsesocial.com/papers/69af94e870916d39fea4bf44https://doi.org/10.1002/rsa.70056
Ask AI
Helpful
Bookmark
Share
View Full Paper