Victor Seixas Souza Research Fellow at Sidney Sussex College

Research Associate at Department of Computer Science and Technology
University of Cambridge

Office FC15
William Gates Building
Cambridge, CB3 0FD

United Kingdom

vss28 cam ac uk

I am a new Research Fellow at Sidney Sussex College, Cambridge, and a Research Associate in the Algorithms and Complexity group, under the mentorship of Tom Gur.

I have recently finished my PhD at Department of Pure Mathematics and Mathematical Statistics at the University of Cambridge, where I was very fortunate of being supervised by Professor Béla Bollobás. Prior to that, I had the pleasure of being a master student of Rob Morris at IMPA surounded by the forests of Rio de Janeiro.

Research Interests

I am broadly interested in combinatorics, number theory, probability theory and related areas in statistical physics and theoretical computer science.

Recently, I have been involved with the study of synchronisation phenomena. My work on synchronisation has been recently featured in Quanta magazine.

Publications 2024 The Maker-Breaker percolation game on a random board V. Dvořák, A. Mond and V. Souza arxiv The $(m,b)$ Maker-Breaker percolation game on $(\mathbb{Z}^2)_p$, introduced by Day and Falgas-Ravry, is played in the following way. Before the game starts, each edge of $\mathbb{Z}^2$ is removed independently with probability $1-p$. After that, Maker chooses a vertex $v_0$ to protect. Then, in each round Maker and Breaker claim respectively $m$ and $b$ unclaimed edges of $G$. Breaker wins if after the removal of the edges claimed by him the component of $v_0$ becomes finite, and Maker wins if she can indefinitely prevent Breaker from winning.

We show that for any $p < 1$, Breaker almost surely has a winning strategy for the $(1,1)$ game on $(\mathbb{Z}^2)_p$. This fully answers a question of Day and Falgas-Ravry, who showed that for $p = 1$ Maker has a winning strategy for the $(1,1)$ game. Further, we show that in the $(2,1)$ game on $(\mathbb{Z}^2)_p$ Maker almost surely has a winning strategy whenever $p > 0.9402$, while Breaker almost surely has a winning strategy whenever $p < 0.5278$. This shows that the threshold value of $p$ above which Maker has a winning strategy for the $(2,1)$ game on $\mathbb{Z}^2$ is non-trivial. In fact, we prove similar results in various settings, including other lattices and biases $(m,b)$.

