Source author record

Yoshiharu Kohayakawa

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms math.PR Discrete Mathematics

Catalog footprint

Research overview

24works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

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, Škorić, 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}$ .

preprint2022arXiv

The threshold for the constrained Ramsey property

Given graphs $G$ , $H_1$ , and $H_2$ , let $G\xrightarrow{\text{mr}}(H_1,H_2)$ denote the property that in every edge colouring of $G$ there is a monochromatic copy of $H_1$ or a rainbow copy of $H_2$ . The constrained Ramsey number, defined as the minimum $n$ such that $K_n\xrightarrow{\text{mr}}(H_1,H_2)$ , exists if and only if $H_1$ is a star or $H_2$ is a forest. We determine the threshold for the property $G(n,p)\xrightarrow{\text{mr}}(H_1,H_2)$ when $H_2$ is a forest, explicitly when the threshold is $Ω(n^{-1})$ and implicitly otherwise.

preprint2021arXiv

On the query complexity of estimating the distance to hereditary graph properties

Given a family of graphs $\mathcal{F}$ , we prove that the normalized edit distance of any given graph $Γ$ to being induced $\mathcal{F}$ -free is estimable with a query complexity that depends only on the bounds of the Frieze--Kannan Regularity Lemma and on a Removal Lemma for $\mathcal{F}$ .

preprint2020arXiv

Covering $3$ -edge-coloured random graphs with monochromatic trees

We investigate the problem of determining how many monochromatic trees are necessary to cover the vertices of an edge-coloured random graph. More precisely, we show that for $p\gg n^{-1/6}{(\ln n)}^{1/6}$ , in any $3$ -edge-colouring of the random graph $G(n,p)$ we can find three monochromatic trees such that their union covers all vertices. This improves, for three colours, a result of Bucić, Korándi and Sudakov.

preprint2020arXiv

The mod $k$ chromatic index of graphs is $O(k)$

Let $χ'_k(G)$ denote the minimum number of colors needed to color the edges of a graph $G$ in a way that the subgraph spanned by the edges of each color has all degrees congruent to $1 \pmod k$ . Scott [{\em Discrete Math. 175}, 1-3 (1997), 289--291] proved that $χ'_k(G)\leq5k^2\log k$ , and thus settled a question of Pyber [{\em Sets, graphs and numbers} (1992), pp. 583--610], who had asked whether $χ_k'(G)$ can be bounded solely as a function of $k$ . We prove that $χ'_k(G)=O(k)$ , answering affirmatively a question of Scott.

preprint2019arXiv

Counting restricted orientations of random graphs

We count orientations of $G(n,p)$ avoiding certain classes of oriented graphs. In particular, we study $T_r(n,p)$ , the number of orientations of the binomial random graph $G(n,p)$ in which every copy of $K_r$ is transitive, and $S_r(n,p)$ , the number of orientations of $G(n,p)$ containing no strongly connected copy of $K_r$ . We give the correct order of growth of $\log T_r(n,p)$ and $\log S_r(n,p)$ up to polylogarithmic factors; for orientations with no cyclic triangle, this significantly improves a result of Allen, Kohayakawa, Mota and Parente. We also discuss the problem for a single forbidden oriented graph, and state a number of open problems and conjectures.

preprint2019arXiv

The size-Ramsey number of powers of bounded degree trees

Given a positive integer $s$ , the $s$ -colour size-Ramsey number of a graph $H$ is the smallest integer $m$ such that there exists a graph $G$ with $m$ edges with the property that, in any colouring of $E(G)$ with $s$ colours, there is a monochromatic copy of $H$ . We prove that, for any positive integers $k$ and $s$ , the $s$ -colour size-Ramsey number of the $k$ th power of any $n$ -vertex bounded degree tree is linear in $n$ . As a corollary we obtain that the $s$ -colour size-Ramsey number of $n$ -vertex graphs with bounded treewidth and bounded degree is linear in $n$ , which answers a question raised by Kamčev, Liebenau, Wood and Yepremyan [The size Ramsey number of graphs with bounded treewidth, arXiv:1906.09185 (2019)].

preprint2017arXiv

Estimating parameters associated with monotone properties

