Source author record

António Girão

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

10works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Cycles with almost linearly many chords

We prove that constant minimum degree already forces cycles with almost linearly many chords. Specifically, every graph $G$ with $δ(G)\ge C$ contains a cycle of length $\ell\ge 4$ with $Ω(\ell/\log^{C}\ell)$ chords for some absolute constant $C>0$ . This is the first result showing that a constant-degree condition yields an unbounded -- indeed nearly linear -- number of chords, placing our bound within a polylogarithmic factor of the Chen--Erdős--Staton conjecture. It also gives a strong affirmative conclusion in the direction of a recent question of Dvořák, Martins, Thomassé, and Trotignon asking whether constant-degree graphs must contain cycles whose chord counts grow with their length.

preprint2022arXiv

Defective Colouring of Hypergraphs

We prove that the vertices of every $(r + 1)$ -uniform hypergraph with maximum degree $Δ$ may be coloured with $c(\fracΔ{d + 1})^{1/r}$ colours such that each vertex is in at most $d$ monochromatic edges. This result, which is best possible up to the value of the constant $c$ , generalises the classical result of Erdős and Lovász who proved the $d = 0$ case.

preprint2022arXiv

Hamiltonicity of random subgraphs of the hypercube

We study Hamiltonicity in random subgraphs of the hypercube $\mathcal{Q}^n$ . Our first main theorem is an optimal hitting time result. Consider the random process which includes the edges of $\mathcal{Q}^n$ according to a uniformly chosen random ordering. Then, with high probability, as soon as the graph produced by this process has minimum degree $2k$ , it contains $k$ edge-disjoint Hamilton cycles, for any fixed $k\in\mathbb{N}$ . Secondly, we obtain a perturbation result: if $H\subseteq\mathcal{Q}^n$ satisfies $δ(H)\geqαn$ with $α>0$ fixed and we consider a random binomial subgraph $\mathcal{Q}^n_p$ of $\mathcal{Q}^n$ with $p\in(0,1]$ fixed, then with high probability $H\cup\mathcal{Q}^n_p$ contains $k$ edge-disjoint Hamilton cycles, for any fixed $k\in\mathbb{N}$ . In particular, both results resolve a long standing conjecture, posed e.g. by Bollobás, that the threshold probability for Hamiltonicity in the random binomial subgraph of the hypercube equals $1/2$ . Our techniques also show that, with high probability, for all fixed $p\in(0,1]$ the graph $\mathcal{Q}^n_p$ contains an almost spanning cycle. Our methods involve branching processes, the Rödl nibble, and absorption.

preprint2022arXiv

Immersion of complete digraphs in Eulerian digraphs

A digraph $G$ \emph{immerses} a digraph $H$ if there is an injection $f : V(H) \to V(G)$ and a collection of pairwise edge-disjoint directed paths $P_{uv}$ , for $uv \in E(H)$ , such that $P_{uv}$ starts at $u$ and ends at $v$ . We prove that every Eulerian digraph with minimum out-degree $t$ immerses a complete digraph on $Ω(t)$ vertices, thus answering a question of DeVos, Mcdonald, Mohar, and Scheide.

preprint2021arXiv

Path and cycle decompositions of dense graphs

We make progress on three long standing conjectures from the 1960s about path and cycle decompositions of graphs. Gallai conjectured that any connected graph on $n$ vertices can be decomposed into at most $\left\lceil \frac{n}{2}\right\rceil$ paths, while a conjecture of Hajós states that any Eulerian graph on $n$ vertices can be decomposed into at most $\left\lfloor \frac{n-1}{2}\right\rfloor$ cycles. The Erdős-Gallai conjecture states that any graph on $n$ vertices can be decomposed into $O(n)$ cycles and edges. We show that if $G$ is a sufficiently large graph on $n$ vertices with linear minimum degree, then the following hold. (i) $G$ can be decomposed into at most $\frac{n}{2}+o(n)$ paths. (ii) If $G$ is Eulerian, then it can be decomposed into at most $\frac{n}{2}+o(n)$ cycles. (iii) $G$ can be decomposed into at most $\frac{3 n}{2}+o(n)$ cycles and edges. If in addition $G$ satisfies a weak expansion property, we asymptotically determine the required number of paths/cycles for each such $G$ . (iv) $G$ can be decomposed into $\max \left\{\frac{odd(G)}{2},\frac{Δ(G)}{2}\right\}+o(n)$ paths, where $odd(G)$ is the number of odd-degree vertices of $G$ . (v) If $G$ is Eulerian, then it can be decomposed into $\frac{Δ(G)}{2}+o(n)$ cycles. All bounds in (i)-(v) are asymptotically best possible.

