BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

António Girão

António Girão contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.CODiscrete Mathematics

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
10works
0followers
2topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

10 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access