5 papers
Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
Matija Bucić, Zhongtian He, Shang-En Huang +1
We design efficient deterministic algorithms for finding short edge-disjoint paths in expanders. Specifically, given an -vertex -edge expander of conductance and mini…
On Graham's rearrangement conjecture over
Benjamin Bedert, Matija Bucić, Noah Kravitz +2
A sequence of elements of a group is called a valid ordering if the partial products are all distinct. A long-standi…
On a Ramsey--Turán variant of Roth's theorem
Matija Bucić, Micha Christoph, Jaehoon Kim +2
A classical theorem of Roth states that the maximum size of a solution-free set of a homogeneous linear equation in is if and only if the sum of…
Intersecting hypergraphs with large cover number
Matija Bucić, Vanshika Jain, Varun Sivashankar
In their famous 1974 paper introducing the local lemma, Erdős and Lovász posed a question-later referred by Erdős as one of his three favorite open problems: What is the minimum nu…
The spanning tree spectrum: improved bounds and simple proofs
Noga Alon, Matija Bucić, Lior Gishboliner
The number of spanning trees of a graph , denoted , is a well studied graph parameter with numerous connections to other areas of mathematics. In a recent remarkable paper…