preprint2021arXiv

Powers of paths in tournaments

In this short note we prove that every tournament contains the $k$ -th power of a directed path of linear length. This improves upon recent results of Yuster and of Girão. We also give a complete solution for this problem when $k=2$ , showing that there is always a square of a directed path of length $\lceil 2n/3 \rceil-1$ , which is best possible.

preprint2020arXiv

A Canonical Polynomial Van der Waerden's Theorem

We prove a canonical polynomial Van der Waerden's Theorem. More precisely, we show the following. Let $\{p_1(x),\ldots,p_k(x)\}$ be a set of polynomials such that $p_i(x)\in \mathbb{Z}[x]$ and $p_i(0)=0$ , for every $i\in \{1,\ldots,k\}$ . Then, in any colouring of $\mathbb{Z}$ , there exist $a,d\in \mathbb{Z}$ such that $\{a+p_1(d),\ldots,a+p_{k}(d)\}$ forms either a monochromatic or a rainbow set.

preprint2020arXiv

Dirac's theorem for random regular graphs

We prove a `resilience' version of Dirac's theorem in the setting of random regular graphs. More precisely, we show that, whenever $d$ is sufficiently large compared to $\varepsilon>0$ , a.a.s. the following holds: let $G'$ be any subgraph of the random $n$ -vertex $d$ -regular graph $G_{n,d}$ with minimum degree at least $(1/2+\varepsilon)d$ . Then $G'$ is Hamiltonian. This proves a conjecture of Ben-Shimon, Krivelevich and Sudakov. Our result is best possible: firstly, the condition that $d$ is large cannot be omitted, and secondly, the minimum degree bound cannot be improved.

preprint2020arXiv

On Covering Numbers, Young Diagrams, and the Local Dimension of Posets

We study covering numbers and local covering numbers with respect to difference graphs and complete bipartite graphs. In particular we show that in every cover of a Young diagram with $\binom{2k}{k}$ steps with generalized rectangles there is a row or a column in the diagram that is used by at least $k+1$ rectangles, and prove that this is best-possible. This answers two questions by Kim, Martin, Masa{ř}{\'ı}k, Shull, Smith, Uzzell, and Wang (Europ. J. Comb. 2020), namely: - What is the local complete bipartite cover number of a difference graph? - Is there a sequence of graphs with constant local difference graph cover number and unbounded local complete bipartite cover number? We add to the study of these local covering numbers with a lower bound construction and some examples. Following Kim \emph{et al.}, we use the results on local covering numbers to provide lower and upper bounds for the local dimension of partially ordered sets of height~2. We discuss the local dimension of some posets related to Boolean lattices and show that the poset induced by the first two layers of the Boolean lattice has local dimension $(1 + o(1))\log_2\log_2 n$ . We conclude with some remarks on covering numbers for digraphs and Ferrers dimension.

preprint2020arXiv

Subgraphs of large connectivity and chromatic number

Resolving a problem raised by Norin, we show that for each $k \in \mathbb{N}$ , there exists an $f(k) \le 7k$ such that every graph $G$ with chromatic number at least $f(k)+1$ contains a subgraph $H$ with both connectivity and chromatic number at least $k$ . This result is best-possible up to multiplicative constants, and sharpens earlier results of Alon-Kleitman-Thomassen-Saks-Seymour from 1987 showing that $f(k) = O(k^3)$ , and of Chudnovsky-Penev-Scott-Trotignon from 2013 showing that $f(k) = O(k^2)$ . Our methods are robust enough to handle list colouring as well: we also show that for each $k \in \mathbb{N}$ , there exists an $f_\ell(k) \le 4k$ such that every graph $G$ with list chromatic number at least $f_\ell(k)+1$ contains a subgraph $H$ with both connectivity and list chromatic number at least $k$ . This result is again best-possible up to multiplicative constants; here, unlike with $f(\cdot)$ , even the existence of $f_\ell(\cdot)$ appears to have been previously unknown.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

António Girão

Research overview

Is this your work?

10 publications

Cycles with almost linearly many chords

Defective Colouring of Hypergraphs

Hamiltonicity of random subgraphs of the hypercube

Immersion of complete digraphs in Eulerian digraphs

Path and cycle decompositions of dense graphs

Powers of paths in tournaments

A Canonical Polynomial Van der Waerden's Theorem

Dirac's theorem for random regular graphs

On Covering Numbers, Young Diagrams, and the Local Dimension of Posets

Subgraphs of large connectivity and chromatic number

See the researcher in context

Building this map preview