300 BCE
Euclid's Combinatorial Lemma
Euclid's Elements includes combinatorial results like the number of ways to choose k objects from n, laying early foundations for combinatorics. #combinatorics #mathematics
Chronological Storyline (44 Milestones)
850 CE
Al-Khalil's Combinatorial Analysis
Al-Khalil al-Farahidi's work on Arabic poetry includes systematic enumeration of possible word patterns, an early combinatorial method. #combinatorics #islamicgoldenage
By احمد محمود خضير - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=27778602
1202 CE
Fibonacci's Liber Abaci
Fibonacci introduces the Fibonacci sequence and combinatorial problems like rabbit breeding, influencing later combinatorial thinking. #combinatorics #mathematics
By Taty2007 - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=5809387
1666 CE
Leibniz's Dissertatio de Arte Combinatoria
Gottfried Wilhelm Leibniz publishes a dissertation on combinatorial art, aiming to create a universal language of reasoning. #combinatorics #philosophy
By Christoph Bernhard Francke - Herzog Anton Ulrich-Museum, online, Public domain, https://commons.wikimedia.org/w/index.php?curid=53159699
1736 CE
Euler Solves Königsberg Bridges Problem
Leonhard Euler solves the Seven Bridges of Königsberg problem, founding graph theory. #graphtheory #combinatorics
By Twotwos - Own work based on: Konigsberg bridges.png. This file was derived from: Image-Koenigsberg, Map by Merian-Erben 1652.jpg, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=175193733
1751 CE
Euler's Formula for Polyhedra
Euler discovers V - E + F = 2 for convex polyhedra, a foundational result in graph theory and topology. #graphtheory #topology
1801 CE
Gauss's Disquisitiones Arithmeticae
Gauss's work includes combinatorial topics like quadratic residues and permutations, influencing number theory and combinatorics. #combinatorics #numbertheory
By Unknown author, Public domain, https://commons.wikimedia.org/w/index.php?curid=641724
1812 CE
Catalan Numbers Discovered
Eugène Catalan studies the sequence now named after him, counting parenthesizations and lattice paths. #combinatorics
By WatchduckYou can name the author as "T. Piesk", "Tilman Piesk" or "Watchduck". - Own work, CC BY 3.0, https://commons.wikimedia.org/w/index.php?curid=17822654
1847 CE
Kirchhoff's Circuit Laws
Gustav Kirchhoff uses graph theory to analyze electrical circuits, introducing concepts like spanning trees. #graphtheory #physics
1852 CE
Four Color Conjecture Posed
Francis Guthrie conjectures that four colors suffice to color any map, sparking a century-long quest. #graphtheory #coloring
By Inductiveload - Based on a this raster image by chas zzz brown on en.wikipedia., CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=1680050
1857 CE
Cayley's Trees Enumeration
Arthur Cayley enumerates trees, founding enumerative combinatorics and chemical graph theory. #combinatorics #graphtheory
By Júlio Reis - Fully drawn by myself, after Cayley_graph_formula_2_4.gif by Rocchini, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=1699157
1872 CE
Sylvester Invents Graph Theory Terms
James Joseph Sylvester coins the term 'graph' in a paper on algebraic invariants. #graphtheory #terminology
By Unknown author - from:http://en.wikipedia.org/wiki/Image:Untitled04.jpg, Public domain, https://commons.wikimedia.org/w/index.php?curid=268041
1878 CE
Ramsey Theory Origins
Frank Plumpton Ramsey's work on combinatorial logic later leads to Ramsey theory, though his seminal paper appears in 1930. #combinatorics #ramsey
1889 CE
Heawood's Map Coloring Conjecture
Percy Heawood proves the five color theorem and poses the Heawood conjecture for map coloring on surfaces. #graphtheory #coloring
By Cmglee - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=110688489
1891 CE
Petersen Graph Discovered
Julius Petersen introduces the Petersen graph, a key counterexample in graph theory. #graphtheory
By Leshabirukov - Own work by uploader based on http://en.wikipedia.org/wiki/File:Heawood_Graph.svg, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=5788203
1913 CE
Burnside's Lemma
William Burnside's lemma counts orbits under group actions, fundamental in combinatorial enumeration. #combinatorics #grouptheory
1920 CE
Kuratowski's Planar Graph Theorem
Kazimierz Kuratowski characterizes planar graphs, forbidding K5 and K3,3 subdivisions. #graphtheory #planarity
By David Eppstein - Own work, CC0, https://commons.wikimedia.org/w/index.php?curid=23861616
1930 CE
Ramsey's Theorem Published
Frank Ramsey proves Ramsey's theorem, founding Ramsey theory: complete disorder is impossible. #combinatorics #ramsey
1935 CE
Whitney's Matroid Theory
Hassler Whitney introduces matroids, abstracting linear independence and graph theory. #combinatorics #graphtheory
1936 CE
Kőnig's Graph Theory Textbook
Dénes Kőnig publishes the first textbook on graph theory, 'Theorie der endlichen und unendlichen Graphen'. #graphtheory #textbook
By no conegut - BUDAPESTI MŰSZAKI ÉS GAZDASÁGTUDOMÁNYI EGYETEM MATEMATIKA INTÉZET: https://math.bme.hu/~hujter/konig1928.jpg, Public domain, https://commons.wikimedia.org/w/index.php?curid=90577639
1941 CE
Brooks' Theorem on Graph Coloring
R. Leonard Brooks proves Brooks' theorem, bounding chromatic number by maximum degree. #graphtheory #coloring
By Vectorisation: BethNaught. Original: Claudio Rocchini (User:Rocchini) - This file was derived from: Graph exact coloring.gif This W3C-unspecified vector image was created with Inkscape ., CC BY 2.5, https://commons.wikimedia.org/w/index.php?curid=42831705
1947 CE
Turan's Graph Theorem
Pál Turán proves Turán's theorem, maximizing edges in a graph without a complete subgraph. #graphtheory #extremal
1950 CE
Erdős–Szekeres Theorem
Paul Erdős and George Szekeres prove the Happy Ending problem, a Ramsey-type result in combinatorial geometry. #combinatorics #geometry
By David Eppstein - self-made. Originally uploaded as png to English Wikipedia; description page is/was here., Public domain, https://commons.wikimedia.org/w/index.php?curid=2503167
1954 CE
Dijkstra's Algorithm
Edsger Dijkstra invents Dijkstra's algorithm for shortest paths in graphs, fundamental in network theory. #graphtheory #algorithms
By Ibmua - Work by uploader., Public domain, https://commons.wikimedia.org/w/index.php?curid=6282617
1956 CE
Kruskal's Algorithm
Joseph Kruskal publishes Kruskal's algorithm for minimum spanning trees. #graphtheory #algorithms
By Shiyu Ji - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=54420893
1958 CE
Pólya Enumeration Theorem
George Pólya's enumeration theorem counts colorings under symmetry, a powerful combinatorial tool. #combinatorics #enumeration
1961 CE
Erdős–Rényi Random Graph Model
Paul Erdős and Alfréd Rényi introduce the random graph model, founding probabilistic combinatorics. #graphtheory #randomgraphs
By David Eppstein - Own work, CC0, https://commons.wikimedia.org/w/index.php?curid=115108260
1965 CE
Lovász Local Lemma
László Lovász proves the Lovász local lemma, a probabilistic method for avoiding bad events. #combinatorics #probability
1969 CE
Appel–Haken Four Color Theorem Proof
Kenneth Appel and Wolfgang Haken prove the Four Color Theorem using computer assistance, a landmark in graph theory. #graphtheory #coloring
1970 CE
Knuth's Art of Computer Programming Vol. 3
Donald Knuth's volume covers combinatorial algorithms, sorting, and searching, influencing computer science. #combinatorics #algorithms
By Addison-Wesley - Vectorized from https://www.amazon.com/Art-Computer-Programming-Fundamental-Algorithms/dp/0201896834 by VectorVoyager, Public domain, https://commons.wikimedia.org/w/index.php?curid=114103224
1973 CE
Szemerédi's Theorem
Endre Szemerédi proves that any set of integers with positive density contains arbitrarily long arithmetic progressions, a milestone in additive combinatorics. #combinatorics #additive
1976 CE
Robertson–Seymour Graph Minor Theorem
Neil Robertson and Paul Seymour begin their series proving the Graph Minor Theorem, a deep structural result. #graphtheory #minors
1983 CE
Graham–Rothschild Parameter Sets
Ronald Graham and Bruce Rothschild develop parameter sets in Ramsey theory, extending the field. #combinatorics #ramsey
1984 CE
Babai's Graph Isomorphism Algorithm
László Babai develops a quasipolynomial-time algorithm for graph isomorphism, a major breakthrough. #graphtheory #algorithms
By BagLuke - Own work, CC0, https://commons.wikimedia.org/w/index.php?curid=162719043
1990 CE
Wigderson's Coloring Algorithm
Avi Wigderson gives a polynomial-time algorithm for coloring 3-colorable graphs, advancing graph coloring. #graphtheory #coloring
By Unknown author, Public domain, https://commons.wikimedia.org/w/index.php?curid=1386753
1996 CE
Green–Tao Theorem
Ben Green and Terence Tao prove that primes contain arbitrarily long arithmetic progressions, a stunning combinatorial number theory result. #combinatorics #numbertheory
2002 CE
AKS Primality Test
Manindra Agrawal, Neeraj Kayal, and Nitin Saxena discover a deterministic polynomial-time primality test, using combinatorial number theory. #combinatorics #algorithms
2004 CE
Hales–Jewett Theorem
Alfred Hales and Robert Jewett prove a multidimensional Ramsey theorem, foundational in combinatorial game theory. #combinatorics #ramsey
2009 CE
Erdős–Ko–Rado Theorem Extensions
Various extensions of the Erdős–Ko–Rado theorem on intersecting families are proven, advancing extremal set theory. #combinatorics #extremal
By David Eppstein - Own work, CC0, https://commons.wikimedia.org/w/index.php?curid=37039431
2012 CE
Bourgain's Sum-Product Theorem
Jean Bourgain proves a sum-product theorem in finite fields, with applications in combinatorics and number theory. #combinatorics #additive
2015 CE
Hrushovski's Stable Group Theory
Ehud Hrushovski applies model theory to combinatorics, proving new results in additive combinatorics. #combinatorics #modeltheory
By Ivonne Vetter, Copyright is MFO - Mathematisches Forschungsinstitut Oberwolfach,https://opc.mfo.de/detail?photo_id=12309, CC BY-SA 2.0 de, https://commons.wikimedia.org/w/index.php?curid=12364746
2018 CE
Kahn–Kalai Conjecture Proved
The Kahn–Kalai conjecture on thresholds in random graphs is proved by Park and Pham, a breakthrough in probabilistic combinatorics. #combinatorics #randomgraphs
2020 CE
Resolution of the Erdős–Hajnal Conjecture
Maria Chudnovsky and colleagues prove the Erdős–Hajnal conjecture for certain graph classes, a major advance in graph theory. #graphtheory #ramsey
By BagLuke - Own work, CC0, https://commons.wikimedia.org/w/index.php?curid=177900956
2023 CE
Mathematical Proof of the Sensitivity Conjecture
Hao Huang proves the sensitivity conjecture using combinatorial methods, solving a long-standing problem in Boolean function analysis. #combinatorics #computerscience