###### Brief Information

- Name : Seminar on Advanced Mathematics 고급수학세미나
- Lecturer : Sang-Mok Kim 김상목
- Semester : 2016 Fall
- Major : BS, Mathematics
- Textbook
- 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.

- key words:

#### Assignments

- 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.

###### Projective Plane

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 .

###### Desarguisian Plane

###### The Bruck-Rayser-Chowla Theorem

###### Design

###### (v, k, λ)-BIBD, Balanced Incomplete Block Design

###### Incidence Matrix of a Design

###### Group, Ring, and Field

#### 3. Ramsey Theory: Pigeonhole Principle and Double Counting

###### Pigeonhole Principle

Let be two finite sets with . Then, for every function , there exist at least two distinct elements such that .

###### Ramsey Number

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

###### Hamiltonian Cycle

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**.

###### Eulerian Cycle

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**.

#### 5. Posets

###### Poset

A partially ordered set, so-called poset, is the pair such that

- is a ground set.
- with the conditions
- [Reflexive]
- [Anti-symmetric] If , then
- [Transitive] If and , then .

###### Hesse Diagram

A **Hesse diagram** is a graphical representation of a poset, which represents only anti-symmetric relations using edges except reflexive or transitive relations.

###### Tightness

The **tightness** of the poset with respect to the labeling is the maximum label difference between labels of incomparable elements.

###### Linear Discrepancy

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.