There has been substantial interest in estimating the value of a graph parameter, i.e., of a real-valued function defined on the set of finite graphs, by querying a randomly sampled substructure whose size is independent of the size of the input. Graph parameters that may be successfully estimated in this way are said to be testable or estimable, and the sample complexity $q_z=q_z(ε)$ of an estimable parameter $z$ is the size of a random sample of a graph $G$ required to ensure that the value of $z(G)$ may be estimated within an error of $ε$ with probability at least 2/3. In this paper, for any fixed monotone graph property $\mathcal{P}=\mbox{Forb}(\mathcal{F})$, we study the sample complexity of estimating a bounded graph parameter $z_{\mathcal{P}}$ that, for an input graph $G$ , counts the number of spanning subgraphs of $G$ that satisfy $\mathcal{P}$ . To improve upon previous upper bounds on the sample complexity, we show that the vertex set of any graph that satisfies a monotone property $\mathcal{P}$ may be partitioned equitably into a constant number of classes in such a way that the cluster graph induced by the partition is not far from satisfying a natural weighted graph generalization of $\mathcal{P}$ . Properties for which this holds are said to be recoverable, and the study of recoverable properties may be of independent interest.

preprint2016arXiv

Chromatic thresholds in dense random graphs

The chromatic threshold $δ_χ(H,p)$ of a graph $H$ with respect to the random graph $G(n,p)$ is the infimum over $d > 0$ such that the following holds with high probability: the family of $H$ -free graphs $G \subset G(n,p)$ with minimum degree $δ(G) \ge dpn$ has bounded chromatic number. The study of the parameter $δ_χ(H) := δ_χ(H,1)$ was initiated in 1973 by Erdős and Simonovits, and was recently determined for all graphs $H$ . In this paper we show that $δ_χ(H,p) = δ_χ(H)$ for all fixed $p \in (0,1)$ , but that typically $δ_χ(H,p) \ne δ_χ(H)$ if $p = o(1)$ . We also make significant progress towards determining $δ_χ(H,p)$ for all graphs $H$ in the range $p = n^{-o(1)}$ . In sparser random graphs the problem is somewhat more complicated, and is studied in a separate paper.

preprint2016arXiv

Chromatic thresholds in sparse random graphs

The chromatic threshold $δ_χ(H,p)$ of a graph $H$ with respect to the random graph $G(n,p)$ is the infimum over $d > 0$ such that the following holds with high probability: the family of $H$ -free graphs $G \subset G(n,p)$ with minimum degree $δ(G) \ge dpn$ has bounded chromatic number. The study of $δ_χ(H) :=δ_χ(H,1)$ was initiated in 1973 by Erdős and Simonovits. Recently $δ_χ(H)$ was determined for all graphs $H$ . It is known that $δ_χ(H,p) =δ_χ(H)$ for all fixed $p \in (0,1)$ , but that typically $δ_χ(H,p) \ne δ_χ(H)$ if $p = o(1)$ . Here we study the problem for sparse random graphs. We determine $δ_χ(H,p)$ for most functions $p = p(n)$ when $H\in\{K_3,C_5\}$ , and also for all graphs $H$ with $χ(H) \not\in \{3,4\}$ .

preprint2016arXiv

Densities in large permutations and parameter testing

A classical theorem of Erdos, Lovasz and Spencer asserts that the densities of connected subgraphs in large graphs are independent. We prove an analogue of this theorem for permutations and we then apply the methods used in the proof to give an example of a finitely approximable permutation parameter that is not finitely forcible. The latter answers a question posed by two of the authors and Moreira and Sampaio.

preprint2016arXiv

Discrepancy and Eigenvalues of Cayley Graphs

We consider quasirandom properties for Cayley graphs of finite abelian groups. We show that having uniform edge-distribution (i.e., small discrepancy) and having large eigenvalue gap are equivalent properties for such Cayley graphs, even if they are sparse. This positively answers a question of Chung and Graham ["Sparse quasi-random graphs", Combinatorica 22 (2002), no. 2, 217-244] for the particular case of Cayley graphs of abelian groups, while in general the answer is negative.

preprint2016arXiv

The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton--Milner family

The celebrated Erdős-Ko-Rado theorem determines the maximum size of a $k$ -uniform intersecting family. The Hilton-Milner theorem determines the maximum size of a $k$ -uniform intersecting family that is not a subfamily of the so-called Erdős-Ko-Rado family. In turn, it is natural to ask what the maximum size of an intersecting $k$ -uniform family that is neither a subfamily of the Erdős-Ko-Rado family nor of the Hilton-Milner family is. For $k\ge 4$ , this was solved (implicitly) in the same paper by Hilton-Milner in 1967. We give a different and simpler proof, based on the shifting method, which allows us to solve all cases $k\ge 3$ and characterize all extremal families achieving the extremal value.

