Program

(PDF download)

DAY 1 (10/31 Friday)      

DAY 2 (11/ 1 Saturday)      

Abstract

(PDF download)

Invited talks

• 국  웅 Woong Kook (Seoul National Univ.) Topological invariants and tree numbers of matroids
  There are several simplicial complexes naturally associated with a matroid, and for that reason, topological methods are often employed in describing various matroid invariants.
  In this talk, we will discuss topological invariants of the independent set complex and the broken circuit complex of a matroid, and their intriguing applications to the spectra of combinatorial Laplacians and the high-dimensional tree numbers of matroid complexes. If time permits, an application to Stanley's $M$-vector conjecture will be presented.
   
• 박보람 Boram Park (Ajou Univ.) Coloring powers of graphs
  Coloring and List coloring of graphs not only are one famous research field in graph theory but also have many applications to real world problems. In this talk, we present several famous conjectures and results, which are related to coloring and list coloring of the power of a graph, including List Square Coloring Conjecture.
   
• 신희성 Heesung Shin (Inha Univ.) Continued fractions and generalized Fibonacci numbers
  The generalized Fibonacci numbers $G_n$ are defined by nonnegative integers $G_0$, $G_1$ and
  $$G_n = G_{n-1} + G_{n-2} \quad \text{for $n\ge 2$.}$$
  Thus $G_n = a \alpha^n + b \beta^n$ for some $a$ and $b$, where $(\alpha, \beta) = (\frac{1+\sqrt{5}}{2}, \frac{1-\sqrt{5}}{2})$.
  The number $G_n$ counts the ways to tile an $(n+1)$-board of dominoes and square tiles with phases for the initial tile.
  For example, the Fibonacci numbers $F_n = \frac{1}{\sqrt{5}}(\alpha^n - \beta^n)$ with $F_0 = 0$ and $F_1=1$ are generalized Fibonacci numbers and the Lucas numbers $L_n = \alpha^n + \beta^n$ with $L_0 = 2$ and $L_1=1$ are also. Thus $F_n$ is the number of unphased $(n-1)$-tilings with squares and dominoes and $L_n$ is the number of $n$-bracelets with square and dominoes.
  
  Given positive integers $a_0, a_1, \dots, a_n$, define $[a_0, a_1, \dots, a_n]$ to be the continued fraction for
  $$ a_0 + \cfrac{1}{ a_1 + \cfrac{1}{ a_2 + \cfrac{1}{ \ddots + \cfrac{1}{ a_n}}}} $$
  Let $p$ and $q$ be functions producing the numerator and denominator of the {\em finite continued fraction} $[a_0, a_1, \dots, a_n]$ in lowest terms. For example, due to $[2,3,4,2] = \frac{67}{29}$,
  $$p(2,3,4,2)=67 \quad \text{and} \quad q(2,3,4,2)=29.$$
  
  Here, let's do some combinatorics.
  The number $p(a_0, a_1, \dots, a_n)$ counts the ways to tile an $(n+1)$-board of dominoes and {\em stackable} square tiles with height conditions $a_0, a_1, \dots, a_n$.
  Also, since $q(a_0, a_1, \dots, a_n) = p(a_1, \dots, a_n)$,
  the number $q(a_0, a_1, \dots, a_n)$ is the number of $n$-tilings with height conditions $a_1, \dots, a_n$.
  
  In this talk, we combinatorially prove that if $m$ is odd, then
  $$\frac{F_{(t+1)m}}{F_{tm}} = [L_m, L_m, \dots, L_m]$$
  where the number $L_m$ appears $t$ times. Also we could generalize it.
   
