Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Paul Erdős: Life and Work Read chapter Read first chapter

2013 | OriginalPaper | Chapter

Unexpected Applications of Polynomials in Combinatorics

Author : Larry Guth

Published in: The Mathematics of Paul Erdős I

Publisher: Springer New York

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In the last 6 years, several combinatorics problems have been solved in an unexpected way using high degree polynomials. The most well-known of these problems is the distinct distance problem in the plane.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Distances in Convex Polygons
next chapter The Number of Homothetic Subsets
Literature
BW86.
E. Berlekamp and L. Welch, Error correction of algebraic block codes. US Patent Number 4,633,470. 1986.
CEGPSSS92.
B. Chazelle, H. Edelsbrunner, L. Guibas, R. Pollack, R. Seidel, M. Sharir, and J. Snoeyink, Counting and cutting cycles of lines and rods in space, Computational Geometry: Theory and Applications, 1(6) 305–323 (1992).MathSciNetMATHCrossRef
CEGSW90.
K.L. Clarkson, H. Edelsbrunner, L. Guibas, M Sharir, and E. Welzl, Combinatorial Complexity bounds for arrangements of curves and spheres, Discrete Comput. Geom. (1990) 5, 99–160.
Dvir09.
Erdős46.
Erdős.
P. Erdős, Some of my favorite problems and results, in The Mathematics of Paul Erdős, Springer, 1996.
EKS11.
Gy. Elekes, H. Kaplan, and M. Sharir, On lines, joints, and incidences in three dimensions, Journal of Combinatorial Theory, Series A (2011) 118, 962–977.
Elekes–Sharir10.
Gy. Elekes and M. Sharir, Incidences in three dimensions and distinct distances in the plane, Proceedings 26th ACM Symposium on Computational Geometry (2010) 413–422.
Federer69.
H. Federer, Geometric measure theory. Die Grundlehren der mathematischen Wissenschaften, Band 153 Springer-Verlag New York Inc., New York 1969.
Feldman–SharirS05.
S. Feldman and M. Sharir, An improved bound for joints in arrangements of lines in space, Discrete Comput. Geom. (2005) 33, 307–320.MathSciNetMATHCrossRef
Gromov03.
Guth–Katz10.
Guth–Katz11.
L. Guth and N. Katz, On the Erdős distinct distance problem in the plane, arXiv:1011.4105.
Guth09.
Minimax problems related to cup powers and Steenrod squares. Geom. Funct. Anal. 18 (2009), no. 6, 1917–1987.
KMS12.
H. Kaplan, J. Matous̆ek, and M. Sharir, Simple proofs of classical theorems in discrete geometry via the Guth–Katz polynomial partitioning technique. Discrete Comput. Geom. 48 (2012), no. 3, 499–517.
KSS10.
Laba08.
I. Laba, From harmonic analysis to arithmetic combinatorics. Bull. Amer. Math. Soc. (N.S.) 45 (2008), no. 1, 77–115.
Quilodrán10.
R. Quilodrán, The joints problem in R n, Siam J. Discrete Math, Vol. 23, 4, p. 2211–2213.
Schmidt74.
Schmidt, Wolfgang M. Applications of Thue’s method in various branches of number theory. Proceedings of the International Congress of Mathematicians (Vancouver, B.C., 1974), Vol. 1, pp. 177–185. Canad. Math. Congress, Montreal, Que., 1975.
Solymosi–Tao12.
SST.
J. Spencer, E. Szemerédi, and W. Trotter, Unit distances in the Euclidean plane. Graph theory and combinatorics (Cambridge, 1983), 293–303, Academic Press, London, 1984.
Sudan95.
M. Sudan, Efficient checking of polynomials and proofs and the hardness of approximation problems, ACM Distinguished Thesees, Springer 1995.MATHCrossRef
Székely97.
ST83.
Tao01.
T. Tao, From rotating needles to stability of waves: emerging connections between combinatorics, analysis, and PDE. Notices Amer. Math. Soc. 48 (2001), no. 3, 294–303.MathSciNetMATH
Toth03.
C. Toth, The Szemerédi-Trotter theorem in the complex plane. aXiv:math/0305283, 2003.
Trevisan04.
L. Trevisan, Some applications of coding theory in computational complexity. Complexity of computations and proofs, 347–424, Quad. Mat., 13, Dept. Math., Seconda Univ. Napoli, Caserta, 2004.
Wolff99.
T. Wolff. Recent work connected with the Kakeya problem. Prospects in mathematics (Princeton, NJ, 1996). pages 129–162, 1999.
Metadata
Title
Unexpected Applications of Polynomials in Combinatorics
Author
Larry Guth
Copyright Year
2013
Publisher
Springer New York
Book
The Mathematics of Paul Erdős I

Print ISBN: 978-1-4614-7257-5

Electronic ISBN: 978-1-4614-7258-2

Copyright Year: 2013

DOI
https://doi.org/10.1007/978-1-4614-7258-2_31

Premium Partner

    Image Credits