preprint2016arXiv

Upper bounds on probability thresholds for asymmetric Ramsey properties

Given two graphs $G$ and $H$ , we investigate for which functions $p=p(n)$ the random graph $G_{n,p}$ (the binomial random graph on $n$ vertices with edge probability $p$ ) satisfies with probability $1-o(1)$ that every red-blue-coloring of its edges contains a red copy of $G$ or a blue copy of $H$ . We prove a general upper bound on the threshold for this property under the assumption that the denser of the two graphs satisfies a certain balancedness condition. Our result partially confirms a conjecture by the first author and Kreuter, and together with earlier lower bound results establishes the exact order of magnitude of the threshold for the case in which $G$ and $H$ are complete graphs of arbitrary size. In our proof we present an alternative to the so-called deletion method, which was introduced by Rödl and Ruciński in their study of symmetric Ramsey properties of random graphs (i.e. the case $G=H$ ), and has been used in many proofs of similar results since then.

preprint2015arXiv

Triangle-free subgraphs of random graphs

Recently there has been much interest in studying random graph analogues of well known classical results in extremal graph theory. Here we follow this trend and investigate the structure of triangle-free subgraphs of $G(n,p)$ with high minimum degree. We prove that asymptotically almost surely each triangle-free spanning subgraph of $G(n,p)$ with minimum degree at least $\big(\frac{2}{5} + o(1)\big)pn$ is $\mathcal O(p^{-1}n)$ -close to bipartite, and each spanning triangle-free subgraph of $G(n,p)$ with minimum degree at least $(\frac{1}{3}+\varepsilon)pn$ is $\mathcal O(p^{-1}n)$ -close to $r$ -partite for some $r=r(\varepsilon)$ . These are random graph analogues of a result by Andrásfai, Erdős, and Sós [Discrete Math. 8 (1974), 205-218], and a result by Thomassen [Combinatorica 22 (2002), 591--596]. We also show that our results are best possible up to a constant factor.

preprint2014arXiv

Powers of Hamilton cycles in pseudorandom graphs

We study the appearance of powers of Hamilton cycles in pseudorandom graphs, using the following comparatively weak pseudorandomness notion. A graph $G$ is $(\varepsilon,p,k,\ell)$ -pseudorandom if for all disjoint $X$ and $Y\subset V(G)$ with $|X|\ge\varepsilon p^kn$ and $|Y|\ge\varepsilon p^\ell n$ we have $e(X,Y)=(1\pm\varepsilon)p|X||Y|$ . We prove that for all $β>0$ there is an $\varepsilon>0$ such that an $(\varepsilon,p,1,2)$ -pseudorandom graph on $n$ vertices with minimum degree at least $βpn$ contains the square of a Hamilton cycle. In particular, this implies that $(n,d,λ)$ -graphs with $λ\ll d^{5/2 }n^{-3/2}$ contain the square of a Hamilton cycle, and thus a triangle factor if $n$ is a multiple of $3$ . This improves on a result of Krivelevich, Sudakov and Szabó [Triangle factors in sparse pseudo-random graphs, Combinatorica 24 (2004), no. 3, 403--426]. We also extend our result to higher powers of Hamilton cycles and establish corresponding counting versions.

preprint2013arXiv

Almost spanning subgraphs of random graphs after adversarial edge removal

Let Delta>1 be a fixed integer. We show that the random graph G(n,p) with p>>(log n/n)^{1/Delta} is robust with respect to the containment of almost spanning bipartite graphs H with maximum degree Delta and sublinear bandwidth in the following sense: asymptotically almost surely, if an adversary deletes arbitrary edges in G(n,p) such that each vertex loses less than half of its neighbours, then the resulting graph still contains a copy of all such H.

preprint2013arXiv

An Extension of the Blow-up Lemma to arrangeable graphs

