# Enumerative Combinatorics School 2014

The * Enumerative Combinatorics School 2014* (ECS2014) will be held at Center for Applications of Mathematical Principles (CAMP), National Institute for Mathematical Sciences (NIMS), Daejeon on April 4-6, 2014.

The purpose of this school is not just presenting individual works but teaching basic concepts and tools of enumerative combinatorics. So we invite 4 lecturers, each of whom has two 90-minute letures or three 60-minute lectures. All topic of lectures are including "*enumeration*" of combinatorial objects, and the style of talk tends to be less formal.

In principle, registration is on a first-come, first-served basis. If you want to participate, please write a registration form until March 21.

## Information

**Title**Enumerative Combinatorics School 2014 (계수적 조합수학 스쿨 2014)**Date**April 4-6 (Fri-Sun), 2014**Venue**CAMP, NIMS, Daejeon

**Organizers**

Seunghyun Seo (Kangwon National University)

Heesung Shin (Inha University)

**Host**National Institute for Mathematical Sciences**Sponsor**2014 NIMS School (2014년 개방형 학술교류 프로그램)

We are going to

give just six 60-minute lectures and four 90-minute lectures in Korean.

provide for 6 meals (dinner of April 4, breakfast, lunch & dinner of April 5, and breakfast & lunch of April 6) of all participants.

support the accommodation of all participants registered until March 21. (except from Daejeon area)

distribute the abstracts of ECS2014.

## Invited Lecturers

Jang Soo Kim (Sungkyunkwan University)

Sangwook Kim (Chonnam National University)

Boram Park (NIMS)

Seunghyun Seo (Kangwon National University)

## Timetable

April 4 (Friday)

00h00 - 14h00 Registration

14h00 - 00h00 Opening Ceremony

14h00 - 15h00 Lecture SS-1

15h15 - 16h45 Lecture BP-1

17h00 - 18h00 Lecture SK-1

18h00 - 00h00 Dinner

April 5 (Saturday)

08h30 - 09h30 Breakfast

09h30 - 10h30 Lecture SS-2

10h45 - 12h15 Lecture JK-1

12h15 - 14h00 Lunch

14h00 - 15h00 Lecture SK-2

15h15 - 16h45 Lecture BP-2

17h00 - 18h00 Lecture SS-3

18h00 - 00h00 Dinner

April 6 (Sunday)

08h30 - 09h30 Breakfast

09h30 - 10h30 Lecture SK-3

10h45 - 12h15 Lecture JK-2

12h15 - 00h00 Closing Ceremony

## Program

Lecture JK-1

**Speaker**Jang Soo Kim (Sungkyunkwan University)**Language**Korean**Length**90 min**Title**Viennot’s combinatorial theory of orthogonal polynomials**Abstract**An orthogonal polynomial sequence is a family of polynomials which are orthogonal under an inner product. In this lecture we will study Viennot’s combinatorial theory of orthogonal polynomials.We will first start with definitions and basic properties of orthogonal polynomials such as 3-term recurrence relations. We then show that the moment of orthogonal polynomials can be viewed as a generating function for weighted Motzkin paths. We will see that the moments of Hermite, Charlier, and Laguerre polynomials are equal to the numbers of matchings, partitions, and permutations. If time permites, we will also consider q-analogs of these polynomials.

**Video**

http://open.nims.re.kr/new/board/upload/event/vod/[20140414546542].wmv

http://open.nims.re.kr/new/board/upload/event/vod/[20140414735322].wmv

Lecture JK-2

**Speaker**Jang Soo Kim (Sungkyunkwan University)**Language**Korean**Length**90 min**Title**Linearization coefficients**Abstract**For an orthogonal polynomial sequence, the nth polynomial p_{n}(x) is of degree n. Thus we can always write p_{n}(x)p_{m}(x) as a unique linear sum of these polynomials, i.e.,

p_{n}(x)p_{m}(x) = ∑_{l} a_{n,m,l} p_{l}(x)

The coefficients a_{n,m,l} are called linearization coefficients.

