Yoshiharu Kohayakawa
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
Yoshiharu Kohayakawa has a total of 217 co-authors. Here are the top co-authors by number of shared publications:
- Guilherme Oliveira Mota
Universidade de São Paulo
22 shared publications - Carlos Hoppen
Instituto de Matemática e Estatística, Universidade Federal do Rio Grande do Sul, Porto Alegre, Brazil
20 shared publications - Julia Böttcher
Department of Mathematics The London School of Economics London UK
19 shared publications - Vojtěch Rödl
Emory Univ, Atlanta, GA 30322 USA
16 shared publications Vojtěch Rödl
Department of Mathematics and Computer Science Emory University Atlanta Georgia 30322
15 shared publications- Mathias Schacht
Universität Hamburg
12 shared publications
Latest Publications
- Open Access
- 13 October 2026
- Published by Wiley in Random Structures & Algorithms
- Vol. 69 (3)
Robustness of the Sauer–Spencer Theorem
We prove a robust version of a graph embedding theorem of Sauer and Spencer. To state this sparser analogue, we define to be a random subgraph of obtained by retaining each edge of independently with probability , and let be the maximum 1‐density of a graph . We show that for any constant and , if is an ‐vertex host graph with minimum degree and is an ‐vertex graph with maximum degree , then for , the random subgraph contains a copy of with high probability. Our value for is optimal up to a log‐factor. In fact, we prove this result for a more general minimum degree condition on , by introducing an extension threshold , such that the above result holds for graphs with . We show that , and further conjecture that equals , which matches the minimum degree condition on in the Bollobás–Eldridge–Catlin Conjecture. A main tool in our proof is a vertex‐spread version of the blow‐up lemma of Allen, Böttcher, Hàn, Kohayakawa, and Person, which we believe to be of independent interest.
- 13 October 2026
- Published by Wiley in Random Structures & Algorithms
- Vol. 69 (3)
Open AccessRobustness of the Sauer–Spencer Theorem
We prove a robust version of a graph embedding theorem of Sauer and Spencer. To state this sparser analogue, we define to be a random subgraph of obtained by retaining each edge of independently with probability , and let be the maximum 1‐density of a graph . We show that for any constant and , if is an ‐vertex host graph with minimum degree and is an ‐vertex graph with maximum degree , then for , the random subgraph contains a copy of with high probability. Our value for is optimal up to a log‐factor. In fact, we prove this result for a more general minimum degree condition on , by introducing an extension threshold , such that the above result holds for graphs with . We show that , and further conjecture that equals , which matches the minimum degree condition on in the Bollobás–Eldridge–Catlin Conjecture. A main tool in our proof is a vertex‐spread version of the blow‐up lemma of Allen, Böttcher, Hàn, Kohayakawa, and Person, which we believe to be of independent interest.
- 6 August 2026
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- p. 1-27
A canonical Ramsey theorem for even cycles in random graphs
The celebrated canonical Ramsey theorem of Erdős and Rado implies that for 2 less than or equals k element of double struck upper N $2\leq k\in {\mathbb{N}}$ , any colouring of the edges of upper K Subscript n $K_n$ with n $n$ sufficiently large gives a copy of upper C Subscript 2 k $C_{2k}$ which has one of three canonical colour patterns: monochromatic, rainbow or lexicographic. In this paper we show that if p equals omega left parenthesis n Superscript negative 1 plus 1 divided by left parenthesis 2 k minus 1 right parenthesis Baseline log n right parenthesis $p=\omega (n^{-1+1/(2k-1)}\log n)$ , then bold upper G left parenthesis n comma p right parenthesis ${\mathbf G}(n,p)$ will asymptotically almost surely also have the property that any colouring of its edges induces canonical copies of upper C Subscript 2 k $C_{2k}$ . This determines the threshold for the canonical Ramsey property with respect to even cycles, up to a log $\log$ factor.- 6 August 2026
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- p. 1-27
A canonical Ramsey theorem for even cycles in random graphs
The celebrated canonical Ramsey theorem of Erdős and Rado implies that for 2 less than or equals k element of double struck upper N $2\leq k\in {\mathbb{N}}$ , any colouring of the edges of upper K Subscript n $K_n$ with n $n$ sufficiently large gives a copy of upper C Subscript 2 k $C_{2k}$ which has one of three canonical colour patterns: monochromatic, rainbow or lexicographic. In this paper we show that if p equals omega left parenthesis n Superscript negative 1 plus 1 divided by left parenthesis 2 k minus 1 right parenthesis Baseline log n right parenthesis $p=\omega (n^{-1+1/(2k-1)}\log n)$ , then bold upper G left parenthesis n comma p right parenthesis ${\mathbf G}(n,p)$ will asymptotically almost surely also have the property that any colouring of its edges induces canonical copies of upper C Subscript 2 k $C_{2k}$ . This determines the threshold for the canonical Ramsey property with respect to even cycles, up to a log $\log$ factor.- Open Access
Robustness of the Sauer-Spencer Theorem
We prove a robust version of a graph embedding theorem of Sauer and Spencer. To state this sparser analogue, we define $G(p)$ to be a random subgraph of $G$ obtained by retaining each edge of $G$ independently with probability $p \in [0,1]$, and let $m_1(H)$ be the maximum $1$-density of a graph $H$. We show that for any constant $Δ$ and $γ> 0$, if $G$ is an $n$-vertex host graph with minimum degree $δ(G) \geq (1 - 1/2Δ+ γ)n$ and $H$ is an $n$-vertex graph with maximum degree $Δ(H) \leq Δ$, then for $p \geq Cn^{-1/m_1(H)}\log n$, the random subgraph $G(p)$ contains a copy of $H$ with high probability. Our value for $p$ is optimal up to a log-factor. In fact, we prove this result for a more general minimum degree condition on $G$, by introducing an \emph{extension threshold} $δ_{\rm e}(Δ)$, such that the above result holds for graphs $G$ with ${δ(G) \geq (δ_{\rm e}(Δ) + γ)n}$. We show that $δ_{\rm e}(Δ) \leq (2Δ-1)/2Δ$, and further conjecture that $δ_{\rm e}(Δ)$ equals $Δ/(Δ+1)$, which matches the minimum degree condition on $G$ in the Bollobás-Eldridge-Catlin Conjecture. A main tool in our proof is a vertex-spread version of the blow-up lemma of Allen, Böttcher, Hàn, Kohayakawa, and Person, which we believe to be of independent interest.Open AccessRobustness of the Sauer-Spencer Theorem
We prove a robust version of a graph embedding theorem of Sauer and Spencer. To state this sparser analogue, we define $G(p)$ to be a random subgraph of $G$ obtained by retaining each edge of $G$ independently with probability $p \in [0,1]$, and let $m_1(H)$ be the maximum $1$-density of a graph $H$. We show that for any constant $Δ$ and $γ> 0$, if $G$ is an $n$-vertex host graph with minimum degree $δ(G) \geq (1 - 1/2Δ+ γ)n$ and $H$ is an $n$-vertex graph with maximum degree $Δ(H) \leq Δ$, then for $p \geq Cn^{-1/m_1(H)}\log n$, the random subgraph $G(p)$ contains a copy of $H$ with high probability. Our value for $p$ is optimal up to a log-factor. In fact, we prove this result for a more general minimum degree condition on $G$, by introducing an \emph{extension threshold} $δ_{\rm e}(Δ)$, such that the above result holds for graphs $G$ with ${δ(G) \geq (δ_{\rm e}(Δ) + γ)n}$. We show that $δ_{\rm e}(Δ) \leq (2Δ-1)/2Δ$, and further conjecture that $δ_{\rm e}(Δ)$ equals $Δ/(Δ+1)$, which matches the minimum degree condition on $G$ in the Bollobás-Eldridge-Catlin Conjecture. A main tool in our proof is a vertex-spread version of the blow-up lemma of Allen, Böttcher, Hàn, Kohayakawa, and Person, which we believe to be of independent interest. - Open Access
- 1 July 2024
- Published by EDP Sciences in RAIRO - Operations Research
- Vol. 58 (4) , 3607-3619
Directed graphs with lower orientation Ramsey thresholds
We investigate the threshold p⃗H = p⃗H (n) for the Ramsey-type property G(n, p) → ⃗H, where G(n, p) is the binomial random graph and G → ⃗H indicates that every orientation of the graph G contains the oriented graph ⃗ H as a subdigraph. Similarly to the classical Ramsey setting, the upper bound p⃗H ⩽ Cn−1/m2(⃗ H) is known to hold for some constant C = C( ⃗ H), where m2(⃗H) denotes the maximum 2-density of the underlying graph H of ⃗ H. While this upper bound is indeed the threshold for some ⃗H, this is not always the case. We obtain examples arising from rooted products of orientations of sparse graphs (such as forests, cycles and, more generally, subcubic {K3, K3,3}-free graphs) and arbitrarily rooted transitive triangles.
- 1 July 2024
- Published by EDP Sciences in RAIRO - Operations Research
- Vol. 58 (4) , 3607-3619
Open AccessDirected graphs with lower orientation Ramsey thresholds
We investigate the threshold p⃗H = p⃗H (n) for the Ramsey-type property G(n, p) → ⃗H, where G(n, p) is the binomial random graph and G → ⃗H indicates that every orientation of the graph G contains the oriented graph ⃗ H as a subdigraph. Similarly to the classical Ramsey setting, the upper bound p⃗H ⩽ Cn−1/m2(⃗ H) is known to hold for some constant C = C( ⃗ H), where m2(⃗H) denotes the maximum 2-density of the underlying graph H of ⃗ H. While this upper bound is indeed the threshold for some ⃗H, this is not always the case. We obtain examples arising from rooted products of orientations of sparse graphs (such as forests, cycles and, more generally, subcubic {K3, K3,3}-free graphs) and arbitrarily rooted transitive triangles.
- Open Access
- 6 June 2023
- Published by Wiley in Journal of Graph Theory
- Vol. 103 (4) , 603-605
Issue Information
- 6 June 2023
- Published by Wiley in Journal of Graph Theory
- Vol. 103 (4) , 603-605
Open AccessIssue Information
- 8 March 2023
- Published by Wiley in Journal of Graph Theory
- Vol. 103 (4) , 767-779
The mod k $k$ chromatic index of random graphsThe mod chromatic index of a graph is the minimum number of colors needed to color the edges of in a way that the subgraph spanned by the edges of each color has all degrees congruent to . Recently, the authors proved that the mod chromatic index of every graph is at most , improving, for large , a result of Scott. Here we study the mod chromatic index of random graphs. We prove that for every integer , there is such that if and as , then the following holds: if is odd, then the mod chromatic index of is asymptotically almost surely (a.a.s.) equal to , while if is even, then the mod chromatic index of (respectively, ) is a.a.s. equal to (respectively, ).
- 8 March 2023
- Published by Wiley in Journal of Graph Theory
- Vol. 103 (4) , 767-779
The mod k $k$ chromatic index of random graphsThe mod chromatic index of a graph is the minimum number of colors needed to color the edges of in a way that the subgraph spanned by the edges of each color has all degrees congruent to . Recently, the authors proved that the mod chromatic index of every graph is at most , improving, for large , a result of Scott. Here we study the mod chromatic index of random graphs. We prove that for every integer , there is such that if and as , then the following holds: if is odd, then the mod chromatic index of is asymptotically almost surely (a.a.s.) equal to , while if is even, then the mod chromatic index of (respectively, ) is a.a.s. equal to (respectively, ).
- Open Access
- 1 February 2023
- Published by Springer Nature in Algorithmica
- Vol. 85 (8) , 2482-2484
Guest Editorial: Special Issue on Theoretical Informatics
- 1 February 2023
- Published by Springer Nature in Algorithmica
- Vol. 85 (8) , 2482-2484
Open AccessGuest Editorial: Special Issue on Theoretical Informatics
- 1 February 2023
- Published by Elsevier in Discrete Mathematics
- Vol. 346 (5)
The anti-Ramsey threshold of complete graphs
- 1 February 2023
- Published by Elsevier in Discrete Mathematics
- Vol. 346 (5)
The anti-Ramsey threshold of complete graphs
- Open Access
The anti-Ramsey threshold of complete graphs
For graphs $G$ and $H$, let $G {\displaystyle\smash{\begin{subarray}{c} \hbox{$\tiny\rm rb$} \\ \longrightarrow \\ \hbox{$\tiny\rm p$} \end{subarray}}}H$ denote the property that for every proper edge-colouring of $G$ there is a rainbow $H$ in $G$. It is known that, for every graph $H$, an asymptotic upper bound for the threshold function $p^{\rm rb}_H=p^{\rm rb}_H(n)$ of this property for the random graph $G(n,p)$ is $n^{-1/m^{(2)}(H)}$, where $m^{(2)}(H)$ denotes the so-called maximum $2$-density of $H$. Extending a result of Nenadov, Person, \v{S}kori\'c, and Steger [J. Combin. Theory Ser. B 124 (2017),1-38] we prove a matching lower bound for $p^{\rm rb}_{K_k}$ for $k\geq 5$. Furthermore, we show that $p^{\rm rb}_{K_4} = n^{-7/15}$.Open AccessThe anti-Ramsey threshold of complete graphs
For graphs $G$ and $H$, let $G {\displaystyle\smash{\begin{subarray}{c} \hbox{$\tiny\rm rb$} \\ \longrightarrow \\ \hbox{$\tiny\rm p$} \end{subarray}}}H$ denote the property that for every proper edge-colouring of $G$ there is a rainbow $H$ in $G$. It is known that, for every graph $H$, an asymptotic upper bound for the threshold function $p^{\rm rb}_H=p^{\rm rb}_H(n)$ of this property for the random graph $G(n,p)$ is $n^{-1/m^{(2)}(H)}$, where $m^{(2)}(H)$ denotes the so-called maximum $2$-density of $H$. Extending a result of Nenadov, Person, \v{S}kori\'c, and Steger [J. Combin. Theory Ser. B 124 (2017),1-38] we prove a matching lower bound for $p^{\rm rb}_{K_k}$ for $k\geq 5$. Furthermore, we show that $p^{\rm rb}_{K_4} = n^{-7/15}$. - 28 April 2022
- Published by Springer Nature in São Paulo Journal of Mathematical Sciences
- Vol. 16 (1) , 1-4
Opening Note: The Golden Jubilee of the Institute of Mathematics and Statistics of the University of São Paulo
- 28 April 2022
- Published by Springer Nature in São Paulo Journal of Mathematical Sciences
- Vol. 16 (1) , 1-4
Opening Note: The Golden Jubilee of the Institute of Mathematics and Statistics of the University of São Paulo