The Blow-up Lemma established by Komlós, Sárközy, and Szemerédi in 1997 is an important tool for the embedding of spanning subgraphs of bounded maximum degree. Here we prove several generalisations of this result concerning the embedding of a-arrangeable graphs, where a graph is called a-arrangeable if its vertices can be ordered in such a way that the neighbours to the right of any vertex v have at most a neighbours to the left of v in total. Examples of arrangeable graphs include planar graphs and, more generally, graphs without a K_s-subdivision for constant s. Our main result shows that a-arrangeable graphs with maximum degree at most sqrt(n)/log(n) can be embedded into corresponding systems of super-regular pairs. This is optimal up to the logarithmic factor. We also present two applications. We prove that any large enough graph G with minimum degree at least ((r-1)/r+γ)n contains an F-factor of every a-arrangeable r-chromatic graph F with at most ξn vertices and maximum degree at most sqrt(n)/log(n), as long as ξ is sufficiently small compared to γ/(ar). This extends a result of Alon and Yuster [J. Combin. Theory Ser. B 66(2),269-282, 1996]. Moreover, we show that for constant p the random graph G(n,p) is universal for the class of a-arrangeable n-vertex graphs H of maximum degree at most ξn/log(n), as long as ξ is sufficiently small compared to p/a.

preprint2013arXiv

Tight Hamilton cycles in random hypergraphs

We give an algorithmic proof for the existence of tight Hamilton cycles in a random r-uniform hypergraph with edge probability p=n^{-1+eps} for every eps>0. This partly answers a question of Dudek and Frieze [Random Structures Algorithms], who used a second moment method to show that tight Hamilton cycles exist even for p=omega(n)/n (r>2) where omega(n) tends to infinity arbitrary slowly, and for p=(e+o(1))/n (r>3). The method we develop for proving our result applies to related problems as well.

preprint2012arXiv

Limits of permutation sequences

A permutation sequence is said to be convergent if the density of occurrences of every fixed permutation in the elements of the sequence converges. We prove that such a convergent sequence has a natural limit object, namely a Lebesgue measurable function $Z:[0,1]^2 \to [0,1]$ with the additional properties that, for every fixed $x \in [0,1]$ , the restriction $Z(x,\cdot)$ is a cumulative distribution function and, for every $y \in [0,1]$ , the restriction $Z(\cdot,y)$ satisfies a "mass" condition. This limit process is well-behaved: every function in the class of limit objects is a limit of some permutation sequence, and two of these functions are limits of the same sequence if and only if they are equal almost everywhere. An ingredient in the proofs is a new model of random permutations, which generalizes previous models and might be interesting for its own sake.

preprint2011arXiv

Hypergraphs with many Kneser colorings (Extended Version)

For fixed positive integers $r, k$ and $\ell$ with $1 \leq \ell < r$ and an $r$ -uniform hypergraph $H$ , let $κ(H, k,\ell)$ denote the number of $k$ -colorings of the set of hyperedges of $H$ for which any two hyperedges in the same color class intersect in at least $\ell$ elements. Consider the function $\KC(n,r,k,\ell)=\max_{H\in{\mathcal H}_{n}} κ(H, k,\ell) $, where the maximum runs over the family ${\mathcal H}_n$ of all $r$ -uniform hypergraphs on $n$ vertices. In this paper, we determine the asymptotic behavior of the function $\KC(n,r,k,\ell)$ for every fixed $r$ , $k$ and $\ell$ and describe the extremal hypergraphs. This variant of a problem of Erdős and Rothschild, who considered edge colorings of graphs without a monochromatic triangle, is related to the Erdős--Ko--Rado Theorem on intersecting systems of sets [Intersection Theorems for Systems of Finite Sets, Quarterly Journal of Mathematics, Oxford Series, Series 2, {\bf 12} (1961), 313--320].

preprint2011arXiv

Limits of permutation sequences through permutation regularity

A permutation sequence $(σ_n)_{n \in \mathbb{N}}$ is said to be convergent if, for every fixed permutation $τ$ , the density of occurrences of $τ$ in the elements of the sequence converges. We prove that such a convergent sequence has a natural limit object, namely a Lebesgue measurable function $Z:[0,1]^2 \to [0,1]$ with the additional properties that, for every fixed $x \in [0,1]$ , the restriction $Z(x,\cdot)$ is a cumulative distribution function and, for every $y \in [0,1]$ , the restriction $Z(\cdot,y)$ satisfies a "mass" condition. This limit process is well-behaved: every function in the class of limit objects is a limit of some permutation sequence, and two of these functions are limits of the same sequence if and only if they are equal almost everywhere. An important ingredient in the proofs is a new model of random permutations, which generalizes previous models and is interesting for its own sake.

preprint2011arXiv

The chromatic thresholds of graphs

