2010 Combinatorics Workshop

The 7th, “2010 Combinatorics Workshop” will be held at Yeungnam University on August 20-21.

If you want to participate, please write a registration form at the bottom of this mail and email to ysookwon@ynu.ac.kr until August 6. In particular, if you want to give a contributed talk, please submit the title and the abstract of your talk when you send a registration form to ysookwon@ynu.ac.kr. (The program will consist of 30-minute talks by invited speakers, and 20 minute contributed talks)

The invited speakers and organizers of this workshop are the following:

Invited speakers

  • Jin Ho Kwak (POSTECH)
  • Sang-il Oum (KAIST)
  • Soojin Cho (Ajou University)
  • Gi-Sang Cheon (SungKyunKwan University)
  • Mitsugu Hirasaka (Pusan National University)

Organizers

  • Dongsu Kim (KAIST)
  • Seung Kyung Park (Yonsei University)
  • Gi-Sang Cheon (SungKyunKwan University)
  • Jaeun Lee (Yeungnam University)

Venue

319, Department of Mathematics, Science Building no. 1, Yeungnam University

Program

August 20, 2010 (Friday)

Chair: Moo Young Sohn

  • 14:00–14:30 Sang-il Oum (KAIST): Hyperbolic surface subgroups of one-ended doubles of free groups
  • 14:35–14:55 Hyun Kwang Kim (POSTECH): Polytope numbers
  • 14:55–15:10 Coffee Break

Chair: Gi-Sang Cheon

  • 15:10–15:30 Mark Siggers (Kyungbook National University): Intersecting and Union Families of Sets
  • 15:35–15:55 Dan Drake (KAIST): A bijection from weighted Dyck paths to Schroeder paths, little and big
  • 15:55–16:10 Coffee Break

Chair: Dongseok Kim

  • 16:10–16:30 Hana Kim (Sungkyunkwan University): Combinatorial interpretations for k-consistent Riordan arrays
  • 16:35–16:55 Boram Park (Seoul National University): The competition numbers of circulant graphs
  • 16:55–17:10 Coffee Break

Chair: Young Soo Kwon

  • 17:10–17:30 Wonjin Park (Seoul National University): List dynamic coloring of planar graph
  • 17:35–17:55 Joonkyung Lee (Korea Military Academy): Rank-width of Random Graphs
  • 18:00–18:10 Conference Photo
  • 18:30–20:30 Banquet

August 21, 2010 (Saturday)

Chair: Suh-Ryung Kim

  • 09:30–10:00 Soojin Cho (Ajou University): Schur P-functions
  • 10:05–10:35 Mitsugu Hirasaka (Pusan National University): Equitable partitions in a balanced coherent configuration
  • 10:35–10:50 Coffee Break

Chair: Jack Koolen

  • 10:50–11:10 Lee-Chae Jang (Konkuk University): Some properties of q-Bernstein polynomials
  • 11:15–11:35 Sangwook Kim (KAIST): Topology of diagonal arrangements
  • 11:40–12:00 Kyoung-Suk Park (Ajou University): Combinatorics of permutation tableaux
  • 12:00–13:00 Lunch

Abstracts

Sang-il Oum (KAIST)

Title: Hyperbolic surface subgroups of one-ended doubles of free groups
Abstract: Gromov asked whether every one-ended word-hyperbolic group contains a hyperbolic surface group. We prove that every one-ended double of a free group has a hyperbolic surface subgroup if (1) the free group has rank two, or (2) every generator is used the same number of times in the amalgamating words. To prove this, we formulate a stronger statement on Whitehead graphs and prove its specialization by combinatorial induction for (1) and the characterization of perfect matching polytopes by Edmonds for (2).

This is joint work with Sang-hyun Kim.

Hyun Kwang Kim (POSTECH)

Title: Polytope numbers
Abstract: We present recent developments in the theory of polytope numbers.

Mark Siggers (Kyungbook National University)

Title: Intersecting and Union Families of Sets
Abstract: We present some Erdos-Ko-Rado type results about the maximum size of set families satisfying intersection conditions (of the family and their complement). We consider a weighted version of the problem, and the case in which every set in the family has the same size.

