António Girão

activity

20222024

collaborators

8 papers

math.CO2024

Monochromatic odd cycles in edge-coloured complete graphs

António Girão, Zach Hunter

It is easy to see that every $q$ -edge-colouring of the complete graph on $2^{q} + 1$ vertices must contain a monochromatic odd cycle. A natural question raised by Erdős and Graham in $…

math.CO2024

Sparse Partitions of Graphs with Bounded Clique Number

António Girão, Toby Insley

We prove that for each integer $r \geq 2$ , there exists a constant $C_{r} > 0$ with the following property: for any $0 < ε \leq 1/2$ and any graph $G$ with clique number at most…

math.CO2024

Small families of partially shattering permutations

António Girão, Lukas Michel, Youri Tamitegama

We say that a family of permutations $t$ -shatters a set if it induces at least $t$ distinct permutations on that set. What is the minimum number $f_{k} (n, t)$ of permutations of $\{1,…

math.CO2024

Embedding induced trees in sparse expanding graphs

António Girão, Eoin Hurley

Inspired by the network routing literature \cite{aggarwal1996efficient}, we develop what we call a ``Pre-Emptive Greedy Algorithm" to embed bounded degree induced trees in sparse e…

math.CO2023

Abundance: Asymmetric Graph Removal Lemmas and Integer Solutions to Linear Equations

António Girão, Eoin Hurley, Freddie Illingworth +1

We prove that a large family of pairs of graphs satisfy a polynomial dependence in asymmetric graph removal lemmas. In particular, we give an unexpected answer to a question of Gis…

math.CO2023

Flashes and rainbows in tournaments

António Girão, Freddie Illingworth, Lukas Michel +2

Colour the edges of the complete graph with vertex set ${1, 2, \dots, n}$ with an arbitrary number of colours. What is the smallest integer $f (l, k)$ such that if $n > f (l, k)$ th…