- Name : Seminar on Advanced Mathematics 고급수학세미나
- Lecturer : Sang-Mok Kim 김상목
- Semester : 2016 Fall
- Major : BS, Mathematics
- Syllabus : Syllabus_2016-5-2__Seminar on Advanced Mathematics.pdf
- In short
- key words: combinatorial structures, finite structures, projective planes, Desarguisian planes
- In this course, unsolved problems are introduced in the fields of combinatorial structures.
- Kruskal’s Algorithm | Essay Assignment | Seminar on Advanced Mathematics
- B+ Tree | Presentation Assignment | Seminar on Advanced Mathematics
1. Subfields of Combinatorics
- Enumerative combinatorics
- Graph theory
- Order theory
- Finite geometry
- Design theory
- Sequence and arrays, etc.
2. Projective Planes
Finite Structure / Finite Geometry
A triple S = (P, L, I) is called a finite structure or finite geometry if
1. P is a finite set, which is called the set of points.
2. L is a collection of subsets of P, which is called the set of lines[=blocks]
3. I is a set of relations between P and L, which is called an incidence relation of S.
An incidence structure is called a projective plane if satisfies the following properties.
1. For all , there exists a unique with
2. For all, , there exists a unique with .
3. There exists 4 points in such that none of three are linear.
- If three points are linear, that means three points are in a line.
- The third condition can be said that ‘there exists a quadrangle‘ in a projective plane. The negation of the third statement is ‘there exists a pencil’ in an incidence structure. A pencil is an incidence structure that has four points such that three points are in the same line.
The Order of a Projective Plane
For a finite projective plane, there exists such that
(i) for each and
(ii) for each .
Then, the order of the projective plane is . Then, the projective plane is written as .
The Bruck-Rayser-Chowla Theorem
(v, k, λ)-BIBD, Balanced Incomplete Block Design
Incidence Matrix of a Design
Group, Ring, and Field
3. Ramsey Theory: Pigeonhole Principle and Double Counting
Let be two finite sets with . Then, for every function , there exist at least two distinct elements such that .
The Ramsey number is defined by .
- is a graph of order such that each vertex is connected to all other vertices. is called the complete graph of order . If is in a graph, then it is called a clique.
- is a graph of order such that each vertex is not connected to all other vertices. is called the null graph of order .
Finding Ramsey Numbers
It is easy to find that R(1,n)=1, R(2,2)=1, and R(2,3)=3. However, proving R(3,3)=6 is a little bit challenging. To prove R(3,4)=9, the fact R(3,3)=6 is used. To prove R(4,4)=18, the fact R(3,4)=9 is used.
4. Graph Theory
A Hamiltonian cycle, also called a Hamiltonian circuit, Hamilton cycle, or Hamilton circuit, is a graph cycle (i.e., closed loop) through a graph that visits each node exactly once (Skiena 1990, p. 196). A graph possessing a Hamiltonian cycle is said to be a Hamiltonian graph.
An Eulerian cycle, also called an Eulerian circuit, Euler circuit, Eulerian tour, or Euler tour, is a trail which starts and ends at the same graph vertex. In other words, it is a graph cycle which uses each graph edge exactly once. A graph containing an Eulerian cycle is said to be an Eulerian graph.
A partially ordered set, so-called poset, is the pair such that
- is a ground set.
- with the conditions
- [Anti-symmetric] If , then
- [Transitive] If and , then .
A Hesse diagram is a graphical representation of a poset, which represents only anti-symmetric relations using edges except reflexive or transitive relations.
The tightness of the poset with respect to the labeling is the maximum label difference between labels of incomparable elements.
The least discrepancy of the poset is the minimum of all tightness.
Total Linear Discrepancy
The total linear discrepancy is the minimum of sums of all difference between labels of incomparable elements.