In the second lecture we will show that the linearization coefficients for Hermite, Charlier Laguerre polynomials are equal to the numbers of inhomogeneous matchings, inhomogeneous partitions, and multi-derangements. If time permites, we will also consider q-analogs of these polynomials.

**Video**

http://open.nims.re.kr/new/board/upload/event/vod/[20140414152732].wmv

http://open.nims.re.kr/new/board/upload/event/vod/[20140414865812].wmv

Lecture SK-1

**Speaker**Sangwook Kim (Chonnam National University)**Language**Korean**Length**60 min**Title**Order complexes and face posets**Abstract**We begin by defining the order complex of a poset and the face poset of a simplicial complex. These constructions enable us to view posets and simplicial complexes as essentially the same topological object. They link combinatorics with topology and other areas of mathematics in a deep and fundamental way. Combinatorial interest in poset topology dates back to Gian-Carlo Rota’s seminal 1964 paper on the Möbius function of a partially ordered set. The Möbius number of a poset, an important combinatorial invariant, is equal to the reduced Euler characteristic of the order complex, an important topological invariant.

We will discuss various applications of poset topology in the theory of hyperplane and subspace arrangements. Some connections with graphs, groups and lattices are also discussed.

**Video**http://open.nims.re.kr/new/board/upload/event/vod/[20140414208412].wmv**Reference**Poset Topology: Tools and Applications, written by Michelle L. Wachs

Lecture SK-2

**Speaker**Sangwook Kim (Chonnam National University)**Language**Korean**Length**60 min**Title**Shellability and edge labelings**Abstract**Shellability is a combinatorial property of simplicial and more general cell complexes, with strong topological and algebraic consequences. Shellability first appeared in the middle of the nineteenth century in Schläfli's computation of the Euler characteristic of a convex polytope. The original theory of shellability applied only to pure complexes. In the early 1990's, a nonpure simplicial complex arose in the complexity theory with topological properties somewhat similar to those of pure shellable complexes. This led Björner and Wachs to extend the theory of shellability to nonpure complexes.

Lexicographic labeling is an labeling of the edges of the Hasse diagram of a poset in a certain way which implies shellability of the order complex of the poset. Two versions of lexicographic shellability, EL-shellability and CL-shellability will be discussed with several examples.

**Video**http://open.nims.re.kr/new/board/upload/event/vod/[20140414738122].wmv**Reference**Poset Topology: Tools and Applications, written by Michelle L. Wachs

Lecture SK-3

**Speaker**Sangwook Kim (Chonnam National University)**Language**Korean**Length**60 min**Title**Recursive techniques**Abstract**The recursive definition of the Möbius function of a poset provides a recursive technique for computing the reduced Euler characteristic of the order complex of a poset. More refined recursive techniques for computing the homology of a poset are discussed. A general class of posets to which these techniques can be applied, the Cohen-Macaulay posets or more generally the sequentially Cohen-Macaulay posets, are discussed. A recursive formulation of CL-shellability and the recursive techniques for computing Betti numbers are also presented.**Video**http://open.nims.re.kr/new/board/upload/event/vod/[20140414967012].wmv**Reference**Poset Topology: Tools and Applications, written by Michelle L. Wachs

Lecture BP-1

**Speaker**Boram Park (NIMS)**Language**Korean**Length**90 min**Title**List coloring of a graph**Abstract**A proper coloring of a graph G is a function ϕ defined on V(G) such that ϕ(v)≠ϕ(w) for any two adjacent vertices v and w. The chromatic number of a graph is the smallest integer k such G admits a proper coloring ϕ such that the number of used colors |ϕ(V(G))| is k. A list assignment L of a graph G is a function defined on V(G) such that for each vertex v, L(v) is a finite set. For a positive integer k, for a graph G, we say G is k-choosable if for any list assignment L of G such that |L(v)|=k for any vertex v, there is a proper coloring ϕ of G such that ϕ(v)∈L(v) for any vertex v. The list chromatic number of a graph is the smallest integer k such that G is k-choosable. We will see some results and properties of list coloring of a graph. The List Coloring Conjecture sates that the chromatic number and the list chromatic number of any line graph are the same, and we discuss their related topics as well. In addition, we discuss paintability of a graph as a generalization of the list coloring.**Video**http://open.nims.re.kr/new/board/upload/event/vod/[20140414766152].wmv

