David Munhá Correia

activity

20212025

most citedHamiltonicity of expanders: optimal bounds and applications

1 citations · 2 across the 7 of their papers we have counts for

collaborators

8 papers

math.CO2025

Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions

Nemanja Draganić, Jaehoon Kim, Hyunwoo Lee +3

Dirac's classical theorem asserts that, for $n \geq 3$ , any $n$ -vertex graph with minimum degree at least $n /2$ is Hamiltonian. Furthermore, if we additionally assume that such grap…

math.CO2024★ 1 cited

Hamiltonicity of expanders: optimal bounds and applications

Nemanja Draganić, Richard Montgomery, David Munhá Correia +2

An $n$ -vertex graph $G$ is a $C$ -expander if $∣ N (X) ∣ \geq C ∣ X ∣$ for every $X \subseteq V (G)$ with $∣ X ∣ < n /2 C$ and there is an edge between every two disjoint sets of at least $n /2 C$ …

cs.CC2024

Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs

Jun-Ting Hsieh, Pravesh K. Kothari, Sidhanth Mohanty +2

Given a $k$ -uniform hypergraph $H$ on $n$ vertices, an even cover in $H$ is a collection of hyperedges that touch each vertex an even number of times. Even covers are a generalizat…

math.CO2023

Optimal Hamilton covers and linear arboricity for random graphs

Nemanja Draganić, Stefan Glock, David Munhá Correia +1

In his seminal 1976 paper, Pósa showed that for all $p \geq C lo g n / n$ , the binomial random graph $G (n, p)$ is with high probability Hamiltonian. This leads to the following natural…

math.CO2023

Size-Ramsey numbers of structurally sparse graphs

Nemanja Draganić, Marc Kaufmann, David Munhá Correia +2

Size-Ramsey numbers are a central notion in combinatorics and have been widely studied since their introduction by Erdős, Faudree, Rousseau and Schelp in 1978. Research has mainly…

math.CO2023

A generalization of Bondy's pancyclicity theorem

Nemanja Draganić, David Munhá Correia, Benny Sudakov

The bipartite independence number of a graph $G$ , denoted as $α ~ (G)$ , is the minimal number $k$ such that there exist positive integers $a$ and $b$ with $a + b = k + 1$ with the pro…

math.CO2022★ 1 cited

Turán problems in pseudorandom graphs

Xizhi Liu, Dhruv Mubayi, David Munhá Correia

Given a graph $F$ , we consider the problem of determining the densest possible pseudorandom graph that contains no copy of $F$ . We provide an embedding procedure that improves a ge…

math.CO2021

Tight bound for powers of Hamilton cycles in tournaments

Nemanja Draganić, David Munhá Correia, Benny Sudakov

A basic result in graph theory says that any $n$ -vertex tournament with in- and out-degrees larger than $\frac{n - 2}{4}$ contains a Hamilton cycle, and this is tight. In 1990, Bollo…