Embedded Files
Instructor: Dr. Shen-Fu Tsai （蔡昇甫）
Office: M414, Hong-Jing Hall
Phone: 03-4227151 ext. 65125
E-mail: parity@math.ncu.edu.tw, parity@gmail.com
Office hour: by appointment
Image credit: Kilom691, CC BY-SA 3.0 <https://creativecommons.org/licenses/by-sa/3.0>, via Wikimedia Commons
Course objective:
This course aims to introduce students into the field of extremal combinatorics on pattern avoidance, with the focus mainly on 0-1 matrices. The students will acquire the basic problem definitions, high level overview in the context of classical graph theory, and various techniques for tackling the problems. By the end of the course, students should gain reasonable understanding of the are and be familiar with the involved techniques and connections with other areas of discrete mathematics.
Covered materials:
2023/2/16
High level definition of containment, avoidance, and the ex function
Definitions of 0-1 matrix and simple graph, and their containment and avoidance
Definitions of directed graph
Double counting
2023/2/23
Zarankiewicz problem and Kővári–Sós–Turán theorem
Containment of sequences, Davenport-Shinzel sequences
Containment of permutation, Stanley-Wilf conjecture
2023/3/02
Stanley-Wilf conjecture
Füredi–Hajnal conjecture, proof that Füredi–Hajnal conjecture implies Stanley-Wilf conjecture [Kla00]
Ordered graph and its containment and ex function
r-partite graph, bipartite graph, bipartite ordered graph
Relations among extremal functions of graph, ordered graph, and 0-1 matrix [PT06]
Turán's theorem
2023/3/09
Proof of Turán's theorem
Chromatic number
Erdős-Stone theorem, Erdős-Simonovits theorem, and how the former implies the latter
2023/3/16
Proof of Erdős-Stone theorem except for the key inductive step
Interval coloring and interval chromatic number of ordered graph
Erdős-Stone-Simonovits theorem for ordered graph [PT06]
2023/3/23
Finish proof of Erdős-Stone theorem
Proof that the greedy interval coloring algorithm is optimal
Bridge playing rules
2023/3/30
Reduction technique for 0-1 matrices that preserve linearity of ex function [Tar05]
Super-additivity of ex function [PT06]
ex functions of associated 0-1 matrices and ordered graphs are within a log(n) factor [PT06]
2023/4/13
Extremal functions of associated 0-1 matrices and ordered graphs are within a log(n) factor [PT06]
Expansions of 0-1 matrices that limit the growth of ex function to a log(n) multiplicative factor [PT06]
2023/4/20
First example of categorization method for proving the linearity of ex function [FH92]
Using planar graph and bar visibility graph to prove the linearity of ex function [Ful09]
2023/4/27
Using s-bar visibility hypergraph to prove the linearity of ex function [GS15]
Second example of categorization method for proving the linearity of ex function [Tar05]
Proof that ex function of permutation matrix is linear [MT04]
2023/5/04
Power-of-two-based nlog(n) construction [Pet11b]
A powerful recursive nlog(n) construction [Pet11b]
An nlog(n) construction based on lexicographical and anti-lexicographical orders [Tar05]
2023/5/11
Finite projective plane
Axioms P1, P2, P3, and how they imply P4
Every line has the same number of points, and every point lies in the same number of lines
Finite field based on prime
2023/5/18
Construction of finite projective plane based on finite field
Minimally nonlinear matrix
Potential usage of identifying all matrices with linear ex function
There are infinite minimally nonlinear matrices [Gen09]
2023/5/25
Minimally nonlinear matrix has aspect ratio in (0.25, 4) [Cro18]
Multidimensaionl 0-1 matrix
Range of ex function [GT17]
Permutation matrix [KM07]
Block matrix [GT17]
2023/6/01
References:
Research papers provided by the instructor. We'll only cover some of them!
West, Douglas B. Combinatorial Mathematics. Cambridge University Press, 2020
West, Douglas B. Introduction to graph theory. Vol. 2. Upper Saddle River: Prentice hall, 2001.
Grading policy:
Class participation or presentation: 20%
Homework assignment or quiz: 80%
Important dates:
No class on April 6, 2023
Page updated
Google Sites
Report abuse