Yoshiharu Kohayakawa - Publications

• List of publications (PDF file)

Profiles

• Mathematical Reviews profile
• Zentralblatt für Mathematik profile
• Scopus profile
• ACM Digital Library profile

Some manuscripts on-line

• Manuscripts on arXiv

• Some other manuscripts
   
  1. (with C. G. Moreira), Tópicos em Combinatória Contemporânea, Publicações Matemáticas, IMPA, 2010, xiii + 137pp [pdf]
  2. (with S. J. Lee, C. G. Moreira, and V. Rödl), On strong Sidon sets of integers, J. Combin. Theory Ser. A, 28pp [pdf]
  3. (with D. Dellamonica Jr, S. J. Lee, V. Rödl and W. Samotij), The number of $B_h$-sets of a given cardinality, Proc. London Math. Soc. (3), 41pp [pdf]
  4. (with T. Retter and V. Rödl) The size-Ramsey number of short subdivisions of bounded degree graphs, 42pp [pdf]
  5. (with D. Dellamonica Jr) An algorithmic Friedman--Pippenger theorem on tree embeddings and applications, Electron. J. Combin. 15 (2008), no. 1, Research Paper 127, 14pp [ElJC page]
  6. (with B. Bollobás, V. Rödl, M. Schacht, and A. Taraz) Essentially infinite colourings of hypergraphs, 28pp [pdf]
  7. (with N. Alon, C. Mauduit, C.G. Moreira, and V. Rödl) Measures of pseudorandomness for finite sequences: typical values, 42pp [pdf | ps.bz2 | dvi.bz2 | tex.bz2]
  8. (with V. Rödl, M. Schacht, P. Sissokho, and J. Skokan) Turán's theorem for pseudo-random graphs, Journal of Combinatorial Theory, Series A, 30pp [pdf]
  9. (with S. Gerke, V. Rödl, and A. Steger) Small subsets inherit sparse $\epsilon$-regularity, Journal of Combinatorial Theory, Series B, 23pp [pdf]
  10. (with N. Alon, C. Mauduit, C.G. Moreira, and V. Rödl) Measures of pseudorandomness for finite sequences: minimal values, 30pp [pdf | ps.gz | dvi.gz | tex.gz]
  11. (with M. Ferrara and V. Rödl) Distance graphs on the integers, 25pp [pdf | ps.gz | dvi.gz | tex.gz]
  12. (with F.K. Miyazawa, P. Raghavan, and Y. Wakabayashi) Multidimensional cube packing, 23 pp [pdf | ps.gz | dvi.gz | tex.gz]
  13. (with E. Friedgut, V. Rödl, A. Rucinski, and P. Tetali) Ramsey games against a one-armed bandit, 39pp [pdf | ps.gz | dvi.gz]. Revised version, Combinatorics, Probability, and Computing, to appear, 31 pp [pdf | ps.gz | dvi.gz | tex.gz]
  14. (with B. Kreuter) The width of random subsets of Boolean lattices, Journal of Combinatorial Theory, Series A, 100 (2002), no. 2, 376-386 [pdf | ps.gz | dvi.gz | tex.gz]
  15. (with V. Rödl and P.A. Sissokho) Embedding graphs with bounded degree in sparse pseudorandom graphs, Israel Journal of Mathematics, 139 (2004), 93-137 [pdf | ps.gz | dvi.gz]
  16. (with V. Rödl and M. Schacht) The Turán theorem for random graphs, Combinatorics, Probability, and Computing, 31pp [pdf | ps.gz | dvi.gz]
  17. (with B. Bollobás, J. Donadelli, and R.H. Schelp) Ramsey minimal graphs, J. of the Brazilian Computer Society 7 (2002), no. 3, 27--37 [pdf | ps.gz | dvi.gz | tex.gz]
  18. (with R. Carmo, J. Donadelli, and E. Laber) Searching in random partially ordered sets (extended abstract), LATIN 2002: Theoretical Informatics (Cancún, April 2002), Lecture Notes in Computer Science 2286, Springer, Berlin, 2002, pp. 278--292 [pdf | ps.gz | dvi.gz]. Full version, to appear in Theoretical Computer Science, 20pp [pdf | ps.gz | dvi.gz]
  19. (with B. Nagle and V. Rödl) Efficient testing of hypergraphs (extended abstract), ICALP 2002, 29th International Colloquium on Automata, Languages, and Programming (Málaga, Spain, July 2002), Lecture Notes in Computer Science 2380, Springer 2002, pp. 1017--1028 [dvi.gz | ps.gz]
  20. (with Carlos Gustavo T. de A. Moreira) Bounds for optimal coverings, Discrete Applied Mathematics, to appear, 16pp [pdf | ps.gz | dvi.gz | tex.gz]
  21. (with V. Rödl and L. Thoma) An optimal algorithm for checking regularity (extended abstract), The 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), San Francisco, CA, 6 to 8 January 2002, 10pp [ps.gz | dvi.gz]. Full version: An optimal algorithm for checking regularity, SIAM J. on Computing 32 (2003), no. 5, 1210-1235 [pdf | ps.gz | dvi.gz]
  22. (with V. Rödl) Regular pairs in sparse random graphs I, Random Structures and Algorithms 22 (2003), no. 4, 359-434 [pdf | ps.gz | dvi.gz | tex.gz]
  23. (with N. Alon, M. Capalbo, V. Rödl, A. Rucinski, and E. Szemerédi) Near-optimum universal graphs for graphs with bounded degrees (extended abstract), Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques (M. Goemans, K. Jansen, J.D.P. Rolim, and L. Trevisan, eds), Lecture Notes in Computer Science 2129, Springer-Verlag, 2001, pp. 170-180 [ps.gz | pdf]
  24. (with V. Rödl) Szemerédi's regularity lemma and quasi-randomness, Recent Advances in Algorithmic Combinatorics (B. Reed and C. Linhares-Sales, eds.), CMS Books Math./Ouvrages Math. SMC, vol. 11, Springer, New York, 2003, pp. 289-351 [pdf | ps.gz | dvi.gz | tex.gz]
  25. (with V. Rödl and J. Skokan) Hypergraphs, quasi-randomness, and conditions for regularity, J. of Combinatorial Theory A, 97 (2002), no. 2, 307-352 [ps.gz | dvi.gz]
  26. (with B. Nagle and V. Rödl) Hereditary properties of triple systems, Combinatorics, Probability, and Computing, 12 (2003), no. 2, 155-189 [dvi.gz | ps.gz]
  27. (with J. Donadelli) A density result for random sparse oriented graphs and its relation to a conjecture of Woodall, Electronic Journal of Combinatorics 9 (2002), no. 1, Research paper 45 [pdf | ps.gz | dvi.gz | tex.gz]
  28. (with N. Alon, M. Capalbo, V. Rödl, A. Rucinski, and E. Szemerédi) Universality and tolerance (extended abstract), Proceedings of the 41st IEEE Annual Symposium on Foundations of Computer Science (FOCS 2000), 2000, pp. 14-21 [ps.gz]
  29. (with V. Rödl) Algorithmic aspects of regularity, LATIN 2000: Theoretical Informatics (Punta del Este, 2000) (G. Gonnet, D. Panario, and A. Viola, eds.), Lecture Notes in Computer Science 1776, Springer, Berlin, 2000, pp. 1-17 [ps.gz | dvi.gz | tex.gz]
  30. Szemerédi's regularity lemma for sparse graphs, Foundations of Computational Mathematics (Berlin, Heidelberg) (F. Cucker and M. Shub, eds.), Springer-Verlag, January 1997, pp. 216-230 [pdf | ps.gz | dvi.gz | tex.gz]. The proof sketched in this manuscript is given in detail in The Regularity Lemma of Szemerédi for Sparse Graphs (unpublished manuscript, 1993, 10pp) [pdf | tex.bz2].
  31. (with T. Łuczak and V. Rödl) On $K^4$-free subgraphs of random graphs, Combinatorica 17 (1997), no. 2, 173-213 [ps.gz | pdf | dvi.gz | tex.gz]
  32. (with B. Kreuter) Threshold functions for asymmetric Ramsey properties involving cycles, Random Structures Algorithms 11 (1997), no. 3, 245-276 [pdf]
  33. (with P. Erdős and A. Gyárfás) The size of the largest bipartite subgraphs, Discrete Math. 177 (1997), no. 1-3, 267-271 [pdf]
  34. (with T. Łuczak and V. Rödl) Arithmetic progressions of length three in subsets of a random set, Acta Arith. 75 (1996), no. 2, 133-163 [ps.gz | pdf | dvi.gz | tex.gz]
  35. (with P.E. Haxell) On an anti-Ramsey property of Ramanujan graphs, Random Structures and Algorithms 6 (1995), no. 4, 417-431 [ps.gz | pdf | dvi.gz | tex.gz]
  36. (with P.E. Haxell and T. Łuczak) The induced size-Ramsey number of cycles, Combinatorics, Probability and Computing 4 (1995), no. 3, 217-239 [pdf]
  37. (with P.E. Haxell) The size-Ramsey number of trees, Israel Journal of Mathematics 89 (1995), no. 1-3, 261-274 [ps.gz | pdf | dvi.gz | tex.gz]
  38. (with B. Bollobás and T. Łuczak) Connectivity properties of random subgraphs of the cube, Random Structures and Algorithms 6 (1995), no. 2-3, 221-230 [pdf | tex.bz2]
  39. (with B. Bollobás and T. Łuczak) On the evolution of random Boolean functions, Extremal Problems for Finite Sets (Visegrád), P. Frankl, Z. Füredi, G. Katona, and D. Miklós, eds., Bolyai Society Mathematical Studies, vol. 3, Jáanos Bolyai Mathematical Society, 1994, pp. 137-156 [pdf]
  40. (with B. Bollobás and T. Łuczak) On the diameter and radius of random subgraphs of the cube, Random Structures and Algorithms 5 (1994), no. 5, 627-648 [pdf | tex.bz2]
  41. (with B. Bollobás and T. Łuczak) The evolution of random subgraphs of the cube, Random Structures and Algorithms 3 (1992), no. 1, 55-90 [pdf]
  42. (with B. Bollobás) The hitting time of Hamilton cycles in random bipartite graphs, in Graph theory, combinatorics, algorithms, and applications (San Francisco, CA, 1989), 26–41, SIAM, Philadelphia, PA, 1991 [pdf]

My BibTeX file

• refs.bib [outdated]

• The Collection of Computer Science Bibliographies
• A Survey of bibliographic tools, by Dana Jacobsen
• btOOL: A Programmer's Interface to BibTeX Files, by Greg Ward
• See also Nelson H.F. Beebe's home page

Last modified: Sun 2 Jul 2023 8:21:13pm UTC -03