Yoshiharu Kohayakawa - Publications
Profiles
Some manuscripts on-line
- Some other manuscripts
- (with C. G. Moreira), Tópicos em Combinatória Contemporânea,
Publicações Matemáticas, IMPA, 2010, xiii + 137pp
[pdf]
- (with S. J. Lee, C. G. Moreira, and V. Rödl), On strong Sidon
sets of integers, J. Combin. Theory Ser. A, 28pp [pdf]
- (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]
- (with T. Retter and V. Rödl) The size-Ramsey number of short
subdivisions of bounded degree graphs, 42pp
[pdf]
- (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]
- (with B. Bollobás, V. Rödl, M. Schacht, and A. Taraz) Essentially
infinite colourings of hypergraphs, 28pp [pdf]
- (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]
- (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]
- (with S. Gerke, V. Rödl, and A. Steger) Small subsets inherit sparse
$\epsilon$-regularity, Journal of Combinatorial Theory, Series B,
23pp [pdf]
- (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]
- (with M. Ferrara and V. Rödl) Distance graphs on the integers,
25pp [pdf | ps.gz | dvi.gz | tex.gz]
- (with F.K. Miyazawa, P. Raghavan, and Y. Wakabayashi) Multidimensional
cube packing, 23 pp [pdf | ps.gz | dvi.gz | tex.gz]
- (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]
- (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]
- (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]
- (with V. Rödl and M. Schacht) The Turán theorem for random graphs,
Combinatorics, Probability, and Computing, 31pp [pdf | ps.gz | dvi.gz]
- (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]
- (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]
- (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]
- (with Carlos Gustavo T. de A. Moreira) Bounds for optimal coverings,
Discrete Applied Mathematics, to appear, 16pp [pdf | ps.gz | dvi.gz | tex.gz]
- (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]
- (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]
- (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]
- (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]
- (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]
- (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]
- (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]
- (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]
- (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]
- 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].
- (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]
- (with B. Kreuter) Threshold functions for asymmetric Ramsey properties
involving cycles, Random Structures Algorithms 11 (1997), no. 3,
245-276 [pdf]
- (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]
- (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]
- (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]
- (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]
- (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]
- (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]
- (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]
- (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]
- (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]
- (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
I use the following BibTeX file, which is not really well organized, but it
helps if you get the original LaTeX files above.
Information about BibTeX:
Back to the index page.
Y. Kohayakawa
<yoshi@ime.usp.br>
Last modified: Sun 25 Aug 2024 4:17:27pm UTC -03