Topics in Combinatorics
The aim of the course is to introduce students to Combinatorics, a fundamental mathematical discipline as well as an essential component of many mathematical areas. While in the past many of the basic combinatorial results were obtained by ingenuity and detailed reasoning, the modern theory has grown out of this early stage and often relies on deep, well-developed tools. The course will cover over a dozen virtually independent topics, chosen to illustrate several such techniques. This is an ultimate fun course, showcasing the gems of modern Combinatorics.
讲师
本杰明·苏达科夫
日期
2026年09月17日 至 12月17日
位置
| Weekday | Time | Venue | Online | ID | Password |
|---|---|---|---|---|---|
| 周四 | 15:30 - 17:20 | Online | ZOOM 14 | 712 322 9571 | BIMSA |
课程大纲
Examples illustrating combinatorics and its connections with other areas of mathematics. Basic graph theory and Eulerian graphs. The pigeonhole principle: a few quick examples, Dirichlet’s lemma, and the Erdős–Szekeres bound on the longest increasing or decreasing subsequence. Double counting.
Sperner’s lemma and Brouwer’s fixed-point theorem. Ramsey’s theorem for graphs and set systems. Finding a convex polygon among points in the plane. Upper bounds for (k)-colour Ramsey numbers of triangles.
Lower bounds for Ramsey numbers and the power of counting. Ramsey theory for integers: the theorems of Schur and van der Waerden. Density of subsets of integers containing no cubes. Turán’s theorem: statement and first application.
Turán’s theorem: two proofs and its application to the number of edges in permutation graphs. Turán numbers for general graphs and the Erdős–Stone theorem. Maximum number of edges in a graph containing no (4)-cycle.
Maximum number of edges in a graph containing no fixed complete bipartite graph (K_{t,s}), and applications to additive number theory. Probabilistic methods: elementary tools; tournaments with the Schütte property, in which every (k) players are beaten by somebody; (2)-colourability of uniform hypergraphs; linearity of expectation and its application to sum-free subsets.
Probabilistic methods: graphs with large girth and large chromatic number. Three famous results on finite sets: Sperner’s theorem and its application to the Littlewood–Offord problem, and Bollobás’s theorem on set pairs.
Three famous results on finite sets: the Erdős–Ko–Rado theorem. Kneser graphs and the application of the Borsuk–Ulam theorem to the chromatic number of Kneser graphs.
Algebraic methods: the Oddtown and Eventown problems, Fisher’s inequality, the number of lines determined by a non-collinear set of points, and two-distance sets in (\mathbb{R}^n).
Algebraic methods: bounds on the number of sets with restricted pairwise intersections, modular versions of the restricted-intersection problem, and a counterexample to Borsuk’s conjecture.
Spectral techniques: the adjacency matrix of a graph and its eigenvalues; eigenvalues of cliques, complete bipartite graphs, graph complements, and line graphs. Applications: decompositions of (K_{10}) into Petersen graphs and the Friendship Theorem.
Spectral techniques: the variational characterization of eigenvalues; bounds on Max-Cut, the chromatic number, and the independence number; graph expansion using eigenvalues.
Sperner’s lemma and Brouwer’s fixed-point theorem. Ramsey’s theorem for graphs and set systems. Finding a convex polygon among points in the plane. Upper bounds for (k)-colour Ramsey numbers of triangles.
Lower bounds for Ramsey numbers and the power of counting. Ramsey theory for integers: the theorems of Schur and van der Waerden. Density of subsets of integers containing no cubes. Turán’s theorem: statement and first application.
Turán’s theorem: two proofs and its application to the number of edges in permutation graphs. Turán numbers for general graphs and the Erdős–Stone theorem. Maximum number of edges in a graph containing no (4)-cycle.
Maximum number of edges in a graph containing no fixed complete bipartite graph (K_{t,s}), and applications to additive number theory. Probabilistic methods: elementary tools; tournaments with the Schütte property, in which every (k) players are beaten by somebody; (2)-colourability of uniform hypergraphs; linearity of expectation and its application to sum-free subsets.
Probabilistic methods: graphs with large girth and large chromatic number. Three famous results on finite sets: Sperner’s theorem and its application to the Littlewood–Offord problem, and Bollobás’s theorem on set pairs.
Three famous results on finite sets: the Erdős–Ko–Rado theorem. Kneser graphs and the application of the Borsuk–Ulam theorem to the chromatic number of Kneser graphs.
Algebraic methods: the Oddtown and Eventown problems, Fisher’s inequality, the number of lines determined by a non-collinear set of points, and two-distance sets in (\mathbb{R}^n).
Algebraic methods: bounds on the number of sets with restricted pairwise intersections, modular versions of the restricted-intersection problem, and a counterexample to Borsuk’s conjecture.
Spectral techniques: the adjacency matrix of a graph and its eigenvalues; eigenvalues of cliques, complete bipartite graphs, graph complements, and line graphs. Applications: decompositions of (K_{10}) into Petersen graphs and the Friendship Theorem.
Spectral techniques: the variational characterization of eigenvalues; bounds on Max-Cut, the chromatic number, and the independence number; graph expansion using eigenvalues.
视频公开
公开
笔记公开
公开
语言
英文
讲师介绍
Benny Sudakov received his PhD from Tel Aviv University in 1999. He had appointments in Princeton University, the Institute for Advanced Studies and in University of California at Los Angeles. Sudakov is currently professor of mathematics in ETH, Zurich. He is the recipient of a Sloan Fellowship, NSF CAREER Award, Humboldt Research Award, is Fellow of the American Math. Society and was invited speaker at the 2010 International Congress of Mathematicians. He authored more than 300 scientific publications and is on the editorial board of 14 research journals. His main scientific interests are combinatorics and its applications to other areas of mathematics and computer science.