KIAS Combinatorics Workshop Series |
2nd Workshop | Home > 2nd Workshop |
The 2nd KIAS Combinatorics Workshop will be held at KIAS on December 20-21, 2013.
- Date: December 20 - 21 (Fri-Sat), 2013
- Venue: Room 1503, KIAS
- Invited Speakers
Ilkyoo Choi (UIUC)
Kyomin Jung (Seoul National University)
Eun Jung Kim (LAMSADE, CNRS)
Choongbum Lee (MIT)
Seungkyung Park (Yonsei University)
Heesung Shin (Inha University)
- Support
Accommodation: We provide accommodations to participants, but rooms are available on a first come, first served basis. Priority will be given to students. (Accommodation Facilities)
Meal: We provide the dinner on December 20th and the breakfast on December 21st to all participants.
- Schedule
[1st Day, December 20th]
14:00 ~ 14:10 Opening address
14:10 ~ 15:00 <Talk I> Seungkyung Park
"Generalizing lattice paths and their enumeration"
15:20 ~ 16:10 <Talk II> Heesung Shin
"Eulerian polynomials via continued fractions - part 2"
Coffee Break
16:40 ~ 17:30 <Talk III> Kyomin Jung
"Tipping point analysis and influence maximization in social networks"
17:50 ~ Banquet
[2nd Day, December 21st]
~ 09:20 Breakfast
09:20 ~ 10:10 <Talk IV> Choongbum Lee
"Resilience of random graphs"
Coffee Break
10:40 ~ 11:30 <Talk V> Ilkyoo Choi
"3-coloring triangle-free planar graphs with a precolored 9-cycle"
11:40 ~ 12:30 <Talk VI> Eun Jung Kim
"Notable ideas for kernelization on sparse graphs"
Abstracts
<Talk I> Seungkyung Park
"Generalizing lattice paths and their enumeration"
I will survey generalities of lattice paths enumeration first. Then several attempts to generalizing lattice paths will be discussed. And I will finish the talk by showing recent progresses and results of generalizations of lattice paths.
<Talk II> Heesung Shin
"Eulerian polynomials via continued fractions - part 2"
Using continued fraction expansion, it is shown that the sequence of coefficients of Eulerian polynomial is symmetric and unimodal. Recently, Blanco and Petersen (arXiv:1206.0803v2) conjectured a $q$-analogue of Eulerian polynomial as an expansion formula for inversions and excedances in the symmetric group. In this talk, we prove this conjecture.
<Talk III> Kyomin Jung
"Tipping point analysis and influence maximization in social networks"
Diffusion of information, rumors or epidemics via various social networks has been extensively studied for decades. In particular, Kempe, Kleinberg, and Tardos (KDD '03) proposed the general threshold model, a generalization of many mathematical models for diffusion on networks which is based on utility maximization of individuals in game theoretic consideration. Despite its importance, the analysis under the threshold model, however, has concentrated on special cases such as the submodular influence (by Mossel-Roch (STOC '07)), homogeneous thresholds (by Whitney(Phys. Rev. E. '10)), and locally tree-like networks (by Watts(PNAS '02)). We first consider the general threshold model with arbitrary threshold distribution on arbitrary networks. We prove that only if (essentially) all nodes have degrees omega(log n), the final cascade size is highly concentrated around its mean with high probability for a large class of general threshold models including the linear threshold model, and the Katz-Shapiro pricing model. We also prove that in those cases, somewhat surprisingly, the expectation of the cascade size is asymptotically independent of the network structure if initial adopters are chosen by public advertisements, and provide a formula to compute the cascade size. Our formula allows us to compute when a phase transition for a large spreading (a tipping point) happens. We then provide a novel algorithm for influence maximization that integrates a new message passing based influence ranking and influence estimation methods in the independent cascade model.
<Talk IV> Choongbum Lee
"Resilience of random graphs"
Joint work with Michael Krivelevich and Benny Sudakov
<Talk V> Ilkyoo Choi
"3-coloring triangle-free planar graphs with a precolored 9-cycle"
We are interested in characterizing when a $3$-coloring of a cycle in a $3$-colorable planar graph does not extend to a $3$-coloring of the entire graph. Gr"otzsch's Theorem states that a triangle-free planar graph $G$ is $3$-colorable. Moreover, every $3$-coloring of a $4$-cycle or a $5$-cycle in $G$ extends to all of $G$. Given a $3$-coloring of a cycle $C$ of length at most $8$ in a triangle-free planar graph, it is characterized when the $3$-coloring extends to the entire graph. We extend this result to cycles of length $9$. Namely, we characterize all situations where a $3$-coloring of a cycle of length $9$ in a triangle-free planar graph does not extend to a $3$-coloring of the whole graph.
<Talk VI> Eun Jung Kim
"Notable ideas for kernelization on sparse graphs"
A closely related concept is that of kernelization. A kernelization algorithm, or just kernel, for a parameterized problem $Pi$ takes an instance $(x, k)$ of the problem and, in time polynomial in $|x| + k$, outputs an instance $(x',k')$ such that $|x'|,k'leq g(k)$ for some function $g$, and $(x,k)in Pi$ if and only if $(x',k')in Pi$. The function $g$ is called the size of the kernel and may be viewed as a measure of the “compressibility” of a problem using polynomial-time preprocessing rules. It is a folklore result that a decidable problem is in FPT if and only if it has a kernelization algorithm. However, the kernel that one obtains in this way is typically of size at least exponential in the parameter. A natural problem in this context is to find polynomial or linear kernels for problems that are in FPT.
During the last decade, a plethora of results emerged on linear kernels for graph-theoretic problems restricted to {sl sparse} graph classes. A celebrated result by Alber emph{et al}. for {sc Dominating Set} on planar graphs prompted an explosion of research papers on linear kernels on planar graphs. Guo and Niedermeier designed a general framework and showed that problems that satisfy a certain ``distance property'' have linear kernels on planar graphs. Bodlaender emph{et al}. provided a meta-theorem for problems to have a linear kernel on graphs of bounded genus. Fomin emph{et al}. extended these results for bidimensional problems on $H$-minor-free and apex-minor-free graphs. Recently, Kim emph{et al}. further pushed the boundary of meta-kernelization to include $H$-topological-minor-free graphs.
In the talk, we shall trace the trail of ideas for kernelization on sparse graphs after warming up with a minimal set of background notions to appreciate the progress.