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 copy of $K_t$ that is canonically coloured, i.e. monochromatic, rainbow, or lexicographic. In this paper we investigate two variations of th...
Strahinja Gvozdic, Zach Hunter, Aleksa Milojević et al.· 0 citations
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 vertices in which each vertex has degree at least $n/2$ has this property. In this short expository note, intended to be used in the classroom, we...
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 distinct cycle lengths occurring in the graph. In 1966, Erd\H{o}s and Hajnal suggested studying $s(G):=\sum_{\ell\in{C}(G)}1/\ell$ as a measure of...
Richard Montgomery, Aleksa Milojević, A. Pokrovskiy et al.· 0 citations
The spherical random geometric graph $G(n,d,p)$ is obtained by sampling $n$ independent points uniformly on the unit sphere $\mathbb{S}^{d-1}\subseteq\mathbb{R}^d$ and joining pairs of points which are sufficiently close, where the threshold is chosen so that the edge probability is $p$. The central question related to...
Let $w_1, \dots, w_m$ be positive real weights whose sum is $1$, and let $v_1, \dots, v_m$ be i.i.d. Bernoulli$(p)$ random variables. If we let $X=\sum_{i=1}^m w_i v_i$, then we conjecture that for all $0\leq p\leq 1/3$ we have \[\mathbb{P}\big[X\geq \mathbb{E}[X]\big]\geq p.\] In this short note, we observe a connecti...
Aleksa Milojević, Benny Sudakov· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
