7 papers · 1 filter
Breaking the Bollobás-Eldridge-Catlin Barrier for Bipartite Graphs
Peter Allen, Julia Böttcher, Julia Böttcher +2
The celebrated Bollobás-Eldridge-Catlin packing conjecture states that every -vertex graph with minimum degree at least contains every -vert…
Nearly-uniform degree distributions in spanning subgraphs
Richard Montgomery, Alexey Pokrovskiy, Benny Sudakov
We show that, when , every -regular -vertex graph contains a spanning subgraph whose degree distribution is nearly uniform, i.e., for each , there are…
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…
Power saving for the Brown-ErdÅs-Sós problem
Oliver Janzer, Abhishek Methuku, Aleksa MilojeviÄ +1
Let denote the maximum number of edges in a 3-uniform hypergraph on vertices which does not contain vertices spanning at least edges. A central problem in…
Restricted subgraphs of edge-colored graphs and applications
Benny Sudakov
A properly edge-colored graph is a graph with a coloring of its edges such that no vertex is incident to two or more edges of the same color. A subgraph is called rainbow if all it…
Approximate path decompositions of regular graphs
Richard Montgomery, Alp Müyesser, Alexey Pokrovskiy +1
We show that the edges of any -regular graph can be almost decomposed into paths of length roughly , giving an approximate solution to a problem of Kotzig from 1957. Along th…