MATH/CMSC 38502: Topics in Combinatorics and Logic

Winter 2019: Tuesday, Thursday 9:30am-10:50am (E 202)

Office hours: drop by (preferably by appointment) or ask your question on Piazza.
Projects:
- March 5
  - Mittal, Kronecker coefficients: a meeting point of combinatorics, representation theory and computational complexity
  - Srivastava, Covering and Packing in Hypergraphs: The Rodl Nibble
- March 7
  - Bajo, Halfgraphs and Szemeredi's Regularity Lemma
  - Tiago, Turing degrees
- March 12
  - Papamakarios, More about Goedel's theorems
  - Vale, Second-order logic and proof theory
- March 14
  - Meila & Stern, Combinatorial Objects from Database Reconstruction and Statistical Learning Theory

Literature.
1. N. J. Cutland, Computability, Cambridge University Press, 1980.
2. E. Mendelson, Introduction to Mathematical Logic, fifth edition, CRC Press, 2009.
3. M. Nathanson, Cantor Polynomials and the Fueter-Polya Theorem, American Mathematical Monthly, 123(10): 1001-1012, 2017.
4. M. Rabin, Decidable Theories, in Handbook of Mathematical Logic (Studies in Logic and the Foundations of Mathematics), ed. J. Barwise, North Holland, 1989.
5. B. Fine, A. Gaglione, G. Rosenberger, D. Spellman, The Tarski Problems and Their Solutions, Advances in Pure Mathematics, 5: 212-231, 2015.
6. W. W. Boone, F. B. Cannonito, R. C. Lyndon. Word Problems: Decision Problem in Group Theory, Netherlands: North-Holland, 1973.
7. R. Lyndon, P. Schupp, Combinatorial group theory, Springer-Verlag, Berlin, 2001.
8. H. Hatami, S. Norin, Undecidability of linear inequalities in graph homomorphism densities, J. Amer. Math. Soc., 24 (2011), 547-565.
9. A. Razborov, What is a Flag Algebra?, Notices of the AMS, 60(10): 1324-1327, 2013.
10. T. Tao and V. H. Vu, Additive Combinatorics, Cambridge University Press, 2009.
11. M. Sharir and P.K. Agarwal, Davenport-Schinzel Sequences and Their Geometric Applications, Cambridge University Press, 1995.
12. F. Eisenbrand, N. Hahnle, A. Razborov, T. Rothvoss, Diameter of Polyhedra: Limits of Abstraction, in Mathematics of Operations Research, Vol. 35, 2010, pages 786 - 794.
13. N. Alon, J. Spencer, The probabilistic method, 3rd ed., Wiley, 2008.
14. R. Moser, G. Tardos, A constructive proof of the general Lovasz local lemma, in Journal of the ACM , Vol. 57, 2010, pages 11:1-11:15.
15. J. E.. Greene, A new short proof of Kneser's conjecture, in American Mathematical Monthly, 109 (10), 2002, pages 918–920.
16. J. Kahn, M. Saks, D. Sturtevant, A topological approach to evasiveness, in Combinatorica, 4(4), 1984, pages 297-306.
17. P. Frankl, A new short proof for the Kruskal-Katona theorem, in Discrete Mathematics, 48, 1984, 327-329.
18. T.S. Motzkin, E.G. Straus, Maxima for graphs and a new proofof a theorem of Turan, in Canad. J. Math 17, 1965, pages 533-540.
19. L. Lovasz, Large networks and graph limits, American Mathematical Society, 2012.
20. A. Razborov, Flag algebras, in Journal of Symbolic Logic, 72(4), 2007, pages 1239-1282.
21. F. Chung, R. Graham, R. Wilson, Quasi-random graphs, in Combinatorica, 9, 1989, pages 345-362.
22. M. Krivelevich, B. Sudakov, Pseudo-random Graphs, in More Sets, Graphs and Numbers, Bolyai Society Mathematical Studies, vol 15. Springer, 2006.
23. A. Razborov, Flag Algebras: an Interim Report, in Mathematics of Paul Erdos II, Springer, 2013.
24. A. Potechin, Sum of squares lower bounds from symmetry and a good story, 2017.
25. G. Blekherman, A. Raymond, T. Reikha, M. Singh, Simple graph density inequalities with no sum of squares proofs, 2018.
26. L. Coregliano, A. Razborov, Semantic Limits of Combinatorial Objects, 2019.
Progress and further references.
- First week: Administrative. Vignette #1: Church-Turing thesis. Primitive recursive functions [1, Chapters 2.1-2.4; 2, Chapter 3.3]. The Ackermann function [1, Ch.2, Example 5.5], see also Wikipedia article. The latter contains our computation of A(4,3) as well as a few other values. The Ackermann function is not primitive recursive. Cantor polynomials and the Fueter-Polya theorem: [3]. Recursive functions [1, Ch. 3.2 and 2.5; 2, Ch. 3.3]. Turing machines [2, Ch. 5.1; 1, Ch. 3.4]. Post machines: [1, Ch. 3.5]. Unlimited register machines [1, Ch. 1 and 2]. Every recursive function is URM-computable [1, Theorem 3.2.2].
- Second week: Markov Normal Algorithms [2, Ch. 5.5; 1, Ch. 3.5]. Church-Turing Thesis [1, Ch. 3.7]. Vignette #2: Goedel's incompleteness theorem (almost) without Goedel encodings. Decidable problems, recursive and recursively enumerable sets [1., Ch. 6 and 7]. Enumerations $\phi_e$ and $W_e$ of recursive functions and r.e. sets [1, Ch. 4.2]. Halting problem is undecidable [1, Thm 6.1.3]. Many-one reducibility [1, Ch. 9.1]. Universal sets are called m-complete in [1, Ch. 9.3]. First-order logic [2, Ch. 2; 1, Ch. 8.1]. Peano Arithmetic [2, Ch. 3.1]. Defining new function symbols [2, Ch. 2.9]. Recursive functions are definable (representable) in PA [2, Proposition 3.24]. Th(PA) is undecidable [1., Ch. 8.3; 2., Ch. 3.6] and hence incomplete (for details see [2, Prop. 3.47]). The same will remain true for any effective extension of PA [1, Thm. 9.2.4; 2, Cor. 3.48]. Vignette #3: Decidable and undecidable problems. Robinson's Arithmetic is called RR in [2, Ch. 3.4].
- Third week: Deduction Theorem [2, Ch. 2.4, Prop. 2.5]. Pure first-order calculus is undecidable [2, Ch. 3.6, Cor. 3.52]. [4] is an excellent survey on decidable theories (and methods to prove their decidability). Buchi's Theorem, Rabin's Theorem etc.: [4, Sct. 3.2-3.5] (for proofs, see the references therein). Hilbert's Tenth problem [1, Ch. 6.3 and 6.6.]. Elementary theory of free groups (aka Tarski's problems): [5]. Word problem in groups [1, Ch. 6.2]; for more information see Wikipedia article or [6]. Adian-Rabin theorem: Wikipedia article, and the reference [7] suggested therein is an excellent source of knoweldge for combinatorial group theory in general. Asymptotic extremal combinatorics is undecidable [8]; for the context see [9] (we will re-visit this later). For a compendium of undecidable problems in mathematics, see Wikipedia article.
- Fourth week (short): Mini-Vignette #4: Completeness and Compactness. Completeness theorem for the first-order logic: [2, Ch. 2.12]. De Bruijn-Erdos theorem: Wikipedia article. Hadwiger-Nelson problem: Wikipedia article. See also lovely story in the Quanta Magazine. Szemeredi's theorem: [10, Ch. 10]. Vignette #5: Interval Geometry. Lower envelopes and Davenport-Schinzel sequences [11, Ch. 1.1]. Upper bounds on the length of DS-sequences of order 3: [11, Ch. 2.2].
- Fifth week: Davenport-Schinzel sequences cntd. Combinatorial approach to the Hirsh conjecture [12], see also (dormant) Polymath project that came out of it. Vignette #6: The probabilistic method. Condorcet paradox: Wikipedia article. Tournaments with property S(k): [13, Thm. 1.2.1]. Sperner's theorem: [13, pages 219-220].
- Sixth week: Lower bounds on the crossing number: [10, Theorem 8.1]. Szemeredi-Trotter theorem: [10, Theorem 8.3]. Lovasz's Local lemma: [13, Ch. 5]. A constructive proof: [14]. Vignette #7: Topological methods. A proof of Kneser's conjecture: [15]. Evasiveness: Wikipedia article. Proof of the evasiveness conjecture for prime powers: [16].
- Seventh week: Kahn-Saks-Sturtevant cntd. Vignette #8: Extremal Combinatorics. Kruskal-Katona theorem: [17]. The proof of Turan's theorem using Lagrangians: [18]. Mini-Vignette #9: Polynomial method. Combinatorial Nullstellensatz: [10, Thm. 9.2]. Cauchy-Davenport inequality: [10, Thm. 9.4]. Vignette #10: Continuous Combinatorics. Preamble: huge combinatorial objects [19, part 1; 20, Sct. 1]. Sampling densities/probabilities/frequencies: [19, Ch. 5.2; 20, Def. 1]. Conversion formulas: [19, Sct. 5.2.3].
- Eighth week: Quasi-random (aka pseudo-random) graphs: [21,22]. Convergent sequences: [19, Ch. 11; 20, Ch. 3.1]. Graphons: [19, Ch. 13-14]. Master theorem on cryptomorphisms: [19, Thm. 11.52]. Syntax of flag algebras: [20, Ch. 2]. Cryptomorphism between convergent sequences and flag algebra homomorphisms: [20, Thm. 3.3]. Averaging operator: [20, Ch. 2.2] and disappointingly indirect proof of its positivity: [20, Thm 3.1(a)]. A (somewhat outdated) survey of concrete results obtained with flag algebras: [23]. Undecidability (reminder): [8]. Concrete problems not solvable by sum of squares: [24,25]. Limit objects other than graphs: [26] and the literature cited therein.
- Nineth and tenth weeks: Projects (see above).