IAIgor Araujo

Igor Araujo

*This is an algorithmically generated author record based on publicly available information.

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


Igor Araujo has a total of 62 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    On the Off-Diagonal Unordered Erdős-Rado Numbers

    by Igor Araujo, Dadong Peng

    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$.

  • New lower bounds for essential covers of the cube

    by Igor Araujo, József Balogh, Letícia Mattos


  • Tiling Edge-Ordered Graphs with Monotone Paths and Other Structures

    by Igor Araujo, Simón Piga, Andrew Treglown, Zimu Xiang

    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.


  • Triangle Percolation on the Grid

    by Igor Araujo, Bryce Frederickson, Robert A. Krueger, Bernard Lidický, Tyrrell B. McAllister, Florian Pfender, Sam Spiro, Eric Nathan Stucky

  • Open Access

    Triangle Percolation on the Grid

    by Igor Araujo, Bryce Frederickson, Robert A. Krueger, Bernard Lidický, Tyrrell B. McAllister, Florian Pfender, Sam Spiro, Eric Nathan Stucky

    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

    by Igor Araujo, Simón Piga, Andrew Treglown, Zimu Xiang

    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

    by Igor Araujo, József Balogh, Robert A. Krueger, Simón Piga, Andrew Treglown

    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

    On the Maximum $F_5$-Free Subhypergraphs of a Random Hypergraph

    by Igor Araujo, József Balogh, Haoran Luo

    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

    Tiling problems in edge-ordered graphs

    by Igor Araujo, Simón Piga, Andrew Treglown, Zimu Xiang

    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.