Aleksa Milojević

Perfect matchings in hypergraphs and Feige's inequality

Aleksa Milojević, Benny Sudakov

How large of a minimum degree does an $n$ -vertex graph need before we are sure that it contains a perfect matching? Dirac's theorem states that a graph on an even number of vertice…

Sharp bounds for off-diagonal and tripartite canonical Ramsey numbers

Strahinja Gvozdić, Zach Hunter, Aleksa Milojević +1

The canonical Ramsey theorem establishes that for every positive integer $t$ , there is a sufficiently large $n$ such that every edge-colouring of a complete graph $K_{n}$ contains a…

Minimising the harmonic sum of cycle lengths

Richard Montgomery, Aleksa Milojević, Alexey Pokrovskiy +1

A central theme in extremal graph theory is to understand the relationship between the density of a graph and the richness of its cycle length spectrum, which is the set of distinc…

Nearly tight bounds for induced subdivisions

Zach Hunter, Aleksa Milojević, Patryk Morawski +1

Subdivisions of complete graphs play a central role in combinatorics, having deep connections to structural, extremal, and topological aspects of graph theory. A celebrated conject…

Gaussian random graphs and Ramsey numbers

Zach Hunter, Aleksa Milojević, Benny Sudakov

We give a simple proof of the recent remarkable exponential improvement for Ramsey lower bounds, obtained by Ma, Shen and Xie. Our key ingredient is an alternative construction bas…

From small eigenvalues to large cuts, and Chowla's cosine problem

Zhihan Jin, Aleksa Milojević, István Tomon +1

We prove that every graph with average degree $d$ and smallest adjacency eigenvalue $∣ λ_{n} ∣ \leq d^{γ}$ contains a clique of size $d^{1 - O (γ)}$ . A simple corollary of this yields the fi…

Cyclic subsets of tournaments

Zach Hunter, Teng Liu, Aleksa Milojević +1

Let $G$ be a Dirac graph, and let $S$ be a vertex subset of $G$ , chosen uniformly at random. How likely is the induced subgraph $G [S]$ to be Hamiltonian? This question, proposed by…

Beyond the MaxCut problem in $H$ -free graphs

Zhihan Jin, Aleksa Milojević, István Tomon

In a recent breakthrough, Zhang proves that if $G$ is an $H$ -free graph with $m$ edges, then $G$ has a cut of size at least $m /2 + c_{H} m^{0.5001}$ , making a significant step towards a…

$C_{4}$ -free subgraphs of high degree with geometric applications

Zach Hunter, Aleksa Milojević, Istvan Tomon +1

The Zarankiewicz problem, a cornerstone problem in extremal graph theory, asks for the maximum number of edges in an $n$ -vertex graph that does not contain the complete bipartite g…

Universality for transversal Hamilton cycles in random graphs

Micha Christoph, Anders Martinsson, Aleksa Milojević

A tuple $(G_{1}, \dots, G_{n})$ of graphs on the same vertex set of size $n$ is said to be Hamilton-universal if for every map $χ : [n] \to [n]$ there exists a Hamilton cycle whose $i$ -th e…

Disjoint pairs in set systems and combinatorics of low rank matrices

Zach Hunter, Aleksa Milojević, Benny Sudakov +1

We study and solve several problems in two closely related settings: set families in $2^{[n]}$ with many disjoint pairs of sets and low rank matrices with many zero entries. - More…

Long induced paths in $K_{s, s}$ -free graphs

Zach Hunter, Aleksa Milojević, Benny Sudakov +1

More than 40 years ago, Galvin, Rival and Sands showed that every $K_{s, s}$ -free graph containing an $n$ -vertex path must contain an induced path of length $f (n)$ , where $f(n)\to…

Canonical Ramsey numbers of sparse graphs

Lior Gishboliner, Aleksa Milojević, Benny Sudakov +1

The canonical Ramsey theorem of Erdős and Rado implies that for any graph $H$ , any edge-coloring (with an arbitrary number of colors) of a sufficiently large complete graph $K_{N}$ c…

Larger Nearly Orthogonal Sets over Finite Fields

Ishay Haviv, Sam Mattheus, Aleksa Milojević +1

For a field $F$ and integers $d$ and $k$ , a set $A \subseteq F^{d}$ is called $k$ -nearly orthogonal if its members are non-self-orthogonal and every $k + 1$ ve…

Point-variety incidences, unit distances and Zarankiewicz's problem for algebraic graphs

Aleksa Milojević, Benny Sudakov, István Tomon

In this paper we study the number of incidences between $m$ points and $n$ varieties in $F^{d}$ , where $F$ is an arbitrary field, assuming the incidence graph conta…

Kővári-Sós-Turán theorem for hereditary families

Zach Hunter, Aleksa Milojević, Benny Sudakov +1

The celebrated Kővári-Sós-Turán theorem states that any $n$ -vertex graph containing no copy of the complete bipartite graph $K_{s, s}$ has at most $O_{s} (n^{2 - 1/ s})$ edges. In the pas…