• 이상준 Sang June Lee (Duksung Women's Univ.) Universality of random graphs for graphs of maximum degree two
  A graph $G=G(V,E)$ consists of a vertex set $V$ and an edge set $E$ of two element sets of $V$.
  For a positive integer $n$ and a real number $p$ with $0\leq p\leq 1$, the random graph $G(n,p)$ is a graph obtained from the complete graph on $n$ vertices by choosing each edge with probability $p$, independently of all other edges.
  After the random graph $G(n,p)$ was first introduced by Erd\H{o}s in 1947, the theory of the random graph has become an active area of research.
  
  One of the most interesting problems is the containment problem, in which one tries to obtain conditions on $p$ for the property that $G(n,p)$ contains a given graph $H$ as a subgraph with high probability.
  
  In this talk, we consider a containment problem with respect to a family of graphs rather than a single graph. For a family $\cF$ of graphs, a graph $G$ is called \emph{$\cF$-universal} if $G$ contains every graph in $\cF$ as a subgraph. Constructing an universal graph with a small number of edges plays an important role in VLSI design in computer science, and is also an interesting combinatorics problem.
  
  Let $\cF^*$ be the family of all graphs on $n$ vertices with maximum degree at most $2$. We show that the random graph $G(n,p)$ is $\cF^*$-universal with high probability provided $p\geq C\big(\frac{\log n}{n}\big)^{1/2}$ for a sufficiently large constant~$C$.
  This is joint work with Jeong Han Kim.
   

Contributed Talks

• 정지수 Jisu Jeong (KAIST) Planar graphs with girth 5 are (1,10)-colorable
  A graph is (d_1,...,d_r)-colorable if its vertex set can be partitioned into r sets V_1,...,V_r so that the maximum degree of the graph induced by V_i is at most d_i for each i\in {1,...,r}. For a given pair (g,d_1), the question of determining the minimum d_2 = d_2(g,d_1) such that planar graphs with girth g are (d_1,d_2)-colorable has attracted much interest. The finiteness of d_2(g,d_1) was known for all cases except when (g,d_1)=(5,1). Montassier and Ochem explicitly asked if d_2(5,1) is finite. We answer this question in the affirmative with d_2(5,1)\le 10; namely, we prove that all planar graphs with girth at least 5 are (1,10)-colorable. Moreover, we prove that for any surface S of Euler genus \gamma, there exists a K = K(\gamma) where graphs with girth at least 5 that are embeddable on S are (1,K)-colorable. On the other hand, it was already known that there is no finite k where planar graphs with girth at least 5 are (0,k)-colorable. This is joint work with Hojin Choi, Ilkyoo Choi, and Geewon Suh.
   
• 최지훈 Jihoon Choi (Seoul National Univ.) On competition graphs of n-tuply partial orders
  Studying competition graphs of interesting digraphs is a basic open problem in the study of competition graphs. In this context, Cho and Kim~\cite{chokim} studied competition graphs of doubly partial orders and gave a nice characterization of the competition graphs of doubly partial orders. In this paper, we extend their results to a general case, which turns out to be quite interesting. Especially, we take a close look at the competition graphs of triply partial orders to present their meaningful properties.
   
• 최광주 Kwang Ju Choi (NIMS) The structure of non-planar graphs containing a critical edge
  By Kuratowski and Wagner's theorem, if we delete or contract any edge of $K_{3,3}$ or $K_5$, it becomes planar. We consider the class $\mathcal{C}$ of non-planar graphs $G$ containing an edge $e$ such that both $G\setminus e$ and $G/e$ are planar. Then, every member of $\mathcal{C}$ has alternating double wheel as a topological minor. This is a joint work with Guoli Ding.
   
• 박한철 Hanchul Park (KIAS) Simplicial spheres, wedge operations and classification of toric varieties
  A fundamental result in toric geometry is that there exists a bijection between toric varieties and fans. More generally, it is known that some class of manifolds having well-behaved torus actions, called topological toric manifolds. Similar to toric varieties, topological toric manifolds $M$ can be described in terms of combinatorial data containing simplicial complexes $K$.
  The classification problem for toric varieties is important but seems difficult even for smooth case. Smooth complete toric varieties of Picard number 3 were classified by Batyrev. In this talk, we discuss the classification of smooth complete toric varieties of Picard number 4. Furthermore, we also discuss about the classification of topological toric manifolds. For this, we use the relationship between $M$ and simplicial wedge operation of $K$.
  This is a joint work with Suyoung Choi.
   
• 박선정 Seonjeong Park (NIMS) Origami templates for simple polytopes
  An origami template is a collection of Delzant polytopes with some additional gluing data encoded by a template graph. In this talk, we define a smooth $\mathbb{Z}^n$-coloring on a simple polytope, and then we discuss the existence of an origami template for a given simple polytope with smooth $\mathbb{Z}^n$-coloring.
   
• 김연진 Younjin Kim (KAIST) On the Erdos-Ko-Rado  Theorem and the Bollobas Theorem for t-intersecting families
  A family $\mathcal{F}$ of sets is t - intersecting if any two members of $\mathcal{F}$ have at least t common elements. In 1961, Erdos, Ko, and Rado proved that the maximum size of a t-intersecting family $\mathcal{F}\subset {{[n]}\choose {\leq k}}$ is $ \sum_{i=0}^{k-t}{{n-t} \choose {k-t-i}}$ if $n\geq n_0(k,t)$ for some $n_0(k,t)$. In 2014, Alon, Aydinian, and Huang considered families generalizing intersecting families, and gave a strengthening of this non-uniform EKR theorem when $t=1$. In this paper, we give a strengthening of this theorem by considering families generalizing t-intersecting families for all $t \geq 1$. In 2004, Talbot generalized Bollobas's Two Families Theorem to t-intersecting families. In this paper, we proved a slight generalization of Talbot's result by using the probabilistic method. This is joint work with Dong Yeap Kang and Jaehoon Kim.
   
• 정지윤 JiYoon Jung (NIMS) Descent pattern avoidance
  We extend the notion of consecutive pattern avoidance to considering sums over all permutations where each term is a product of weights depending on each consecutive pattern of a fixed length. We study the problem of finding the asymptotics of these sums. Our technique is to extend the spectral method of Ehrenborg, Kitaev and Perry. When the weight depends on the descent pattern we show how to find the equation determining the spectrum. We give two length $4$ applications, and we show that the error term in the asymptotic expression for a weighted pattern of length $3$ is the smallest possible.
   
• 박경숙 Kyoungsuk Park (Ajou Univ.) Permutation statistics and weak Bruhat order in permutation tableaux of type B
  Many important statistics of signed permutations are realized in the corresponding permutation tableaux or bare tableaux of type $B$: Alignments, crossings and inversions of signed permutations are realized in the corresponding permutation tableaux of type $B$, and the cycles of signed permutations are understood in the corresponding bare tableaux of type $B$. This leads us to relate the number of alignments and crossings with other statistics of signed permutations and also to characterize the covering relation in weak Bruhat order on Coxeter system of type $B$ in terms of permutation tableaux of type $B$.