Publications2024The Maker-Breaker percolation game on a random boardV. Dvořák, A. Mond and V. Souzaarxiv
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.
2023On the number of monochromatic solutions to multiplicative equationsL. Aragão, J. Chapman, M. Ortega and V. Souzaarxiv
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.
2023Localised graph Maclaurin inequalitiesL. Aragão and V. SouzaAnnals of Combinatorics, 2023arxivjournal
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.
2022Expander graphs are globally synchronisingP. Abdalla, A. Bandeira, M. Kassabov, V. Souza, S. Strogatz and A. Townsendarxivquanta
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.
2022A note on the number of Egyptian fractionsN. Lebowitz-Lockard and V. SouzaIntegers, 2023arxivjournal
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.
2022Improved bounds for the dimension of divisibilityV. Souza and L. VersteegenEuropean Journal of Combinatorics, 2024arxivjournal
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.
2021The Maker-Breaker percolation game on the square latticeV. Dvořák, A. Mond and V. SouzaJournal 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$.
2020The order dimension of divisibilityD. Lewis and V. SouzaJournal of Combinatorial Theory, Series A, 2021arxivjournal
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.
2019The typical structure of sets with small sumsetM. Campos, M. Collares, R. Morris, N. Morrison and V. SouzaInternational Mathematics Research Notices, 2022arxivjournal
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$.
2019Blowup Ramsey numbersV. SouzaEuropean Journal of Combinatorics, 2021arxivjournal
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 Papers2022On the zero-sum Ramsey problem over $\mathbb{Z}_2^d$J. Alvarado, L. Colucci, R. Parente and V. SouzaThe 15th Latin American Theoretical Informatics Symposium, 2022proceedings
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.
2021Hitting times for arc-disjoint arborescences in random digraph processesM. Collares, Y. Kohayakawa, T. Martins, R. Parente and V. SouzaXI Latin and American Algorithms, Graphs and Optimization Symposium, 2021proceedings
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
2023 University of Cambridge -
Supervisor Part II Graph Theory.
2022 University of Cambridge -
Supervisor Part II Number Theory.
2021 University of Cambridge -
Supervisor Part II Number Theory.
2021 University of Cambridge -
Supervisor Part IA Analysis I.
2020 University of Cambridge -
Supervisor Part II Number Theory.
