SpringerLink
Log in

Extremal Hypergraphs and Combinatorial Geometry

  • Conference paper
Proceedings of the International Congress of Mathematicians

Abstract

Here we overview some of the methods and results of extremal graph and hypergraph theory. A few geometric applications are also given.

Article Note

1991 Mathematics Subject Classification. Primary 05D05; secondary 05B25, 05C65, 52C10.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. L. Babai and P. Frankl,Note on set intersections, J. Combin. Theory Ser. A28(1980), 103–105.

    Article  MathSciNet  Google Scholar 

  2. L. Babai and P. Frankl,Linear algebra methods in combinatorics, (Preliminary version 2.), Dept. Comp. Sci., The University of Chicago, 1992.

    Google Scholar 

  3. I. Bárány, Z. Füredi, and L. Lovász,On the number of halving planes, Combinatorica10(1990), 175–183.

    Article  MathSciNet  Google Scholar 

  4. C. T. Benson,Minimal regular graphs of girth eight and twelve, Canad. J. Math.26(1966), 1091–1094.

    Article  MathSciNet  Google Scholar 

  5. B. Bollobás, Extremal Graph Theory, Academic Press, London, 1978.

    MATH  Google Scholar 

  6. A. Bondy and M. Simonovits,Cycles of even length in graphs, J. Combin. Theory Ser. B16(1974), 97–105.

    Article  MathSciNet  Google Scholar 

  7. K. Borsuk,Drei Sätze über die n-dimensionale euklidische Sphräre, Fund. Math.20(1933), 177–190.

    Article  Google Scholar 

  8. W. G. Brown,On graphs that do not contain a Thomsen graph, Canad. Math. Bull.9(1966), 281–289.

    Article  MathSciNet  Google Scholar 

  9. L. Caccetta and R. Häggkvist,On diameter critical graphs, Discrete Math.28(1979), 223–229.

    Article  MathSciNet  Google Scholar 

  10. D. K. Ray-Chaudhuri and R. M. Wilson,On t-designs, Osaka J. Math.12(1975), 737–744.

    MathSciNet  MATH  Google Scholar 

  11. F. R. K. Chung and P. Erdős,On unavoidable graphs, Combinatorica3(1983), 167–176;On unavoidable hypergraphs, J. Graph. Theory11(1987), 251–263.

    Article  MathSciNet  Google Scholar 

  12. F. R. K. Chung and P. Erdős,On unavoidable graphs, Combinatorica3(1983), 167–176;On unavoidable hypergraphs, J. Graph. Theory11(1987), 251–263.

    Article  MathSciNet  Google Scholar 

  13. F. R. K. Chung, R. L. Graham, and R. M. Wilson,Quasi-random graphs, Combinatorica9(1989), 345–362.

    Article  MathSciNet  Google Scholar 

  14. L. K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Wetzl,Combinatorial complexity bounds for arrangements of curves and spheres, Discrete Comput. Geom.,5(1990), 99–160.

    Article  MathSciNet  Google Scholar 

  15. Tamal K. Dey and H. Edelsbrunner,Counting triangle crossings and halving planes, manuscript Nov. 1992.

    MATH  Google Scholar 

  16. M. Deza, P. Erdős, and P. Frankl,Intersection properties of systems of finite sets, Proc. London Math. Soc. (3)36(1978), 368–384.

    MathSciNet  MATH  Google Scholar 

  17. R. Duke and V. Rödl,The Erdős-Ko-Rado theorem for small families, J. Combin. Theory Ser. A65(1994), 246–251.

    Article  MathSciNet  Google Scholar 

  18. H. Edelsbrunner and P. Hajnal,A lower bound on the number of unit distances between the vertices of a convex polygon, J. Combin. Theory Ser. A55(1990), 312–314.

    MathSciNet  MATH  Google Scholar 

  19. G. Elekes, Irregular pairs are necessary in Szemerédi’s regularity lemma, manuscript (1992).

    Google Scholar 

  20. P. Erdős,On sequences of integers no one of which divides the product of two others and some related problems, Izv. Naustno-Issl. Inst. Mat. i Meh. Tomsk2(1938), 74–82. (Zbl.20, p. 5)

    MATH  Google Scholar 

  21. P. Erdős,On sets of distances of n points, Amer. Math. Monthly53(1946), 248–250.

    Article  MathSciNet  Google Scholar 

  22. P. Erdős,On extremal problems of graphs and generalized graphs, Israel J. Math.2(1964), 183–190.

    Article  MathSciNet  Google Scholar 

  23. 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 Combin.2(1986), 113–121.

    Article  MathSciNet  Google Scholar 

  24. P. Erdős, Chao Ko, and R. Rado,An intersecting theorem for finite sets, Quart. J. Math. Oxford12(1961), 313–320.

    Article  Google Scholar 

  25. P. Erdős and L. Moser,Problem If Canad. Math. Bull.2(1959), 43.

    Google Scholar 

  26. P. Erdős, A. Renyi, and V. T. Sös,On a problem of graph theory, Studia Sci. Math. Hungar.1(1966), 215–235.

    MATH  Google Scholar 

  27. P. Erdős and M. Simonovits,A limit theorem in graph theory, Studia Sci. Math. Hungar.1(1966), 51–57.

    MathSciNet  MATH  Google Scholar 

  28. P. Erdős and M. Simonovits,Supersaturated graphs and hypergraphs, Combinatorica3(1983), 181–192.

    Article  MathSciNet  Google Scholar 

  29. P. Erdős and J. Spencer, Probabilistic Methods in Combinatorics, Akadémiai Kiadó, Budapest, 1974.

    Google Scholar 

  30. P. Erdős and A. H. Stone,On the structure of linear graphs, Bull. Amer. Math. Soc.52(1946), 1087–1091.

    Article  MathSciNet  Google Scholar 

  31. G. Fan,On diameter 2-critical graphs, Discrete Math.67(1987), 235–240.

    Article  MathSciNet  Google Scholar 

  32. D. C. Fisher,Lower bounds on the number of triangles in a graph, J. Graph Theory13(1989), 505–512.

    Article  MathSciNet  Google Scholar 

  33. P. Frankl,The Erdős-Ko-Rado theorem is true for n = ckt, Combinatorics, Proc Fifth Hungarian Colloq. Combin., Keszthely, Hungary, 1976, (A. Hajnal et al., eds.), Proc. Colloq. Math. Soc. J. Bolyai18(1978), 365–375, North-Holland, Amsterdam.

    Google Scholar 

  34. P. Frankl,All rationals occur as exponents, J. Combin. Theory Ser. A42(1986), 200–206.

    Article  MathSciNet  Google Scholar 

  35. P. Frankl and Z. Föredi,Exact solution of some Turán-type problems, J. Combin. Theory Ser. A45(1987), 226–262.

    Article  MathSciNet  Google Scholar 

  36. P. Frankl and Z. Föredi,Beyond the Erdős-Ko-Rado theorem, J. Combin. Theory Ser. A56(1991), 182–194.

    Article  MathSciNet  Google Scholar 

  37. P. Frankl, K. Ota, and N. Tokushige,Exponents of uniform L-systems, manuscript, 1994.

    MATH  Google Scholar 

  38. P. Frankl and V. Rödl,Hypergraphs do not jump, Combinatorica4(1984), 149–159.

    Article  MathSciNet  Google Scholar 

  39. P. Frankl and V. Rödl,Forbidden intersections, Trans. Amer. Math. Soc.300(1987), 259–286.

    Article  MathSciNet  Google Scholar 

  40. P. Frankl and R. M. Wilson,Intersection theorems with geometric consequences, Combinatorica1(1981), 357–368.

    Article  MathSciNet  Google Scholar 

  41. Z. Föredi,The maximum number of unit distances in a convex n-gon, J. Combin. Theory Ser. A55(1990), 316–320.

    Article  MathSciNet  Google Scholar 

  42. Z. Föredi,Turán type problems, in Surveys in Combinatorics, Proc. of the 13th British Combinatorial Conference, (ed. A. D. Keedwell), Cambridge Univ. Press, London Math. Soc. Lecture Note Series166(1991), 253–300.

    Google Scholar 

  43. Z. Föredi,The maximum number of edges in a minimal graph of diameter 2, J. Graph Theory16(1992), 81–98.

    Article  MathSciNet  Google Scholar 

  44. Z. Föredi,New asymptotics for bipartite Turán numbers, J. Combin. Theory Ser. A, to appear.

    Google Scholar 

  45. Z. Föredi,An upper bound on Zarankiewicz’ problem, Comb. Prob. and Comput., to appear.

    Google Scholar 

  46. H. Hadwiger,Überdeckungssatze für den Euklidischen Raum, Portugal. Math.4(1944), 140–144.

    MATH  Google Scholar 

  47. C. Hylten-Cavallius,On a combinatorial problem, Colloq. Math.6(1958), 59–65.

    Article  MathSciNet  Google Scholar 

  48. W. Imrich,Explicit construction of graphs without small cycles, Combinatorica4(1984), 53–59.

    Article  MathSciNet  Google Scholar 

  49. J. Kahn and G. Kalai, A counterexample to Borsuk’s conjecture, Bull. Amer. Math. Soc. 29 (1993), 60–63.

    Article  MathSciNet  Google Scholar 

  50. Gy. Katona,Intersection theorems for systems of finite sets, Acta Math. Hungar.15(1964), 329–337.

    Article  MathSciNet  Google Scholar 

  51. T. Kővári, V. T. Sös, and P. Turán,On a problem of K. Zarankiewicz, Colloq. Math.3(1954), 50–57.

    Article  MathSciNet  Google Scholar 

  52. D. C. Larman,A note on the realization of distances within sets in Euclidean space, Comment. Math. Helv.53(1978), 529–535.

    Article  MathSciNet  Google Scholar 

  53. D. Larman and C. Rogers,The realization of distances within sets in Euclidean space, Mathematika19(1972), 1–24.

    Article  MathSciNet  Google Scholar 

  54. F. Lazebnik, V. A. Ustimenko, and A. J. Woldar,A new series of dense graphs of high girth, Bull. Amer. Math. Soc.,32(1995), 73–79.

    Article  MathSciNet  Google Scholar 

  55. L. Lovász,Kneser’s conjecture, chromatic number and homotopy, J. Combin. Theory Ser. A 25 (1978), 319–324.

    Article  MathSciNet  Google Scholar 

  56. L. Lovász and M. Simonovits,On the number of complete subgraphs of a graph II, inStudies in Pure Math., Birkhäuser Verlag, Basel, (1983), 459–495.

    Chapter  Google Scholar 

  57. A. Lubotzky, R. Phillips, and P. Sarnak,Ramanujan graphs, Combinatorica8(1988), 261–277.

    Article  MathSciNet  Google Scholar 

  58. W. Mantel, Problem 28, Wiskundige Opgaven10(1907), 60–61.

    Google Scholar 

  59. G. A. Margulis,Explicit construction of graphs without short cycles and low density codes, Combinatorica2(1982), 71–78.

    Article  MathSciNet  Google Scholar 

  60. M. Mörs,A new result on the problem of Zarankiewicz, J. Combin. Theory Ser. A31(1981), 126–130.

    Article  MathSciNet  Google Scholar 

  61. J. Pach and P. K. Agarwal, Combinatorial Geometry, Wiley, New York, 1995.

    Book  Google Scholar 

  62. J. Pach, W. Steiger, and E. Szemerédi,An upper bound on the number of planar k-sets, Discrete Comput. Geom.7(1992), 109–123.

    Article  MathSciNet  Google Scholar 

  63. V. Rödl, personal communication

    Google Scholar 

  64. I. Z. Ruzsa and E. Szemerédi,Triple systems with no six points carrying three triangles, Combinatorics (Keszthely, 1976), Proc. Colloq. Math. Soc. J. Bolyai18, vol.II., 939–945, North-Holland, Amsterdam and New York, 1978.

    Google Scholar 

  65. M. Sharir,Almost linear upper bounds on the length of generalized Davenport- Schinzel sequences, Combinatorica7(1987), 131–143.

    Article  MathSciNet  Google Scholar 

  66. A. F. Sidorenko,On the maximal number of edges in a uniform hypergraph that does not contain prohibited subgraphs, Math. Notes41(1987), 247–259.

    Article  Google Scholar 

  67. M. Simonovits,Extremal graph theory, in Selected Topics in Graph Theory 2, (eds. L. W. Beineke and R. J. Wilson), Academic Press, New York, 1983, 161–200.

    Google Scholar 

  68. M. Simonovits,Extremal graph problems, degenerate extremal problems, and supersaturated graphs, Progress in Graph Theory (Waterloo, Ont. 1982), 419–437, Academic Press, Toronto, Ont., 1984.

    Google Scholar 

  69. V. T. Sös and M. Simonovits,Szemerédi’s partition and quasi-randomness, Random Structures and Algorithms2(1991), 1–10.

    MathSciNet  MATH  Google Scholar 

  70. J. Spencer, E. Szemeredi, and W. T. Trotter,Unit distances in the Euclidean plane, Graph Theory and Combinatorics, (ed. B. Bollobas), Academic Press, London, 1984, pp. 293–303.

    Google Scholar 

  71. E. Szemerédi,Regular partitions of graphs, Problèmes Combinatoires et Theorie des Graphes, Proc. Colloq. Int. CNRS 260, (1978), 399–401, Paris.

    Google Scholar 

  72. A. Thomason,Pseudo random graphs, Proceedings on Random Graphs, Poznan, 1985, (M. KaroŃsky, ed.), Ann. Discrete Math.33(1987), 307–331.

    Google Scholar 

  73. P. Turán,On an extremal problem in graph theory, Mat. Fiz. Lapok48(1941), 436–452 (in Hungarian). (Also see Colloq. Math.3(1954), 19–30.)

    MathSciNet  Google Scholar 

  74. P. Turán,On an extremal problem in graph theory, Mat. Fiz. Lapok48(1941), 436–452 (in Hungarian). (Also see Colloq. Math.3(1954), 19–30.)

    Article  Google Scholar 

  75. H. Tverberg,A generalization of Radon’s theorem, J. London Math. Soc.41(1966), 123–128.

    Article  MathSciNet  Google Scholar 

  76. R. Wenger,Extremal graphs with no C4’s, C6’s or C10’s, J. Combin. Theory Ser. B52(1991), 113–116.

    Article  MathSciNet  Google Scholar 

  77. R. M. Wilson,The exact bound in the Erdős-Ko-Rado theorem, Combinatorica4(1984), 247–257.

    Article  MathSciNet  Google Scholar 

  78. K. Zarankiewicz,Problem of P101, Colloq. Math.2(1951), 301.

    Google Scholar 

  79. Živaljević and Vrecica,The colored Tverberg’s problem and complexes of injective functions, J. Combin. Theory Ser. A61(1992), 309–318.

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Illinois at Urbana-Champaign, Urbana, IL, 61801, USA

    Zoltán Füredi

  2. Math. Inst. Hungarian Academy of Sciences, 1364 Budapest, POB 127, Hungary

    Zoltán Füredi

Authors
  1. Zoltán Füredi
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Département de Mathématiques, EPFL, 1015, Laussane, Switzerland

    S. D. Chatterji

Rights and permissions

Reprints and permissions

Copyright information

© 1995 Birkhäser Verlag, Basel, Switzerland

About this paper

Cite this paper

Füredi, Z. (1995). Extremal Hypergraphs and Combinatorial Geometry. In: Chatterji, S.D. (eds) Proceedings of the International Congress of Mathematicians. Birkhäuser, Basel. https://doi.org/10.1007/978-3-0348-9078-6_129

Download citation

  • DOI: https://doi.org/10.1007/978-3-0348-9078-6_129

  • Publisher Name: Birkhäuser, Basel

  • Print ISBN: 978-3-0348-9897-3

  • Online ISBN: 978-3-0348-9078-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation