Igor Araujo
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Igor Araujo has a total of 62 co-authors. Here are the top co-authors by number of shared publications:
- József Balogh
Department of Mathematics and University of Illinois Urbana-Champaign Urbana IL USA
5 shared publications - Robert A. Krueger
Department of Mathematics University of Illinois at Urbana-Champaign Urbana IL
5 shared publications - Andrew Treglown
University of Birmingham
4 shared publications József Balogh
Department of Mathematics, University of Illinois Urbana-Champaign, Urbana, Illinois 61801, USA
4 shared publications- Simón Piga
University of Birmingham, United Kingdom
4 shared publications - Bernard Lidický
Department of Mathematics Iowa State University Ames Iowa USA
2 shared publications
Latest Publications
- 28 September 2026
- Published by Elsevier in Discrete Mathematics
- Vol. 350 (1)
Monochromatic triangles with empty intersection and Kneser Ramsey numbers
- 28 September 2026
- Published by Elsevier in Discrete Mathematics
- Vol. 350 (1)
Monochromatic triangles with empty intersection and Kneser Ramsey numbers
- Open Access
- 11 April 2025
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 32 (2) , P2.41
On the Off-Diagonal Unordered Erdős-Rado Numbers
Erdős and Rado [Journal of the London Mathematical Society 25 (1950)] introduced the Canonical Ramsey numbers $\text{er}(t)$ as the minimum number $n$ such that every edge-coloring of the ordered complete graph $K_n$ contains either a monochromatic, rainbow, upper lexical, or lower lexical clique of order $t$. Richer [Journal of Combinatorial Theory Series B 80 (2000)] introduced the unordered asymmetric version of the Canonical Ramsey numbers $\text{CR}(s,r)$ as the minimum $n$ such that every edge-coloring of the (unordered) complete graph $K_n$ contains either a rainbow clique of order $r$, or an orderable clique of order $s$.We show that $\text{CR}(s,r) = O(r^3/\log r)^{s-2}$, which, up to the multiplicative constant, matches the known lower bound and improves the previously best known bound $\text{CR}(s,r) = O(r^3/\log r)^{s-1}$ by Jiang [Discrete Mathematics 309 (2009)]. We also obtain bounds on the further variant $\text{ER}(m,\ell,r)$, defined as the minimum $n$ such that every edge-coloring of the (unordered) complete graph $K_n$ contains either a monochromatic $K_m$, lexical $K_\ell$, or rainbow $K_r$.- 11 April 2025
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 32 (2) , P2.41
Open AccessOn the Off-Diagonal Unordered Erdős-Rado Numbers
Erdős and Rado [Journal of the London Mathematical Society 25 (1950)] introduced the Canonical Ramsey numbers $\text{er}(t)$ as the minimum number $n$ such that every edge-coloring of the ordered complete graph $K_n$ contains either a monochromatic, rainbow, upper lexical, or lower lexical clique of order $t$. Richer [Journal of Combinatorial Theory Series B 80 (2000)] introduced the unordered asymmetric version of the Canonical Ramsey numbers $\text{CR}(s,r)$ as the minimum $n$ such that every edge-coloring of the (unordered) complete graph $K_n$ contains either a rainbow clique of order $r$, or an orderable clique of order $s$.We show that $\text{CR}(s,r) = O(r^3/\log r)^{s-2}$, which, up to the multiplicative constant, matches the known lower bound and improves the previously best known bound $\text{CR}(s,r) = O(r^3/\log r)^{s-1}$ by Jiang [Discrete Mathematics 309 (2009)]. We also obtain bounds on the further variant $\text{ER}(m,\ell,r)$, defined as the minimum $n$ such that every edge-coloring of the (unordered) complete graph $K_n$ contains either a monochromatic $K_m$, lexical $K_\ell$, or rainbow $K_r$. - 1 December 2024
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 266 (1) , 383-403
New lower bounds for essential covers of the cube
- 1 December 2024
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 266 (1) , 383-403
New lower bounds for essential covers of the cube
- 7 June 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 38 (2) , 1808-1839
Tiling Edge-Ordered Graphs with Monotone Paths and Other Structures
Given graphs [Formula: see text] and [Formula: see text], a perfect [Formula: see text]-tiling in [Formula: see text] is a collection of vertex-disjoint copies of [Formula: see text] in [Formula: see text] that together cover all the vertices in [Formula: see text]. The study of the minimum degree threshold forcing a perfect [Formula: see text]-tiling in a graph [Formula: see text] has a long history, culminating in the Kühn–Osthus theorem [D. Kühn and D. Osthus, Combinatorica, 29 (2009), pp. 65–107] which resolves this problem, up to an additive constant, for all graphs [Formula: see text]. In this paper we initiate the study of the analogous question for edge-ordered graphs. In particular, we characterize for which edge-ordered graphs [Formula: see text] this problem is well-defined. We also apply the absorbing method to asymptotically determine the minimum degree threshold for forcing a perfect [Formula: see text]-tiling in an edge-ordered graph, where [Formula: see text] is any fixed monotone path.
- 7 June 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 38 (2) , 1808-1839
Tiling Edge-Ordered Graphs with Monotone Paths and Other Structures
Given graphs [Formula: see text] and [Formula: see text], a perfect [Formula: see text]-tiling in [Formula: see text] is a collection of vertex-disjoint copies of [Formula: see text] in [Formula: see text] that together cover all the vertices in [Formula: see text]. The study of the minimum degree threshold forcing a perfect [Formula: see text]-tiling in a graph [Formula: see text] has a long history, culminating in the Kühn–Osthus theorem [D. Kühn and D. Osthus, Combinatorica, 29 (2009), pp. 65–107] which resolves this problem, up to an additive constant, for all graphs [Formula: see text]. In this paper we initiate the study of the analogous question for edge-ordered graphs. In particular, we characterize for which edge-ordered graphs [Formula: see text] this problem is well-defined. We also apply the absorbing method to asymptotically determine the minimum degree threshold for forcing a perfect [Formula: see text]-tiling in an edge-ordered graph, where [Formula: see text] is any fixed monotone path.
- 25 April 2024
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 73 (2) , 569-593
Triangle Percolation on the Grid
- 25 April 2024
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 73 (2) , 569-593
Triangle Percolation on the Grid
- Open Access
Triangle Percolation on the Grid
We consider a geometric percolation process partially motivated by recent work of Hejda and Kala. Specifically, we start with an initial set $X \subseteq \mathbb{Z}^2$, and then iteratively check whether there exists a triangle $T \subseteq \mathbb{R}^2$ with its vertices in $\mathbb{Z}^2$ such that $T$ contains exactly four points of $\mathbb{Z}^2$ and exactly three points of $X$. In this case, we add the missing lattice point of $T$ to $X$, and we repeat until no such triangle exists. We study the limit sets $S$, the sets stable under this process, including determining their possible densities and some of their structure.Open AccessTriangle Percolation on the Grid
We consider a geometric percolation process partially motivated by recent work of Hejda and Kala. Specifically, we start with an initial set $X \subseteq \mathbb{Z}^2$, and then iteratively check whether there exists a triangle $T \subseteq \mathbb{R}^2$ with its vertices in $\mathbb{Z}^2$ such that $T$ contains exactly four points of $\mathbb{Z}^2$ and exactly three points of $X$. In this case, we add the missing lattice point of $T$ to $X$, and we repeat until no such triangle exists. We study the limit sets $S$, the sets stable under this process, including determining their possible densities and some of their structure. - Open Access
Tiling edge-ordered graphs with monotone paths and other structures
Given graphs $F$ and $G$, a perfect $F$-tiling in $G$ is a collection of vertex-disjoint copies of $F$ in $G$ that together cover all the vertices in $G$. The study of the minimum degree threshold forcing a perfect $F$-tiling in a graph $G$ has a long history, culminating in the Kühn--Osthus theorem [Combinatorica 2009] which resolves this problem, up to an additive constant, for all graphs $F$. In this paper we initiate the study of the analogous question for edge-ordered graphs. In particular, we characterize for which edge-ordered graphs $F$ this problem is well-defined. We also apply the absorbing method to asymptotically determine the minimum degree threshold for forcing a perfect $P$-tiling in an edge-ordered graph, where $P$ is any fixed monotone path.Open AccessTiling edge-ordered graphs with monotone paths and other structures
Given graphs $F$ and $G$, a perfect $F$-tiling in $G$ is a collection of vertex-disjoint copies of $F$ in $G$ that together cover all the vertices in $G$. The study of the minimum degree threshold forcing a perfect $F$-tiling in a graph $G$ has a long history, culminating in the Kühn--Osthus theorem [Combinatorica 2009] which resolves this problem, up to an additive constant, for all graphs $F$. In this paper we initiate the study of the analogous question for edge-ordered graphs. In particular, we characterize for which edge-ordered graphs $F$ this problem is well-defined. We also apply the absorbing method to asymptotically determine the minimum degree threshold for forcing a perfect $P$-tiling in an edge-ordered graph, where $P$ is any fixed monotone path. - Open Access
On oriented cycles in randomly perturbed digraphs
In 2003, Bohman, Frieze, and Martin initiated the study of randomly perturbed graphs and digraphs. For digraphs, they showed that for every $\alpha>0$, there exists a constant $C$ such that for every $n$-vertex digraph of minimum semi-degree at least $\alpha n$, if one adds $Cn$ random edges then asymptotically almost surely the resulting digraph contains a consistently oriented Hamilton cycle. We generalize their result, showing that the hypothesis of this theorem actually asymptotically almost surely ensures the existence of every orientation of a cycle of every possible length, simultaneously. Moreover, we prove that we can relax the minimum semi-degree condition to a minimum total degree condition when considering orientations of a cycle that do not contain a large number of vertices of indegree $1$. Our proofs make use of a variant of an absorbing method of Montgomery.Open AccessOn oriented cycles in randomly perturbed digraphs
In 2003, Bohman, Frieze, and Martin initiated the study of randomly perturbed graphs and digraphs. For digraphs, they showed that for every $\alpha>0$, there exists a constant $C$ such that for every $n$-vertex digraph of minimum semi-degree at least $\alpha n$, if one adds $Cn$ random edges then asymptotically almost surely the resulting digraph contains a consistently oriented Hamilton cycle. We generalize their result, showing that the hypothesis of this theorem actually asymptotically almost surely ensures the existence of every orientation of a cycle of every possible length, simultaneously. Moreover, we prove that we can relax the minimum semi-degree condition to a minimum total degree condition when considering orientations of a cycle that do not contain a large number of vertices of indegree $1$. Our proofs make use of a variant of an absorbing method of Montgomery. - Open Access
- 6 October 2023
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 30 (4) , P4.22
On the Maximum $F_5$-Free Subhypergraphs of a Random Hypergraph
Denote by $F_5$ the $3$-uniform hypergraph on vertex set $\{1,2,3,4,5\}$ with hyperedges $\{123,124,345\}$. Balogh, Butterfield, Hu, and Lenz proved that if $p > K \log n /n$ for some large constant $K$, then every maximum $F_5$-free subhypergraph of $G^3(n,p)$ is tripartite with high probability, and showed that if $p_0 = 0.1\sqrt{\log n} /n$, then with high probability there exists a maximum $F_5$-free subhypergraph of $G^3(n,p_0)$ that is not tripartite. In this paper, we sharpen the upper bound to be best possible up to a constant factor. We prove that if $p > C \sqrt{\log n} /n $ for some large constant $C$, then every maximum $F_5$-free subhypergraph of $G^3(n, p)$ is tripartite with high probability.- 6 October 2023
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 30 (4) , P4.22
Open AccessOn the Maximum $F_5$-Free Subhypergraphs of a Random Hypergraph
Denote by $F_5$ the $3$-uniform hypergraph on vertex set $\{1,2,3,4,5\}$ with hyperedges $\{123,124,345\}$. Balogh, Butterfield, Hu, and Lenz proved that if $p > K \log n /n$ for some large constant $K$, then every maximum $F_5$-free subhypergraph of $G^3(n,p)$ is tripartite with high probability, and showed that if $p_0 = 0.1\sqrt{\log n} /n$, then with high probability there exists a maximum $F_5$-free subhypergraph of $G^3(n,p_0)$ that is not tripartite. In this paper, we sharpen the upper bound to be best possible up to a constant factor. We prove that if $p > C \sqrt{\log n} /n $ for some large constant $C$, then every maximum $F_5$-free subhypergraph of $G^3(n, p)$ is tripartite with high probability. - Open Access
- 28 August 2023
- Published by Masaryk University Press in European Conference on Combinatorics, Graph Theory and Applications
- No. 12,p. 74-81
Tiling problems in edge-ordered graphs
Given graphs $F$ and $G$, a perfect $F$-tiling in $G$ is a collection of vertex-disjoint copies of $F$ in $G$ that together cover all the vertices in $G$. The study of the minimum degree threshold forcing a perfect $F$-tiling in a graph $G$ has a long history, culminating in the Kühn-Osthus theorem [Combinatorica 2009] which resolves this problem, up to an additive constant, for all graphs $F$. We initiate the study of the analogous question for edge-ordered graphs. In particular, we characterize for which edge-ordered graphs $F$ this problem is well-defined. We also apply the absorbing method to asymptotically determine the minimum degree threshold for forcing a perfect $P$-tiling in an edge-ordered graph, where $P$ is any fixed monotone path.- 28 August 2023
- Published by Masaryk University Press in European Conference on Combinatorics, Graph Theory and Applications
- No. 12,p. 74-81
Open AccessTiling problems in edge-ordered graphs
Given graphs $F$ and $G$, a perfect $F$-tiling in $G$ is a collection of vertex-disjoint copies of $F$ in $G$ that together cover all the vertices in $G$. The study of the minimum degree threshold forcing a perfect $F$-tiling in a graph $G$ has a long history, culminating in the Kühn-Osthus theorem [Combinatorica 2009] which resolves this problem, up to an additive constant, for all graphs $F$. We initiate the study of the analogous question for edge-ordered graphs. In particular, we characterize for which edge-ordered graphs $F$ this problem is well-defined. We also apply the absorbing method to asymptotically determine the minimum degree threshold for forcing a perfect $P$-tiling in an edge-ordered graph, where $P$ is any fixed monotone path.