The chromatic threshold delta_chi(H) of a graph H is the infimum of d>0 such that there exists C=C(H,d) for which every H-free graph G with minimum degree at least d|G| satisfies chi(G)<C. We prove that delta_chi(H) \in {(r-3)/(r-2), (2r-5)/(2r-3), (r-2)/(r-1)} for every graph H with chi(H)=r>2. We moreover characterise the graphs H with a given chromatic threshold, and thus determine delta_chi(H) for every graph H. This answers a question of Erdős and Simonovits [Discrete Math. 5 (1973), 323-334], and confirms a conjecture of Łuczak and Thomassé [preprint (2010), 18pp].

preprint2010arXiv

Properly coloured copies and rainbow copies of large graphs with small maximum degree

Let G be a graph on n vertices with maximum degree D. We use the Lovász local lemma to show the following two results about colourings c of the edges of the complete graph K_n. If for each vertex v of K_n the colouring c assigns each colour to at most (n-2)/22.4D^2 edges emanating from v, then there is a copy of G in K_n which is properly edge-coloured by c. This improves on a result of Alon, Jiang, Miller, and Pritikin [Random Struct. Algorithms 23(4), 409-433, 2003]. On the other hand, if c assigns each colour to at most n/51D^2 edges of K_n, then there is a copy of G in K_n such that each edge of G receives a different colour from c. This proves a conjecture of Frieze and Krivelevich [Electron. J. Comb. 15(1), R59, 2008]. Our proofs rely on a framework developed by Lu and Székely [Electron. J. Comb. 14(1), R63, 2007] for applying the local lemma to random injections. In order to improve the constants in our results we use a version of the local lemma due to Bissacot, Fernández, Procacci, and Scoppola [preprint, arXiv:0910.1824].

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

Yoshiharu Kohayakawa

Research overview

Is this your work?

24 publications

The anti-Ramsey threshold of complete graphs

The threshold for the constrained Ramsey property

On the query complexity of estimating the distance to hereditary graph properties

Covering $3$ -edge-coloured random graphs with monochromatic trees

The mod $k$ chromatic index of graphs is $O(k)$

Counting restricted orientations of random graphs

The size-Ramsey number of powers of bounded degree trees

Estimating parameters associated with monotone properties

Chromatic thresholds in dense random graphs

Chromatic thresholds in sparse random graphs

Densities in large permutations and parameter testing

Discrepancy and Eigenvalues of Cayley Graphs

The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton--Milner family

Upper bounds on probability thresholds for asymmetric Ramsey properties

Triangle-free subgraphs of random graphs

Powers of Hamilton cycles in pseudorandom graphs

Almost spanning subgraphs of random graphs after adversarial edge removal

An Extension of the Blow-up Lemma to arrangeable graphs

Tight Hamilton cycles in random hypergraphs

Limits of permutation sequences

Hypergraphs with many Kneser colorings (Extended Version)

Limits of permutation sequences through permutation regularity

The chromatic thresholds of graphs

Properly coloured copies and rainbow copies of large graphs with small maximum degree

See the researcher in context

Building this map preview

Yoshiharu Kohayakawa

Research overview

Is this your work?

24 publications

The anti-Ramsey threshold of complete graphs

The threshold for the constrained Ramsey property

On the query complexity of estimating the distance to hereditary graph properties

Covering 333-edge-coloured random graphs with monochromatic trees

The mod kkk chromatic index of graphs is O(k)O(k)O(k)

Counting restricted orientations of random graphs

The size-Ramsey number of powers of bounded degree trees

Estimating parameters associated with monotone properties

Chromatic thresholds in dense random graphs

Chromatic thresholds in sparse random graphs

Densities in large permutations and parameter testing

Discrepancy and Eigenvalues of Cayley Graphs

The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton--Milner family

Upper bounds on probability thresholds for asymmetric Ramsey properties

Triangle-free subgraphs of random graphs

Powers of Hamilton cycles in pseudorandom graphs

Almost spanning subgraphs of random graphs after adversarial edge removal

An Extension of the Blow-up Lemma to arrangeable graphs

Tight Hamilton cycles in random hypergraphs

Limits of permutation sequences

Hypergraphs with many Kneser colorings (Extended Version)

Limits of permutation sequences through permutation regularity

The chromatic thresholds of graphs

Properly coloured copies and rainbow copies of large graphs with small maximum degree

See the researcher in context

Building this map preview

Covering $3$ -edge-coloured random graphs with monochromatic trees

The mod $k$ chromatic index of graphs is $O(k)$