Lecture BP-2

**Speaker**Boram Park (NIMS)**Language**Korean**Length**90 min**Title**Alon-Tarsi Theorem**Abstract**In 1992, N. Alon and M. Tarsi showed that counting even circuits and odd circuits of certain orientation of a graph is related to the list chromatic number of the graph. The circuit C of a digraph is a subset of the arc set such that for any vertex v, the indegree and the outdegree of v in the subdigraph induced by C are the same. A circuit C is even if |C| is even, and C is odd if |C| id odd. Alon-Tarsi Theorem states that if the number of even circuits and the number of odd circuits of an orientation D of a graph G are not the same, then the list chromatic number of G is at most (maximum out-degree of D)+1. In this class, we see the proof of Alon-Tarsi Theorem concisely, then see some results obtained by using Alon-Tarsi Theorem. Brook’s Theorem is one famous theorem in graph coloring, stating that the chromatic number of a graph is bounded by the maximum degree of a graph if the graph is neither a complete graph nor an odd cycle. The list version of Brook’s Theorem is also true, and we could prove it by using Alon-Tarsi Theorem. In addition, if a graph G is a complete graph with odd vertices or a complete bipartite graph, we can obtain the list chromatic number of the line graph of G by using Alon-Tarsi Theorem.**Video**

http://open.nims.re.kr/new/board/upload/event/vod/[20140414100172].wmv

http://open.nims.re.kr/new/board/upload/event/vod/[20140414163222].wmv

Lecture SS-1

**Speaker**Seunghyun Seo (Kangwon National University)**Language**Korean**Length**60 min**Title**Enumeration of various families of labeled trees: Part I**Abstract**A labeled tree of size n is a rooted tree consisting of n nodes that are labeled by the set {1,...,n} usually. On labeled trees, we can assign various conditions, which are kinds of restrictions or generalizations. In the 1st talk, we introduce classic families of labeled trees and present the result of their enumeration.**Video**http://open.nims.re.kr/new/board/upload/event/vod/[20140411854332].wmv

Lecture SS-2

**Speaker**Seunghyun Seo (Kangwon National University)**Language**Korean**Length**60 min**Title**Enumeration of various families of labeled trees: Part II**Abstract**A labeled tree of size n is a rooted tree consisting of n nodes that are labeled by the set {1,...,n} usually. On labeled trees, we can assign various conditions, which are kinds of restrictions or generalizations. In the 2nd talk, we discuss the connections to other combinatorial objects such as permutations, partitions, hyperplane arrangements, parking functions, etc.**Video**http://open.nims.re.kr/new/board/upload/event/vod/[20140414317862].wmv

Lecture SS-3

**Speaker**Seunghyun Seo (Kangwon National University)**Language**Korean**Length**60 min**Title**Enumeration of various families of labeled trees: Part III**Abstract**A labeled tree of size n is a rooted tree consisting of n nodes that are labeled by the set {1,...,n} usually. On labeled trees, we can assign various conditions, which are kinds of restrictions or generalizations. In the 3rd talk, we present some recent work on the enumeration of certain labeled trees.**Video**http://open.nims.re.kr/new/board/upload/event/vod/[20140414898372].wmv

## Registration

There is NO registration fee. Just write a registration form until March 21.

Due to the budget for 50 persons, we set a limit on the number of participants.

In principle, registration is on a first-come, first-served basis. But some special participants could be registered in advance by organizers.

So your registration could be refused if the number of registrations is over 50, although you submit your registration form before March 21.

## Accommodation

The main hotel of school is Hotel Interciti, which is located at 92, Oncheon-Ro, Yuseong-gu, Daejeon, Korea.

The reservations for hotel was already made by NIMS. Please give your name at check-in front after first din ner.

Check your roommates in a below list.