6 papers
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…
Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
Jun-Ting Hsieh, Pravesh K. Kothari, Sidhanth Mohanty +2
Given a -uniform hypergraph on vertices, an even cover in is a collection of hyperedges that touch each vertex an even number of times. Even covers are a generalizat…