Ver registro no DEDALUS
Exportar registro bibliográfico

Metrics


Metrics:

Szemerédis regularity lemma for sparse graphs (1997)

  • Authors:
  • USP affiliated authors: KOHAYAKAWA, YOSHIHARU - IME
  • USP Schools: IME
  • DOI: https://doi.org/10.1007/978-3-642-60539-0_16
  • Subjects: TEORIA DOS GRAFOS
  • Keywords: Random Graph; Arithmetic Progression; Sparse Graph; London Mathematical Society Lecture Note; Regularity Lemma
  • Agências de fomento:
  • Language: Inglês
  • Imprenta:
  • Source:
  • Conference titles: Conference on Foundations of Computational Mathematics
  • Acesso online ao documento

    Online accessDOI or search this record in
    Informações sobre o DOI: https://doi.org/10.1007/978-3-642-60539-0_16 (Fonte: oaDOI API)
    • Este periódico é de assinatura
    • Este artigo NÃO é de acesso aberto
    • Cor do Acesso Aberto: closed

    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      KOHAYAKAWA, Yoshiharu. Szemerédis regularity lemma for sparse graphs. Anais.. Rio de Janeiro: IMPA, 1997.Disponível em: DOI: https://doi.org/10.1007/978-3-642-60539-0_16.
    • APA

      Kohayakawa, Y. (1997). Szemerédis regularity lemma for sparse graphs. In Selected papers. Rio de Janeiro: IMPA. doi:https://doi.org/10.1007/978-3-642-60539-0_16
    • NLM

      Kohayakawa Y. Szemerédis regularity lemma for sparse graphs [Internet]. Selected papers. 1997 ;Available from: https://doi.org/10.1007/978-3-642-60539-0_16
    • Vancouver

      Kohayakawa Y. Szemerédis regularity lemma for sparse graphs [Internet]. Selected papers. 1997 ;Available from: https://doi.org/10.1007/978-3-642-60539-0_16

    Referências citadas na obra
    . N. Alon, R.A. Duke, H. Lefmann, V. Rödl, and R. Yuster. The algorithmic aspects of the regularity lemma.Journal of Algorithms, 16 (1): 80–109, 1994.
    . B. Bollobás.Extremal Graph Theory. Academic Press, London, 1978.
    . B. Bollobás.Random Graphs. Academic Press, London, 1985.
    . F.R.K. Chung. Regularity lemmas for hypergraphs and quasi-randomness.Random Structures and Algorithms, 2 (l): 241–252, 1991.
    . F.R.K. Chung and R.L. Graham. Quasi-random set systems.Journal of the American Mathematical Society, 4 (1): 151–196, 1991.
    . F.R.K. Chung and R.L. Graham. Quasi-random subsets of ℤn.Journal of Combinatorial Theory, Series A, 61 (l): 64–86, 1992.
    . F.R.K. Chung, R.L. Graham, and R.M. Wilson. Quasi-random graphs.Combinatorica, 9 (4): 345–362, 1989.
    . R.A. Duke, H. Lefmann, and V. Rödl. A fast approximation algorithm for computing the frequencies of subgraphs in a given graph.SIAM Journal on Computing, 24 (3): 598–620, 1995.
    . P. Erdös, P. Frankl, and V. Rödl. The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent.Graphs and Combinatorics, 2 (2): 113–121, 1986.
    . P. Erdös and P. Turan. On some sequences of integers.Journal of the London Mathematical Society, 11 (2): 261–264, 1936.
    . P. Frankl and V. Rödl. Large triangle-free subgraphs in graphs without K4.Graphs and Combinatorics, 2 (2): 135–144, 1986.
    . P. Frankl and V. Rödl. The uniformity lemma for hypergraphs.Graphs and Combinatorics, 8 (4): 309–312, 1992.
    . P. Frankl, V. Rödl, and R.M. Wilson. The number of submatrices of a given type in a Hadamard matrix and related results.Journal of Combinatorial Theory, Series B, 44 (3): 317–328, 1988.
    . A. Frieze and R. Kannan. The regularity lemma and approximation schemes for dense problems. InProc. 37th Ann. IEEE Symp. on Foundations of Computer Science. IEEE, October 1996.
    . Z. Füredi. Random Ramsey graphs for the four-cycle.Discrete Mathematics, 126: 407–410, 1994.
    . R.L. Graham and J. Nešetřil. Large minimal sets which force long arithmetic progressions.Journal of Combinatorial Theory, Series A, 42 (2): 270–276, 1986.
    . R.L. Graham and V. Rödl. Numbers in Ramsey theory. In C. Whitehead, editor,Surveys in Combinatorics 1987, volume 123 ofLondon Mathematical Society Lecture Note Series, pages 112–153. Cambridge University Press, Cambridge-New York, 1987.
    . R.L. Graham and J. Spencer. A constructive solution to a tournament problem.Canadian Mathematics Bulletin, 14: 45–48, 1971.
    . P.E. Haxell and Y. Kohayakawa. On an anti-Ramsey property of Ramanujan graphs.Random Structures and Algorithms, 6 (4): 417–431, 1995.
    . P.E. Haxell, Y. Kohayakawa, and T. Luczak. The induced size-Ramsey number of cycles.Combinatorics, Probability, and Computing, 4 (3): 217–239, 1995.
    . P.E. Haxell, Y. Kohayakawa, and T. Luczak. Turán’s extremal problem in random graphs: forbidding even cycles.Journal of Combinatorial Theory, Series B, 64: 273–287, 1995.
    . P.E. Haxell, Y. Kohayakawa, and T. Luczak. Turán’s extremal problem in random graphs: forbidding odd cycles.Combinatorica, 16 (1): 107–122, 1996.
    . Y. Kohayakawa. The regularity lemma of Szemeredi for sparse graphs, manuscript, August 1993, 10 pp.
    . Y. Kohayakawa and B. Kreuter. Threshold functions for asymmetric Ramsey properties involving cycles.Random Structures and Algorithms. Submitted, 1996, 34 pp.
    . Y. Kohayakawa, B. Kreuter, and A. Steger. An extremal problem for random graphs and the number of graphs with large even-girth.Combinatorica. Submitted, 1995, 18 pp.
    . Y. Kohayakawa, T. Luczak, and V. Rödl. On K4-free subgraphs of random graphs.Combinatorica. Submitted, 1995, 35 pp.
    . Y. Kohayakawa, T. Luczak, and V. Rödl. Arithmetic progressions of length three in subsets of a random set.Acta Arithmetica, LXXV(2): 133–163, 1996.
    . Y. Kohayakawa and V. Rödl. Checking pseudorandomness of graphs fast (tentative title). In preparation, 1996.
    . J. Komlós and M. Simonovits. Szemeredi’s regularity lemma and its applications in graph theory. In D. Miklós, V.T. Sós, and T. Szönyi, editors,Combinatorics— Paul Erdös is eighty, vol. 2, Bolyai Society Mathematical Studies, pages 295–352. János Bolyai Mathematical Society, Budapest, 1996.
    . A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs.Combinatorica, 8: 261–277, 1988.
    . J. Nešetřil and V. Rödl. Partite construction and Ramseyan theorems for sets, numbers and spaces.Commentationes Mathematicae Universitatis Carolinae, 28 (3): 569–580, 1987.
    . H.-J. Prömel and B. Voigt. A sparse Graham-Rothschild theorem.Transactions of the American Mathematical Society, 309 (1): 113–137, 1988.
    . V. Rödl. On universality of graphs with uniformly distributed edges.Discrete Mathematics, 59 (1–2): 125–134, 1986.
    . V. Rödl. On Ramsey families of sets.Graphs and Combinatorics, 16 (2): 187–195, 1990.
    . V. Rödl and A. Ruciński. Lower bounds on probability thresholds for Ramsey properties. In D. Miklós, V.T. Sós, and T. Szönyi, editors,Combinatorics—Paul Erdös is eighty, vol. 1, Bolyai Society Mathematical Studies, pages 317–346. János Bolyai Mathematical Society, Budapest, 1993.
    . V. Rödl and A. Ruciński. Threshold functions for Ramsey properties.Journal of the American Mathematical Society, 8 (4): 917–942, 1995.
    . K.F. Roth. On certain sets of integers.Journal of the London Mathematical Society, 28: 104–109, 1953.
    . J. Spencer. Restricted Ramsey configurations.Journal of Combinatorial Theory, Series A, 19 (3): 278–286, 1975.
    . E. Szemeredi. On sets of integer sets containing nokelements in arithmetic progression.Acta Arithmetica, 27: 111–116, 1975.
    E. Szemeredi. Regular partitions of graphs. InProblümes Combinatoires et Théorie des Graphes, pages 399–401, Orsay, 1976. Colloques Internationaux CNRS n. 260.
    A.G. Thomason. Pseudorandom graphs. InRandom graphs ’85 (Poznan,1985), volume 144 ofNorth-Holland Math. Stud., pages 307–331. North-Holland, Amsterdam-New York, 1987.
    . A.G. Thomason. Random graphs, strongly regular graphs pseudorandom graphs. In C. Whitehead, editor,Surveys in Combinatorics 1987, volume 123 ofLondon Mathematical Society Lecture Note Series, pages 173–195. Cambridge University Press, Cambridge-New York, 1987.