In particular we find the maximum size of a k-uniform family of subsets of [n] such that every r sets intersect, and every s sets in the complement intersect. We complement this with stability results, show that the maximum can only be achieved by families where at least one of the intersection conditions is obtained ‘trivially’.

This is joint work with Norihide Toushige.

Dan Drake (KAIST)

Title: A bijection from weighted Dyck paths to Schroeder paths, little and big
Abstract: In previous work, Jang Soo KIM and I showed that the number of Dyck paths in which downsteps at even height have weight 2 is the same as the number of little Schroeder paths. I will show a bijective proof of this that also shows that Dyck paths in which downsteps at odd height are equinumerous with big Schroeder paths.

Hana Kim (Sungkyunkwan University)

Title: Combinatorial interpretations for k-consistent Riordan arrays
Abstract: A Riordan array is said to be consistent if its A-sequence and Z-sequence are identical. As continuation of the previous work, we give combinatorial interpretations for the consistent Riordan arrays in terms of Schröder paths, Motzkin paths, ordered trees, and integer partitions. Further, we extend the consistent Riordan array to a k-consistent Riordan array.

Boram Park (Seoul National University)

Title: The competition numbers of circulant graphs
Abstract: The competition graph of a digraph D is a graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if there exists a vertex v in D such that (x, v) and (y, v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of a graph G is defined to be the smallest number of such isolated vertices. Characterizing a graph by its competition number has been one of important research problems in the study of competition graphs. Opsut conjectured that the competition number of a locally cobipartite graph is at most 2. It has been open for more than 25 years even if partial results had been obtained.

In this paper, we focus on the competition number of a circulant graph which is locally cobipartite. We show that certain circulant graphs including the complement of cycles still satisfy Opsut’s conjecture.

Wonjin Park (Seoul National University)

Title: List dynamic coloring of planar graph
Abstract: Dynamic coloring of a graph G is a proper coloring of G in which each vertex neighborhood of size at least 2 receives at least two distinct colors. The list dynamic chromatic number of G is the least k such that for any assignment of k-element lists to the vertices of G, there is a dynamic coloring of G where the color on each vertex is chosen from its list. We study list dynamic chromatic number of planar graphs. This is joint work with Seog-Jin Kim.

Joonkyung Lee (Korea Military Academy)

Title: Rank-width of Random Graphs
Abstract: Rank-width of a graph G, denoted by rw(G) is a graph width parameter introduced by Oum and Seymour(2006).

We investigate the asymptotic behavior of rank-width of a random graph G(n, p), which is a graph on n vertices such that two vertices are adjacent with the probability p independently at random. This model of random graphs was introduced by Erdős and Rényi (1960).

Using technical inequalities concerning the rank of random matrices, we show that asymptotically almost surely

(i) if p ∈ (0, 1) is a constant then rw(G(n, p)) = ⌈n/3⌉ − O(1),
(ii) if 1/n ≪ p ≤ 1/2, then rw(G(n, p)) = ⌈n/3⌉ − o(n),
(iii) if p = c/n and c > 1 then rw(G(n, p)) ≥ rn for some r = r(c), and
(iv) if p = c/n and c < 1 then rw(G(n, p)) ≤ 2.

Thus, it is shown that G(n, p) has the sharp threshold p(n) = 1/n with respect to having linear rank-width. This is joint work with Choongbum Lee and Sang-il Oum.

Soojin Cho (Ajou University)

Title: Schur P-functions
Abstract: Schur Q (and P)-functions were introduced by Schur in 1911 in relation to the projective representation of the symmetric group. We introduce well-known combinatorial results on Schur P-functions and give a new description of the structural constant (shifted Littlewood-Richardson coefficient) in terms of words.

Mitsugu Hirasaka (Pusan National University)

Title: Equitable partitions in a balanced coherent configuration
Abstract: Let (Ω,R) be a coherent configuration. We say that (Ω,R) is balanced if the number of elements of R in the cartesian product of any two fibers is constant. In this talk we consider equitable partitions of a homogeneous component of (Ω,R) and characterize them if (Ω,R) is balanced and the size of a fiber is a prime.

Lee-Chae Jang (Konkuk University)

Title: Some properties of q-Bernstein polynomials
Abstract: In the present paper, we propose the modified q-Bernstein polynomials of degree n, which are different q-Bernstein polynomials of Phillips. From these the modified q-Bernstein polynomials of degree n, we derive some interesting recurrence formulae for the modified q-Bernstein polynomials.

Sangwook Kim (KAIST)

Title: Topology of diagonal arrangements
Abstract: We show that if a simplicial complex is shellable, then the singularity link of the corresponding diagonal arrangement is homotopy equivalent to a wedge of spheres. Also, we give some examples of diagonal arrangements whose complements are K(π, 1), coming from rank 3 matroids.

Kyoung-Suk Park (Ajou University)

Title: Combinatorics of permutation tableaux
Abstract: We study some combinatorial properties of permutation tableaux; review known results and improve some of them. Permutation tableaux are in bijection with permutations, and their structure is more transparent than the structure of permutations. Thus, permutation tableaux are useful in the understanding of permutations. There is a well-known bijection between permutation tableaux and permutations; and we define a simple algorithm to find the corresponding permutation tableau of a given permutation under this bijection. There are several known bijections on the set of permutation tableaux showing that certain statistics have the same distribution. We consider a new bijection showing that alignments and crossings of certain types have the same distribution on permutation tableaux.

If you have any questions, please email to ysookwon@ynu.ac.kr and then we will reply. And please forward this email to anyone who might be interested. Thank you very much. Best wishes, Jaeun Lee, Young Soo Kwon

P.S: We arrange two accommodations: Guest room in Yeungnam University(35,000 Won per one night) and Yongam Well-being Spa Hotel(55,000 Won per one night) which is 10 minutes distance from our university by car. We will give more informations later. We plan to support the accommodation of graduate students who registered until the deadline.

7회째를 맞는 2010 조합론 학술대회가 8월 20일-21일(금,토)에 영남대학교에서 개최됩니다. 아무쪼록 관련분야의 많은 분들께서 참석하셔서 학문적 교류를 할 수 있었으면 좋겠습니다. 참여를 원하시는 분은 아래에 있는 2010년 조합론 학술대회 참가 신청서를 작성하셔서 8월6일(금)까지 ysookwon@ynu.ac.kr 로 회신주시기 바랍니다. 특히 학회에서 발표하시길 원하시는 분은 제목과 발표초록도 함께 보내주시면 고맙겠습니다. (초청강연자들은 30분 발표, 일반강연자들은 20분 발표시간을 가지는 것으로 현재 생각하고 있습니다.) 참고로, 금번 조합론 학술대회의 초청강사 및 운영위원의 명단은 다음과 같습니다.

초청강사

  • 곽진호 교수님 (포항공대)
  • 엄상일 교수님 (카이스트)
  • 조수진 교수님 (아주대학교)
  • 천기상 교수님 (성균관대학교)
  • 히라사카 미쯔꾸 교수님 (부산대학교)

운영위원

  • 김동수 교수님 (KAIST 수학과)
  • 박승경 교수님 (연세대학교 수학과)
  • 천기상 교수님 (성균관대학교 수학과)
  • 이재운 교수님 (영남대학교 수학과)

기타 궁금하신 점이 있으시면 ysookwon@ynu.ac.kr 로 메일을 주시면 곧 답변 드리겠습니다. 주변에 관심있는 분들께도 알려주셔서 참석을 권해주시길 바랍니다. 감사합니다. 영남대 이재운, 권영수 드림

추신: 저희들이 현재 생각하고 있는 숙박시설은 영남대학교 내의 게스트룸(하루 사용료 35000원)과 학교에서 10분 거리에 있는 용암온천호텔(하루 사용료 55000원) 두 곳 입니다. 자세한 사항은 추후 연락드리도록 하겠습니다. 참고로, 기간 내에 등록한 대학원생들의 1박 숙박비를 지원할 예정입니다. 많은 참여 바랍니다.

2010년 조합론 학술대회 참가 신청서 (Registration form)

  • 이름 (Last name, First name):
  • 소속 (Institution):
  • 숙박유무 (Do you need an accomodation on August 20?):
  • 발표유무 (Do you want to give a contributed talk?) :

If you want to give a talk, please answer the following.

  • 발표논문제목 (Title of your talk):
  • 발표논문요약 (Abstract of your talk):