8 papers
Long Directed Cycles in Vertex-Transitive Digraphs
Bowen Li, Abhishek Methuku
The search for Hamiltonian cycles in vertex-transitive graphs and digraphs is a classical problem at the interface of graph theory and group theory. In the undirected setting, this…
The independence number of uncrowded hypergraphs: bounds matching the shattering threshold
Abhishek Dhawan, Abhishek Methuku, Minh-Quan Vo
A foundational theorem of Ajtai, Komlós, Pintz, Spencer, and Szemerédi asserts that every -vertex -uniform uncrowded hypergraph with maximum degree contains an indepen…
Packing subgraphs in regular graphs
Shoham Letzter, Abhishek Methuku, Benny Sudakov
An \emph{-packing} in a graph is a collection of pairwise vertex-disjoint copies of in . We prove that for every and every bipartite graph , any $\lfloor c…
Nearly Hamilton cycles in sublinear expanders, and applications
Shoham Letzter, Abhishek Methuku, Benny Sudakov
We develop novel methods for constructing nearly Hamilton cycles in sublinear expanders with good regularity properties, as well as new techniques for finding such expanders in gen…
Independent sets and colorings of -free graphs
Abhishek Dhawan, Oliver Janzer, Abhishek Methuku
Alon, Krivelevich, and Sudakov conjectured in 1999 that every -free graph of maximum degree at most has chromatic number . This was previously known only fo…
Regular subgraphs at every density
Debsoumya Chakraborti, Oliver Janzer, Abhishek Methuku +1
In 1975, ErdÅs and Sauer asked to estimate, for any constant , the maximum number of edges an -vertex graph can have without containing an -regular subgraph. In a recent…