These results extend also to the most general case, which we introduce, where each edge is given to Maker with probability $\alpha$ and to Breaker with probability $\beta$ before the game starts. 2023 On the number of monochromatic solutions to multiplicative equations L. Aragão, J. Chapman, M. Ortega and V. Souza arxiv Given an $r$-colouring of the interval $\{2, \dotsc, N \}$, what is the minimum number of monochromatic solutions of the equation $xy = z$? For $r=2$, we show that there are always asymptotically at least $(1/2\sqrt{2}) N^{1/2} \log N$ monochromatic solutions, and that the leading constant is sharp. We also establish a stability version of this result. For general $r$, we show that there are at least $C_r N^{1/S(r-1)}$ monochromatic solutions, where $S(r)$ is the Schur number for $r$ colours and $C_r$ is a constant. This bound is sharp up to logarithmic factors when $r \leq 4$. We also obtain results for more general multiplicative equations of the form $x_1^{a_1} \dotsb x_k^{a_k} = y$, where $a_1, \dotsc, a_k$ are positive integers, at least one of which equals $1$. Our corresponding upper bounds are given in terms of certain 'interval Rado numbers' for additive equations. We pose a number of open problems concerning these numbers. 2023 Localised graph Maclaurin inequalities L. Aragão and V. Souza Annals of Combinatorics, 2023 arxiv journal The Maclaurin inequalities for graphs are a broad generalisation of the classical theorems of Turán and Zykov. In a nutshell they provide an asymptotically sharp answer to the following question: what is the maximum number of cliques of size q in a $K_{r+1}$-free graph with a given number of cliques of size $s$? We prove an extensions of the graph Maclaurin inequalities with a weight function that captures the local structure of the graph. As a corollary, we settle a recent conjecture of Kirsch and Nir, which simultaneously encompass the previous localised results of Bradač, Malec and Tompkins and of Kirsch and Nir. 2022 Expander graphs are globally synchronising P. Abdalla, A. Bandeira, M. Kassabov, V. Souza, S. Strogatz and A. Townsend arxiv quanta The Kuramoto model is a prototypical model used for rigorous mathematical analysis in the field of synchronisation and nonlinear dynamics. A realisation of this model consists of a collection of identical oscillators with interactions given by a network, which we identify respectively with vertices and edges of a graph. In this paper, we show that a graph with sufficient expansion must be globally synchronising, meaning that the Kuramoto model on such a graph will converge to the fully synchronised state with all the oscillators with same phase, for every initial state up to a set of measure zero. In particular, we show that for any $\varepsilon > 0$ and $p \geq (1 + \varepsilon)(\log n)/n$, the Kuramoto model on the Erdős-Rényi graph $G(n,p)$ is globally synchronising with probability tending to one as $n$ goes to infinity. This improves on a previous result of Kassabov, Strogatz and Townsend and solves a conjecture of Ling, Xu and Bandeira. We also show that the Kuramoto model is globally synchronising on any $d$-regular Ramanujan graph with $d \geq 600$ and that, for the same range of degrees, a $d$-regular random graph is typically globally synchronising. 2022 A note on the number of Egyptian fractions N. Lebowitz-Lockard and V. Souza Integers, 2023 arxiv journal Improving an estimate of Croot, Dobbs, Friedlander, Hetzel and Pappalardi, we show that for all $k \geq 2$, the number of integers $1 \leq a \leq n$ such that the equation $$\frac{a}{n} = \frac{1}{m_1} + \dotsc + \frac{1}{m_k}$$ has a solution in positive integers $m_1, \dotsc, m_k$ is bounded above by $n^{1 - 1/2^{k-2} + o(1)}$ as $n$ goes to infinity. 2022 Improved bounds for the dimension of divisibility V. Souza and L. Versteegen European Journal of Combinatorics, 2024 arxiv journal The dimension of a partially-ordered set $P$ is the smallest integer $d$ such that one can embed $P$ into a product of $d$ linear orders. We prove that the dimension of the divisibility order on the interval $\{1, \dotsc, n\}$ is bounded above by $C(\log n)^2 (\log \log n)^{-2} \log \log \log n$ as $n$ goes to infinity. This improves a recent result by Lewis and the first author, who showed an upper bound of $C(\log n)^2 (\log \log n)^{-1}$ and a lower bound of $c(\log n)^2 (\log \log n)^{-2}$, asymptotically. To obtain these bounds, we provide a refinement of a bound of Füredi and Kahn and exploit a connection between the dimension of the divisibility order and the maximum size of $r$-cover-free families. 2021 The Maker-Breaker percolation game on the square lattice V. Dvořák, A. Mond and V. Souza Journal of Combinatorial Theory, Series B. (Accepted) arxiv We study the $(m,b)$ Maker-Breaker percolation game on $\mathbb{Z}^2$, introduced by Day and Falgas-Ravry. In this game, Maker and Breaker claim respectively $m$ and $b$ unclaimed edges of the square lattice $\mathbb{Z}^2$. Breaker wins if the component of the origin becomes finite when his edges are deleted from $\mathbb{Z}^2$. Maker if she can indefinitely avoid a win of Breaker. We show that Breaker has a winning strategy for the $(m,b)$ game whenever $b \geq (2 - 1/14 + o(1))m$, breaking the ratio $2$ barrier proved by Day and Falgas-Ravry.

Addressing further questions of Day and Falgas-Ravry, we show that Breaker can win the $(m,2m)$ game even if he allows Maker to claim $c$ edges before the game starts, for any integer $c$, and that he can moreover win rather quickly as a function of $c$.

