Research Seminar

The Kuramoto model is a system of ordinary differential equations that describes the behavior of coupled oscillators. In this talk, we consider the case where the coupling is given by a random geometric graph on the unit circle. We ask whether it is possible to guarantee global synchronization (for almost any initial condition, the system converges to a state where all phases coincide) or if there exist other stable equilibria. To address this question, we work with the energy function of the Kuramoto model on these graphs and prove the existence of at least one local minimum for each winding number q (with high probability). There is a correspondence between these states and the explicit 'twisted states' found in cycle graphs, although in this case without an explicit formula.

In this talk, we explore graph decompositions in various ways: first, we demonstrate how decomposing into color classes serves as a core technique for classifying highly regular colored graphs. Additionally, we examine classic open conjectures about graph decompositions, such as Hajós' cycle decomposition conjecture and the 3-decomposition conjecture. Finally, we discuss applications of modern decompositions, such as tree decompositions for determining the twin-width of graphs or for practical applications in public transportation networks.

Let $d≥ 1$ and $s≤2^d$ be nonnegative integers. For a subset $A$ of vertices of the hypercube $Q_n$ and $n≥d$, let $\lambda(n,d,s,A)$ denote the fraction of subcubes $Q_d$ of $Q_n$ that contain exactly $s$ vertices of $A$. Let $\lambda(n,d,s)$ denote the maximum possible value of $\lambda(n,d,s,A)$ as $A$ ranges over all subsets of vertices of $Q_n$, and let $\lambda(d,s)$ denote the limit of this quantity as $n$ tends to infinity.

We prove several lower and upper bounds on $\lambda(d,s)$, showing that for all admissible values of $d$ and $s$ it is larger than 0.28. We find all the values of $s=s(d)$ such that $\lambda(d,s)=1$. Many open problems remain, in particular the problem of determining $\lambda(d, 1)$.

This is a joint work with Noga Alon and John Goldwasser.

TBC

TBC

What is the maximum proportion of $d$-dimensional space that can be covered by non-overlapping, identical spheres? In this talk I will discuss a new lower bound for this problem, which is the first asymptotically growing improvement to Rogers' bound from 1947. Our proof is almost entirely combinatorial and reduces to a novel theorem about independent sets in graphs with bounded degrees and codegrees.

This is based on joint work with Marcelo Campos, Matthew Jenssen and Marcus Michelen.

We show that if $n$ is odd and $p ≥ C \log{n}/n$, then with high probability Hamilton cycles in $G(n, p)$ span its cycle space. More generally, we show this holds for a class of graphs satisfying certain natural pseudorandom properties. The proof is based on a novel idea of parity-switchers, which can be thought of as analogues of absorbers in the context of cycle spaces. As another application of our method, we show that Hamilton cycles in a near-Dirac graph $G$, that is, a graph $G$ with odd $n$ vertices and minimum degree $n/2 + C$ for sufficiently large constant $C$, span its cycle space. This is joint work with Micha Christoph and Rajko Nenadov.

An $n$-vertex graph $G$ is a $C$-expander if $|N(X)| \ge C|X|$ for every $X \subseteq V(G)$ with $|X| \lt n/2C$ and there is an edge between every two disjoint sets of at least $n/2C$ vertices. We show that there is some constant $C > 0$ for which every $C$-expander is Hamiltonian. In particular, this implies the well known conjecture of Krivelevich and Sudakov from 2003 on Hamilton cycles in $(n,d,\lambda)$-graphs. This completes a long line of research on the Hamiltonicity of sparse graphs, and has many applications. Joint work with N. Draganić, R. Montgomery, A. Pokrovskiy and B. Sudakov.

Let $R(C_n)$ be the Ramsey number of the cycle on $n$ vertices. We prove that, for some $C > 0$, with high probability every $2$-colouring of the edges of $G(N,p)$ has a monochromatic copy of $C_n$, as long as $N> R(C_n) + C/p$ and $p > C/n$. This is sharp up to the value of $C$ and it improves results of Letzter and of Krivelevich, Kronenberg and Mond.

This is joint work with Matías Pavez-Signe and Nicolas Sanhueza-Matamala.

For some positive integer $k$, a digraph $D$ is called $k$-\textit{dicolorable} if there exists a partition $(V_1,\ldots,V_k)$ of $V(D)$ such that $D[V_i]$ is acyclic for $i \in [k]$. Further, we say that $D$ is {\it $k$-dicritical} if $D$ is not $(k-1)$-dicolorable, but all of its proper subgraphs are.

The analogous problem in undirected graphs having been studied extensively, it is natural to try to understand what the maximum density of a large $k$-dicritical digraph is. Hoshino and Kawarabayashi conjectured that for every positive integer $k$, a simple $k$-dicritical digraph on $n$ vertices has at most $(\frac{1}{2}-\frac{1}{2^k-1})n^2$ arcs, with a finite number of exceptions. Aboulker observed that this conjecture implies that there are only finitely many $k$-dicritical tournaments for any positive integer $k$.

We show that this latter statement is true in the first nontrivial case, that is, when $k=3$. We also extend this result for semi-complete digraphs. Finally, by a computer-assisted approach, we give the full list of 3-dicritical semi-complete digraphs. There are exactly 8 of them, 2 of which are tournaments.

This is joint work with Frédéric Havet and Lucas Picasarri-Arrieta.

In this talk we consider positional games, where the winning sets are tree universal graphs, which contain copies of all spanning trees with a certain maximum degree. In particular, we show that in the unbiased Waiter-Client game on the complete graph $K_n$, Waiter has a strategy to occupy a graph which contains copies of all spanning trees with maximum degree at most $cn/\log(n)$, for a suitable constant $c$ and $n$ being large enough. This also shows that Waiter can play at least as good as suggested by the random graph intuition.

This is a joint work with Grzegorz Adamski, Sylwia Antoniuk, Ma\l gorzata Bednarska-Bzd\c{e}ga, Dennis Clemens, and Fabian Hamann.

A theorem of Frieze from 1985 asserts that the total weight of the minimum spanning tree of the complete graph $K_n$ whose edges get independent weights from the distribution $UNIFORM[0,1]$ converges to Apéry's constant in probability, as $n \to \infty$. We generalize this result to sequences of graphs $G_n$ that converge to a graphon $W$. Further, we allow the weights of the edges to be drawn from different distributions (subject to moderate conditions). The limiting total weight $\kappa(W)$ of the minimum spanning tree is expressed in terms of a certain branching process defined on $W$, which was studied previously by Bollobás, Janson and Riordan in connection with the giant component in inhomogeneous random graphs. Joint work with Gopal Viswanathan. arXiv:2310.11705.

We introduce a family of robust spanning trees embedded in Euclidean space, named central spanning tree (CST), whose geometrical structure is resilient against perturbations such as noise. The family of trees is defined through a parameterized NP-hard minimization problem over the edge lengths, with specific instances including the minimum spanning tree or the Euclidean Steiner tree. The minimization problem weighs the length of the edges by their tree edge-centralities, which are regulated by a parameter $\alpha$. Two variants of the problem are explored: one permitting the inclusion of Steiner points (referred to as branched central spanning tree or BCST), and another that does not. The effect of $\alpha$ on tree robustness is empirically analyzed, and a heuristic for approximating the optimal solution is proposed. Geometrical properties of the tree and its behavior in limit cases as $\alpha\to\pm\infty$ are also studied. This is a joint work with Christoph Schnörr and Fred Hamprecht.