Summer school 2021 at Shandong University

Welcome to the webpage of the online summer school course by Jaehoon Kim (JK) and Hong Liu (HL). This summer school one-week-course consists of two parts. The first part (by JK) is about expanders, i.e.~graphs whose all vertex sets have large neighborhood. This simple-looking notion is important in many areas of mathematics and computer sciences. The expanders can be defined in a combinatorial way, a probabilistic way and an algebraic way. There are interesting connections between them. We will see why expanders are useful, and how different definitions are related. The lecture will be based on the survey on expander graphs written by Hoory, Linial and Wigderson. In the second part (by HL), we will cover some methods involving entropy. Entropy, being a central concept in information theory, has proven to be a power tool also for problems in combinatorics. We will see some of its classical applications and also some recent ones. No prerequisite is needed, though some familiarity with linear algebra, analysis and graph theory and probability would help.

•   Time:   Everyday July 26 - August 1, Beijing time 10:10 - 12:00 (JK) and 14:00 - 15:40 (HL)
•   Zoom ID:   820 6787 2021,   password: 202121

Announcement

•   August 1 afternoon class is moved to the morning at 8:30.

•   Lecture 1. (Jul 26) Applications of expander graphs to construction of good error correcting codes and deterministic error amplification for randomized algorithm with polynomial run time. Video Note 1
  
•   Lecture 2. (Jul 27) Spectrum of graphs, Expander mixing lemma, Relation between the edge expansion ratio and spectral gap. Video Note 2
  
•   Lecture 3. (Jul 28) Random walks, relation between the spectrum and fast mixing. Video Note 3
  
•   Lecture 4. (Jul 29) Alon-Boppana theorem, Lower bounds on the constant fraction of eigenvalues of graphs. Video Note 4
  
•   Lecture 5. (Jul 30) Margulis construction. Video Note 5
  
•   Lecture 6. (Jul 31) Zig-zag product, application of zig-zag product to show L=SL. Video Note 6
  
•   Lecture 7. (Aug 1) Lossless conductor (bipartite graphs with near-optimal vertex expansion). Video Note 7
  

•   Lecture 1. (Jul 26) Definition of entropy, entropy axioms à la Shannon-Khinchin, independence, non-negativity, monotonicity. Tablet note Video
  
•   Lecture 2. (Jul 27) Chain rule, subadditivity, Shearer's lemma, Loomis-Whitney inequality, entropy function satisfies axioms. Tablet note Video
  
•   Lecture 3. (Jul 28) Summary of basic properties, volume of Hamming balls, triangle maximisation, triangle-intersecting family, entropy of uniform distribution. Tablet note Video
  
•   Lecture 4. (Jul 29) Axioms determine entropy function uniquely, Brégman's theorem on permanent of 0,1-matrices, Sidorenko's conjecture for star of size 2. Tablet note Video
  
•   Lecture 5. (Jul 30) Sidorenko's conjecture for bipartite graphs with a dominating vertex, H-colourings. Tablet note Video
  
•   Lecture 6. (Jul 31) Independent sets in bipartite regular graphs, counting matroids. Tablet note Video
  
•   Lecture 7. (Aug 1) Tao's entropy proof for sunflower. Tablet note Video