# Yoshiharu Kohayakawa - Publications

### Some manuscripts on-line

1. (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]
2. (with B. Bollobás, V. Rödl, M. Schacht, and A. Taraz) Essentially infinite colourings of hypergraphs. 28pp [pdf]
3. (with N. Alon, C. Mauduit, C.G. Moreira, and V. Rödl) Measures of pseudorandomness for finite sequences: typical values, submitted, 42pp [pdf | ps.bz2 | dvi.bz2 | tex.bz2]
4. (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, to appear, 30pp [pdf]
5. (with S. Gerke, V. Rödl, and A. Steger) Small subsets inherit sparse $\epsilon$-regularity, Journal of Combinatorial Theory, Series B, to appear, 23pp [pdf]
6. (with N. Alon, C. Mauduit, C.G. Moreira, and V. Rödl) Measures of pseudorandomness for finite sequences: minimal values, submitted, 30pp [pdf | ps.gz | dvi.gz | tex.gz]
7. (with M. Ferrara and V. Rödl) Distance graphs on the integers, submitted, 25pp [pdf | ps.gz | dvi.gz | tex.gz]
8. (with V. Rödl and M. Schacht) Discrepancy and eigenvalues of Cayley graphs, manuscript, 24pp [pdf | ps.gz]
9. (with F.K. Miyazawa, P. Raghavan, and Y. Wakabayashi) Multidimensional cube packing, submitted, 2002, 23 pp [pdf | ps.gz | dvi.gz | tex.gz]
10. (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]
11. (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]
12. (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]
13. (with V. Rödl and M. Schacht) The Turán theorem for random graphs, Combinatorics, Probability, and Computing, to appear, 31pp [pdf | ps.gz | dvi.gz]
14. (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]
15. (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]
16. (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]
17. (with Carlos Gustavo T. de A. Moreira) Bounds for optimal coverings, Discrete Applied Mathematics, to appear, 16pp [pdf | ps.gz | dvi.gz | tex.gz]
18. (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]
19. (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]
20. (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]
21. (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]
22. (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]
23. (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]
24. (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]
25. (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]
26. (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]
27. 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].
28. (with T. Luczak 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]
29. (with B. Kreuter) Threshold functions for asymmetric Ramsey properties involving cycles, Random Structures Algorithms 11 (1997), no. 3, 245-276 [pdf]
30. (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]
31. (with T. Luczak 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]
32. (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]
33. (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]
34. (with B. Bollobás and T. Luczak) Connectivity properties of random subgraphs of the cube, Random Structures and Algorithms 6 (1995), no. 2-3, 221-230 [pdf | tex.bz2]
35. (with B. Bollobás and T. Luczak) On the diameter and radius of random subgraphs of the cube, Random Structures and Algorithms 5 (1994), no. 5, 627-648 [pdf | tex.bz2]
36. (with B. Bollobás and T. Luczak) The evolution of random subgraphs of the cube, Random Structures and Algorithms 3 (1992), no. 1, 55-90 [pdf]

#### My BibTeX file

I use the following BibTeX file, which is not really well organized, but it helps if you get the original LaTeX files above.