We also consider the game played on the so-called polluted board, obtained after performing Bernoulli bond percolation on $\mathbb{Z}^2$ with parameter $p$. We show that for the $(1,1)$ game on the polluted board, Breaker almost surely has a winning strategy whenever $p \leq 0.6298$. 2020 The order dimension of divisibility D. Lewis and V. Souza Journal of Combinatorial Theory, Series A, 2021 arxiv journal The Dushnik-Miller dimension of a partially-ordered set $P$ is the smallest $d$ such that one can embed $P$ into a product of $d$ linear orders. We prove that the dimension of the divisibility order on the interval $\{1,\dotsc,n\}$, is equal to $(\log n)^2(\log\log n)^{\Theta(1)}$ as $n$ goes to infinity. We prove similar bounds for the $2$-dimension of divisibility in $\{1,\dotsc,n\}$, where the $2$-dimension of a poset $P$ is the smallest $d$ such that $P$ is isomorphic to a suborder of the subset lattice of $\{1, \dotsc, d\}$. We also prove an upper bound for the $2$-dimension of posets of bounded degree and show that the $2$-dimension of the divisibility poset on the set $(\alpha n, n]$ is $\Theta_\alpha(\log n)$ for $\alpha \in (0,1)$. At the end we pose several problems. 2019 The typical structure of sets with small sumset M. Campos, M. Collares, R. Morris, N. Morrison and V. Souza International Mathematics Research Notices, 2022 arxiv journal In this paper we determine the number and typical structure of sets of integers with bounded doubling. In particular, improving recent results of Green and Morris, and of Mazur, we show that the following holds for every fixed $\lambda > 2$ and every $k \geq (\log n)^4$: if $\omega \to \infty$ as $n \to \infty$ (arbitrarily slowly), then almost all sets $A \subset [n]$ with $|A| = k$ and $|A+A| \leq \lambda k$ are contained in an arithmetic progression of length $\lambda k/2 + \omega$. 2019 Blowup Ramsey numbers V. Souza European Journal of Combinatorics, 2021 arxiv journal We study a generalisation of the bipartite Ramsey numbers to blowups of graphs. For a graph $G$, denote the $t$-blowup of $G$ by $G[t]$. We say that $G$ is $r$-Ramsey for $H$, and write $G \xrightarrow{r} H$, if every $r$-colouring of the edges of $G$ has a monochromatic copy of $H$. We show that if $G \xrightarrow{r} H$, then for all $t$, there exists $n$ such that $G[n] \xrightarrow{r} H[t]$. In fact, we provide exponential lower and upper bounds for the minimum $n$ with $G[n] \xrightarrow{r} H[t]$, and conjecture an upper bound of the form $c^t$, where $c$ depends on $H$ and $r$, but not on $G$. We also show that this conjecture holds for $G(n,p)$ with high probability, above the threshold for the event $G(n,p) \xrightarrow{r} H$.
Conference Papers 2022 On the zero-sum Ramsey problem over $\mathbb{Z}_2^d$ J. Alvarado, L. Colucci, R. Parente and V. Souza The 15th Latin American Theoretical Informatics Symposium, 2022 proceedings Let $\Gamma$ be a finite abelian group and let $G$ be a graph. The zero-sum Ramsey number $R(G, \Gamma)$ is the least integer $N$ (if it exists) such that, for every edge-colouring $E(K_N) \mapsto \Gamma$, one can find a copy $G \subseteq K_N$ where the sum of the colours of the edges of $G$ is zero. A large body of research on this problem has emerged in the past few decades, paying special attention to the case where $\Gamma$ is cyclic. In this work, we start a systematic study of $R(G, \Gamma)$ for groups $\Gamma$ of small exponent, in particular, $\Gamma = \mathbb{Z}_2^d$. For the Klein group $\mathbb{Z}_2^2$, the smallest non-cyclic abelian group, we compute $R(G, \mathbb{Z}_2^2)$ for all odd forests $G$ and show that $R(G, \mathbb{Z}_2^2) \leq n+2$ for all forests $G$ on at least $6$ vertices. We also show that $R(C_4, \mathbb{Z}_2^d) = 2^d + 1$ for any $d \geq 2$, and determine the order of magnitude of $R(K_{t,r}, \mathbb{Z}_2^d)$ as $d \to \infty$ for all $t, r$. We also consider the related setting where the ambient graph $K_N$ is substituted by the complete bipartite graph $K_{N,N}$. Denote the analogue bipartite zero-sum Ramsey number by $B(G, \Gamma)$. We show that $B(C_4, \mathbb{Z}_2^d) = 2^d + 1$ for all $d \geq 1$ and $B(\{C_4, C_6\}, \mathbb{Z}_2^d) = 2^{d/2} + 1$ for all even $d \geq 2$. Additionally, we show that $B(K_{t,r}, \mathbb{Z}_2^d)$ and $R(K_{t,r}, \mathbb{Z}_2^d)$ have the same asymptotic behaviour as $d \to \infty$, for all $t, r$. Finally, we conjecture the value of $B(\{C_4, \dotsc, C_{2m}\}, \mathbb{Z}_2^d)$ and provide the corresponding lower bound. 2021 Hitting times for arc-disjoint arborescences in random digraph processes M. Collares, Y. Kohayakawa, T. Martins, R. Parente and V. Souza XI Latin and American Algorithms, Graphs and Optimization Symposium, 2021 proceedings In this work, we study hitting times for the appearance of a spanning structure in the Erdős-Rényi random directed graph processes. Namely, we are concerned with the appearance of an arborescence, a spanning digraph in which, for a vertex $u$ called the root and any other vertex $v$, there is exactly one directed path from $u$ to $v$. Let $\mathcal{D}(n,0), \mathcal{D}(n,1), \dotsc, \mathcal{D}(n,n(n-1))$ be the random digraph process where for every $m \in \{0,\dotsc, n(n-1)\}$, $\mathcal{D}(n,m)$ is a digraph with vertex set $\{1,\dotsc, n\}$; $\mathcal{D}(n,0)$ has no arcs and, for $1 \leq m \leq n(n-1)$, the digraph $\mathcal{D}(n,m)$ is obtained by adding an arc to $\mathcal{D}(n,m-1)$, chosen uniformly at random among the not present arcs. In this paper we determine the hitting time for the existence of $k$ arc-disjoint arborescences when $k= k(n) \ll \sqrt{\log n}$.
Teaching
February 2024