KIAS Workshop on Combinatorics

KIAS Combinatorics Workshop Series

6th Workshop

Home > 6th Workshop

6th KIAS Combinatorics Workshop

Date: December 19-20 (Fri-Sat), 2014
Venue: KIAS, 5th fl. #1503
Invited Speakers

Seoungji Hong (홍성지) at Yonsei University
Jisu Jeong (정지수) at KAIST (student of Sang-il Oum)
Jang Soo Kim (김장수) at Sungkyunkwan University
Jon-Lark Kim (김종락) at Sogang University

Sang-Jin Lee (이상진) at Konkuk University
Soojoon Lee (이수준) at Kyung Hee University
Suil O (오수일) at Georgia State University

<Program>
[1st Day, December 19th]
13:55 ~ 14:00 Opening address
14:00 ~ 14:40 <Talk I> Jon-Lark Kim
Who invented Graeco-Latin squares?
14:50 ~ 15:30 <Talk II> Suil O
Spectral radius and fractional matchings in graphs
15:30 ~ 16:00 Coffee Break
16:00 ~ 16:30 <Talk III> Jisu Jeong
The discharging method
16:40 ~ 17:20 <Talk IV> Jang Soo Kim
Mathematics of Juggling
17:30 ~ 17:50 Problem Session
18:00 ~ Banquet

[2nd Day, December 20th]
~ 09:20 Breakfast
09:20 ~ 10:00 <Talk V> Sang-Jin Lee
Simple path lifting property of graph coverings
and embedding of right-angled Artin groups into braid groups
10:00 ~ 10:30 Coffee Break
10:30 ~ 11:10 <Talk VI> Soojoon Lee
Concentrated information of tripartite quantum states
11:20 ~ 12:00 <Talk VII> Seoungji Hong
Touchard's like identity and its application
Support
(1) Accommodation: We support accommodations for December 19th to speakers, students, and researchers who need support.

- For speakers, we support rooms at KIASTEL near KIAS.
- For students and researchers who need support, the lodging expenses will be reimbursed up to KRW 40,000.
For more information on accommodation facilities, please see Accommodation Page.

-12월 19일의 숙박에 대하여 지원이 필요하신 학생 및 참가자분들은 키아스 외부의 숙박시설을 이용하신 후, 숙박영수증, 통장사본, 학회참가동의서 (학생의 경우)를 제출하시면 숙박비를 최대 1인당 4만원으로 실비 정산하여 지급하여 드립니다. (구비서류 제출은 Workshop당일 직접 제출하시거나 또는 이메일(이찬용, globalch@kias.re.kr)로 제출가능합니다.)
-만일 2명이 함께 방을 이용하는 경우는 최대 8만원까지 실비로 지원하여 드립니다. 휘경동 코업레지던스나 베니키아 호텔의 2인 1실 시설을 추천합니다

(2) Meal: We provide all meals during the workshop to all participants.

<Abstract>

***Speaker: Jon-Lark Kim (김종락)
Title: Who invented Graeco-Latin squares?
Abstract: People believed for a long time that Euler was the first to find Graeco-Latin squares. However, it was announced in 2007 that Seok-Jeong Choi, Chosun's mathematician, found orthogonal Latin squares 61 years before Euler found them. In this talk, we review Choi's work on Latin squares and associated magic squares. We relate them to error-correcting codes. Finally we describe our recent result on the dimension of the space of magic squares over fields.

***Speaker: Suil O (오수일)
Title: Spectral radius and fractional matchings in graphs
Abstract: A {it fractional matching} of a graph $G$ is a function $f$ giving each edge a number between 0 and 1 so that $sum_{e in Gamma(v)} f(e) le 1$ for each $vin V(G)$, where $Gamma(v)$ is the set of edges incident to $v$. The {it fractional matching number} of $G$, written $af(G)$, is the maximum of $sum_{e in E(G)} f(e)$ over all fractional matchings $f$. Let $G$ be an $n$-vertex graph with minimum degree $d$, and let $lambda_1(G)$ be the largest eigenvalues of $G$. In this talk, we prove that if $lambda_1(G) < dsqrt{1+frac{2k}{n-k}}$, then $af(G) > FR{n-k}{2}$.

