7 citations · 14 across the 18 of their papers we have counts for
20 papers
Hadwiger--Nelson Problem for Typical Norms
Noga Alon, Matija Bucić, James Davies
The classical Hadwiger-Nelson problem asks for the chromatic number of the unit distance graph of the Euclidean plane. Over the years, this problem has been considered for a variet…
The uniform Turán density of the tetrahedron
Matija Bucić
We prove that the uniform Turán density of is equal to . Kielak, Král', Lamaison, Liu, Shu, and Wu have recently proved the same result using combinatorial methods…
Long cycles in vertex transitive digraphs
Matija Bucić, Kevin Hendrey, Bojan Mohar +2
One of the most well-known conjectures concerning Hamiltonicity in graphs asserts that any sufficiently large connected vertex transitive graph contains a Hamilton cycle. In this f…
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…
Towards Graham's rearrangement conjecture via rainbow paths
Matija Bucić, Bryce Frederickson, Alp Müyesser +2
We study an old question in combinatorial group theory which can be traced back to a conjecture of Graham from 1971. Given a group , and some subset , is it possib…
Equiangular lines via improved eigenvalue multiplicity
Igor Balla, Matija Bucić
A family of lines passing through the origin in an inner product space is said to be equiangular if every pair of lines defines the same angle. In 1973, Lemmens and Seidel raised w…
Topological Minors in Typical Lifts
Matija Bucić, Micha Christoph, Alp Müyesser +1
An -lift of a graph is any graph obtained by replacing every vertex of with an independent set of size , and connecting every pair of two such independent sets…
Counting independent sets in structured graphs
Matija Bucić, Maria Chudnovsky, Julien Codsi
Counting independent sets in graphs and hypergraphs under a variety of restrictions is a classical question with a long history. It is the subject of the celebrated container metho…
Equivalence between Erdős-Hajnal and polynomial Rödl and Nikiforov conjectures
Matija Bucić, Jacob Fox, Huy Tuan Pham
It is well-known that polynomial versions of theorems of Rödl and Nikiforov, as conjectured by Fox and Sudakov and Nguyen, Scott and Seymour imply the classical Erdős-Hajnal conjec…
Geometric graphs with exponential chromatic number and arbitrary girth
Matija Bucić, James Davies
In 1975 Erdős initiated the study of the following very natural question. What can be said about the chromatic number of unit distance graphs in that have large girt…
On polynomial degree-boundedness
Romain Bourneuf, Matija Bucić, Linda Cook +1
We prove a conjecture of Bonamy, Bousquet, Pilipczuk, Rzążewski, Thomassé, and Walczak, that for every graph , there is a polynomial such that for every positive integer …
Essentially tight bounds for rainbow cycles in proper edge-colourings
Noga Alon, Matija Bucić, Lisa Sauermann +2
An edge-coloured graph is said to be rainbow if no colour appears more than once. Extremal problems involving rainbow objects have been a focus of much research over the last decad…
The power of many colours
Noga Alon, Matija Bucić, Micha Christoph +1
A classical problem, due to Gerencsér and Gyárfás from 1967, asks how large a monochromatic connected component can we guarantee in any -edge colouring of ? We consider how…
Unit and distinct distances in typical norms
Noga Alon, Matija Bucić, Lisa Sauermann
Erdős' unit distance problem and Erdős' distinct distances problem are among the most classical and well-known open problems in discrete mathematics. They ask for the maximum numbe…
Induced subgraph density. I. A loglog step towards Erdos-Hajnal
Matija Bucić, Tung Nguyen, Alex Scott +1
In 1977, Erdős and Hajnal made the conjecture that, for every graph , there exists such that every -free graph has a clique or stable set of size at least ;…
Towards the Erdős-Hajnal conjecture for -free graphs
Pablo Blanco, Matija Bucić
The Erdős-Hajnal conjecture is one of the most classical and well-known problems in extremal and structural combinatorics dating back to 1977. It asserts that in stark contrast to…