Seminar on Advanced Mathematics (Combinatorial Structures) | MA

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.

Assignments


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 \pi = (\mathcal{P} , \mathcal{L}) is called a projective plane if  \pi = (\mathcal{P} , \mathcal{L}) satisfies the following properties.
1. For all P,Q\in\mathcal{P}, there exists a unique l \in \mathcal{L} with P,Q\in l
2. For all, l,m \in \mathcal{L}, there exists a unique P\in \mathcal{P} with P\in l \cup m.
3. There exists 4 points in \pi 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 q\in\mathbb{N} such that
(i) |l|=q+1 for each l \in\mathcal{L} and
(ii) |l(\mathbb{P})|=q+1 for each P\in\mathcal{P}.

Then, the order of the projective plane \pi is q. Then, the projective plane \piis written as \pi_{q}.

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 A,B be two finite sets with |A|>|B|. Then, for every function f:A\longrightarrow B, there exist at least two distinct elements x, x' \in A such that f(x)=f(x').

Ramsey Number

The Ramsey number R(s,t) is defined by R(s,t)=min\{n\in \mathbb{N} : \textup{Every graph of order } n \textup{ contains } K_s \textup{ or } \overline{K_t}; s,t\in\mathbb{N}\}.

  •  K_s is a graph of order s such that each vertex is connected to all other vertices. K_s is called the complete graph of order s. If K_s is in a graph, then it is called a clique.
  • \overline{K_t} is a graph of order t such that each vertex is not connected to all other vertices. \overline{K_t} is called the null graph of order t.
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 (X,R) such that

  • X is a ground set.
  • R\subset X\times X with the conditions
    • [Reflexive] \forall x\in X, (x,x)\in R
    • [Anti-symmetric] If (a,b)\in R, then (b,a)\notin R
    • [Transitive] If (a,b)\in R and (b,c)\in R , then (a,c)\in R.
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 T_f(P)of the poset P with respect to the labeling f is the maximum label difference between labels of incomparable elements.

Linear Discrepancy

The least discrepancy ld(P) of the poset P 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.

Leave a Reply

Your email address will not be published. Required fields are marked *