17 citations · 20 across the 11 of their papers we have counts for
6 papers · 1 filter
Recognizing Leaf Powers and Pairwise Compatibility Graphs is NP-Complete
Max Dupré la Tour, Manuel Lafond, Ndiamé Ndiaye
Leaf powers and pairwise compatibility graphs were introduced over twenty years ago as simplified graph models for phylogenetic trees. Despite significant research, several propert…
-Leaf Powers Cannot be Characterized by a Finite Set of Forbidden Induced Subgraphs for
Max Dupré la Tour, Manuel Lafond, Ndiamé Ndiaye +1
A graph is a -leaf power if there is a tree whose leaves are the vertices of with the property that a pair of leaves and induce an edge in if and o…
Optimizing the CGMS upper bound on Ramsey numbers
Parth Gupta, Ndiame Ndiaye, Sergey Norin +1
In a recent breakthrough Campos, Griffiths, Morris and Sahasrabudhe obtained the first exponential improvement of the upper bound on the diagonal Ramsey numbers since 1935. We shor…
The Speed and Threshold of the Biased Hamilton Cycle Game
Noah Brustle, Sarah Clusiau, Vishnu V. Narayan +3
We show that there is a constant C such that for any , Maker wins the Maker-Breaker Hamilton cycle game in $n+\frac{Cn}{\sqrt{\ln{n}}}…
The Speed and Threshold of the Biased Perfect Matching Game
Noah Brustle, Sarah Clusiau, Vishnu V. Narayan +3
We show that Maker wins the Maker-Breaker perfect matching game in turns when the bias is at least , for any …
Descending the Stable Matching Lattice: How many Strategic Agents are required to turn Pessimality to Optimality?
Ndiame Ndiaye, Sergey Norin, Adrian Vetta
The set of stable matchings induces a distributive lattice. The supremum of the stable matching lattice is the boy-optimal (girl-pessimal) stable matching and the infimum is the gi…