***Speaker: Jisu Jeong (정지수)
Title: The discharging method
Abstract: The discharging method is a powerful technique in combinatorics and graph theory. Roughly speaking, the method is used in the following way: one assigns charge to some parts (vertices and/or faces) of a hypothetical counterexample graph, and then applies a discharging procedure to move the charge around. By double counting the charge before and after the discharging procedure, a contradiction is obtained to show that a counterexample cannot exist.
The most famous application of discharging is the Four Color Theorem, which states that every planar graph is 4-colorable. The discharging method is widely known to be used for coloring problems, but it has also been used for many other topics such as graph decomposition, graph homomorphism, dominating set, covering, fixed parameter algorithm, combinatorial geometry, and so on. A graph is $(d_1,d_2)$-colorable if its vertex set can be partitioned into two sets $V_1,V_2$ so that the maximum degree of the graph induced by $V_i$ is at most $d_i$ for $iin{1,2}$. In this talk, we will show how the discharging method is used by proving the following statement: planar graphs with girth at least 5 are (1,10)-colorable.

***Speaker: Jang Soo Kim (김장수)
Title: Mathematics of Juggling
Abstract: Juggling is an act of throwing and catching balls. Assuming that every ball is thrown and caught at discrete beats, if we write the time (number of beats) during which each thrown ball is in the air, we get a "juggling sequence". For instance, the usual 3-ball cascade gives the juggling sequence 333...=3. Another examples of a juggling sequence are 515151...=51 and 441441441...=441. In this talk we will see how to determine whether a given sequence is a juggling sequence and how to find the number of balls needed for a given juggling sequence. We will also find the number of juggling sequences when there are restrictions on the number of balls and the height of thrown balls.
All the materials in this talks are well known. The purpose of this talk is to draw combinatorialists' attention to the fascinating mathematical aspects of juggling.

***Speaker: Sang-Jin Lee (이상진)
Title: Simple path lifting property of graph coverings and embedding of right-angled Artin groups into braid groups
Abstract: Let $Gamma$ be a finite graph with no loops and no multiple edges. The emph{right-angled Artin group} (RAAG) $G(Gamma)$ is defined by the presentation
$$bigllangle vin V(Gamma)mid v_iv_j=v_jv_i
mbox{if ${v_i,v_j}notin E(Gamma)$},bigrrangle,$$
where $V(Gamma)$ and $E(Gamma)$ denote the sets of vertices and edges of $Gamma$. Recently, Sang-hyun Kim and Thomas Koberda showed that for an arbitrary graph $Gamma$ there exists a tree $T$ such that $G(Gamma)$ admits a quasi-isometric embedding into $G(T)$. As a corollary, $G(Gamma)$ admits a quasi-isometric embedding into a braid group. In Kim-Koberda construction, the number of vertices of the tree, $|V(T)|$, is bounded above by a double-exponential function in $|V(Gamma)|$. In the talk, we propose a simpler construction with $|V(T)|le (|V(Gamma)|+1)!$ by using simple path lifting property of graph coverings. This is a jointwork with Eon-Kyung Lee.

***Speaker: Soojoon Lee (이수준)
Title: Concentrated information of tripartite quantum states
Abstract: We introduce the concentrated information of tripartite quantum states. For three parties Alice, Bob and Charlie, it is defined as the maximal mutual information achievable between Alice and Charlie via local operations and classical communication performed by Charlie and Bob. The gap between classical and quantum concentrated information is shown to be an operational figure of merit for a state merging protocol involving shared mixed states and no distributed entanglement. We derive upper and lower bounds on the concentrated information, and obtain a closed expression for arbitrary pure tripartite states in the asymptotic setting. In this situation, one-way classical communication is shown to be sufficient for optimal information concentration. (Joint work with Alexander Streltsov and Gerardo Adesso.)
***Speaker: Seoungji Hong (홍성지)
Title: Touchard's like identity and its application
Abstract: Touchard's identity on Catalan numbers can be generalized on the numbers in Catalan family. We study congruence of modulo identities as its application