Schedule

• Program Booklet (다운로드)

Monday, August 18, 2025

Time	Speaker	Title / Event
13:30-13:50	Registration
13:50-14:00	Welcome remarks
14:00-15:30    CHAIR: Sang-il Oum 엄상일 (IBS)
14:00-15:00	Eun Jung Kim 김은정 KAIST & IBS DIMAG & CNRS	Algorithm and MSO logic on graphs with tree-like structure [IS] A finite-state automaton is a computing machine ("algorithm") of primitive form, which scans a given string over a finite alphabet, e.g. a string consisting of 0's and 1's, and decides if the given string is in some language. It is primitive in the sense that the machine does not have a memory, and the machine keeps track of the inner working of the algorithm by having a "state", out of a finite number of possible states, which is updated according to a hard-wired rule as the machine reads the symbols on the input string one by one. A set of strings ("language") recognized by a finite automaton is known as a regular language. It is well-known that a regular language is precisely described by a homomorphism from the set of all strings to a finite semigroup. A less known but nonetheless important is that a language is regular if and only it is defined by so called Monadic Second Order Logic (Büchi-Elgot-Trakhtenbrot 1960), MSO logic in short. As a consequence, a language that can be defined using MSO logic admits an efficient algorithm for membership test, marking a regular language precisely as a language in which logical, algebraic and algorithmic behavior squarely meet. And these nice characterizations generalize to labelled trees, which extends the path-like shape inherent in strings (Thatcher and Wright, 1968). Courcelle's theorem (Courcelle 1990, Courcelle-Makowski-Rotices 2000) radically broadened the applications of Büchi-Elgot-Trakhtenbrot theorem on the equivalence of "recognizability and definability" on strings. Many fundamental graph problems can be expressed using MSO logic. And many such problems can be efficiently solved via so-called dynamic programming algorithms when the input graph is tree-like, e.g. has constant treewidth or constant cliquewidth. Courcelle's theorem revealed that the availability of dynamic programming algorithms for those problems is not a coincidence by showing that any MSO-definable graph problem has a nice algebraic property. This in turn leads to a meta-algorithm, which is a finite-state (tree) automaton in essence. Whether the opposite implication holds on graph with tree-like structures, thus allowing a nice characterization akin to those on strings and labelled trees, was asked by Courcelle himself (1990). The converse statement of Courcelle's theorem turns out to hold. It is proved by Bojańczyk and Pilipczuk (2016) that if such a nice algebraic property holds for a graph property, the property admits a logical description by MSO logic on graphs of bounded treewidth. As Courcelle's theorem holds on graphs of bounded cliquewidth as well as on matroids of bounded branchwidth when representable over a finite field, it is conjectured that "recognizability equals definability" on these more general structures. In this talk, we overview how algorithms design is intrinsically intertwined with algebraic and logical aspects of problems on graphs with tree-like structure. We also give a brief overview on essential, powerful tools for tackling these conjectures.
15:00-15:30	Yongho Shin 신용호 University of Wrocław	Learning-augmented online bipartite fractional matching [CT] Authors: Davin Choo, Billy Jin, Yongho Shin Online bipartite matching is a fundamental problem in online optimization, extensively studied both in its integral and fractional forms due to its theoretical significance and practical applications, such as online advertising and resource allocation. Motivated by recent progress in learning-augmented algorithms, we study online bipartite fractional matching when the algorithm is given advice in the form of a suggested matching in each iteration. We develop algorithms for both the vertex-weighted and unweighted variants that provably dominate the naive "coin flip" strategy of randomly choosing between the advice-following and advice-free algorithms. Moreover, our algorithm for the vertex-weighted setting extends to the AdWords problem under the small bids assumption, yielding a significant improvement over the seminal work of Mahdian, Nazerzadeh, and Saberi (EC 2007, TALG 2012). Complementing our positive results, we establish a hardness bound on the robustness-consistency tradeoff that is attainable by any algorithm. We empirically validate our algorithms through experiments on synthetic and real-world data.
15:30-16:00	Coffee Break
16:00-18:00    CHAIR: Hyobeen Kim 김효빈 (Chonnam National University)
16:00-16:30	Dabeen Lee 이다빈 KAIST	Combinatorial optimization through the lens of boolean polynomials and binary matroids [CT] Authors: Ahmad Abdi, Dabeen Lee Combinatorial optimization is the problem of choosing an optimal combination of items from a discrete set of elements. One of the most pressing challenges in modern applications is to develop efficient methodologies for nonlinear combinatorial optimization. In this talk, we introduce a novel approach to solving nonlinear problems through the lens of boolean polynomials and binary matroids. Discovering previously unrecognized connections to binary matroids, we develop a new framework for linearizing the equivalent boolean polynomial optimization formulation. We provide a simple characterization for the convex hull of binary solutions to the linearization when the underlying binary matroid is a projective geometry, which contains all binary matroids over the same ground set as restrictions. We also show that if the matroid satisfies the sums of circuits property, then the convex hull coincides with the associated cocycle polytope. Moreover, taking the signs of the objective coefficients into account, we extend the sums of circuits property to idealness of binary clutters via signed binary matroids. To go further beyond the sums of circuits property, we present a sum-of-squares hierarchy that admits efficient semidefinite relaxations. Lastly, we explain extensions to discrete optimization over any finite fields.
16:30-17:00	Seonghyuk Im 임성혁 KAIST & IBS ECOPRO	Random perturbation of dense graphs [CT] Authors: Jie Han, Seonghyuk Im, Bin Wang, Junxue Zhang A randomly perturbed graph is formed by taking the union of a deterministic graph G and a binomial random graph G(n,p) on the same vertex set. Balogh, Treglown, and Wagner showed that for a fixed graph F, if p ≫ n-1/m1(F) and an n-vertex graph G has the minimum degree δ(n), then the graph G ∪ G(n,p) contains an F-factor with high probability. We extend their result by proving that if F is not a forest, then it suffices to assume e(G) = Ω(n2), relaxing the minimum degree condition. Additionally, we establish analogous results for powers of Hamilton cycles and for families of graphs with bounded maximum degree in a randomly perturbed graph.
17:00-17:30	Hyunwoo Lee 이현우 KAIST & IBS ECOPRO	On a Ramsey-Turán variant of Roth's theorem [CT] Authors: Matija Bucić, Micha Christoph, Jaehoon Kim, Hyunwoo Lee, Varun Sivashankar A classical theorem of Roth states that the maximum size of a solution-free set of a homogeneous linear equation L in Fp is o(p) if and only if the sum of the coefficients of L is 0. In this paper, we prove a Ramsey-Turán variant of Roth's theorem, with respect to a natural notion of "structured" sets introduced by Erdős and Sárközy in the 1970's. Namely, we show that the following statements are equivalent: (a) Every solution-free set A of L in Fp with α(CayP̅p(A))=o(p) has size o(p). (b) There exists a non-empty subset of coefficients of L with zero sum.
17:30-18:00	Ingyu Baek 백인규 Yonsei University	Counting loose odd cycles in dense hypergraphs [CT] Authors: Ingyu Baek, Joonkyung Lee Sidorenko's conjecture states that, for all bipartite graphs H, quasirandom graphs asymptotically minimises the number of copies of H taken over all graphs with fixed density p. Although this conjecture has remained open for decades, its natural hypergraph generalisa-tion is known to be false since Sidorenko's own work in the 1990s, which shows that, for a 3-uniform loose 3-cycle C3(3), there exists a 3-uniform hypergraph G with edge density p such that t(C3(3),G) < p3, where t(H,G) denotes the homomorphism density of H in G. In 2020, with interesting applications in additive combinatorics, Fox, Sah, Sawhney, Stoner, and Zhao showed that the inequality t(C3(3),G) ≥ p4 holds and furthermore, the exponent 4 cannot be improved by a smaller number. The tightness of the exponent is demonstrated by Behrend's 3-AP-free set construction, which necessarily requires p tending to zero as |V(G)| tends to infinity. One may then ask whether the tightness of the exponent in the Fox-Sah-Sawhney-Stoner-Zhao inequality can be evidenced by an arbitrary 'dense' hypergraph G, e.g., p=1/2. An analogous question for graphs was recently asked by Blekherman, Raymond, Razborov, and Wei. We answer this question in the negative, by obtaining nontrivial lower-order terms in the lower bound for t(C3(3),G) beyond p4. Our method also generalises to longer loose odd cycles, which can be seen as a progress towards a recent question of Spiro and Nie.
19:00-21:00	Dinner (고반식당 대전엑스포점)

Tuesday, August 19, 2025

Time	Speaker	Title / Event
09:30-10:30    CHAIR: Seunghyun Seo 서승현 (Kangwon National University)
09:30-10:30	Dongsu Kim 김동수 KAIST	Combinatorics of orthogonal polynomials in the q-Askey scheme [IS] Combinatorics of orthogonal polynomials has been studied from 1980's. There are various combinatorial interpretations for important orthogonal polynomials and their properties. Orthogonal polynomials in q-Askey scheme have q-factorials in their terms and coefficients. A nice combinatorial model to handle q-factorials has been introduced in Lecture hall graphs and the Askey scheme, by S. Corteel, B. Jonnadula, J. Keating, J. S. Kim, arXiv:2311.12761v2. This talk is a history of the combinatorics of orthogonal polynomials up to the above paper.
10:30-11:00	Coffee Break
11:00-12:00    CHAIR: Joonkyung Lee 이준경 (Yonsei University)
11:00-11:30	Heesung Shin 신희성 Inha University	Combinatorial Bijections in Permutations, Trees, and Paths [CT] This presentation traces my two-decade journey exploring combinatorial bijections in enumerative combinatorics. My research establishes strong connections and provides combinatorial interpretations for algebraic identities between permutations, trees (rooted, ordered, labeled, p-ary), and lattice paths (Dyck, Schröder, Delannoy, F-paths). Key contributions include bijections for pattern-avoiding inversion sequences and permutations, refined enumerations of trees based on various properties like indegree sequences and maximal decreasing subtrees, and analysis of lattice paths with avoidance conditions. The work also covers bijections for parking functions and involutions on partitions for hook length symmetry. This talk emphasizes the power of bijections in solving problems and revealing new connections in combinatorial theory.
11:30-12:00	Younghan Yoon 윤영한 Ajou University	On the graph a-numbers [CT] Authors: Suyoung Choi, Younghan Yoon We introduce combinatorial invariants, called a-numbers, of finite simple graphs, motivated by toric topology. These invariants exactly correspond to the Betti numbers of the canonical real toric variety associated with graphs. In this talk, we explore two fundamental questions about the behavior of the a-numbers: 1. Are they monotone increasing under edge inclusion? 2. Do they form a unimodal sequence?
12:00-13:30	Lunch Break
13:30-15:30    CHAIR: Hayan Nam 남하얀 (Konkuk University)
13:30-14:30	Ae Ja Yee 이애자 Pennsylvania State University	Partition statistics and the Littlewood decomposition [IS] (in honor of Professor Dongsu Kim's retirement) Integer partitions carry various interesting statistics. Of those, the most loved and studied statistics are Dyson's rank and crank, which explain Ramanujan's mod 5, 7 and 11 partition congruences. In 1990, Garvan, Kim and Stanton found other cranks, which split the set of partitions into t equinumerous classes for t=5,7,11 and thus give a combinatorial account for the three congruences of Ramanujan. In their proof, the Littlewood decomposition of partitions into t-core and t-quotient partitions is an essential component. Since then, their cranks along with Dyson's rank and crank have been adopted to prove other partition congruences and refinements. In this talk, I will discuss the Littlewood decomposition from a partition theory point of view and present some recent results on various partition statistics arising from the Littlewood decomposition. This talk is based on joint work with Hyunsoo Cho, Byungchan Kim and Eunmi Kim.
14:30-15:00	Inseo Kim 김인서 Chungbuk National University	On toric Schubert varieties in flag varieties [CT] Authors: Inseo Kim, Eunjeong Lee Let G be a simple algebraic group over C, and let P be a parabolic subgroup of G. A flag variety G/P is a smooth projective homogeneous variety that admits an action of a maximal torus T of G, where T is contained in the parabolic subgroup P. Schubert varieties form an interesting family of T-invariant subvarieties of G/P indexed by elements of a certain coset of the Weyl group of G. Note that not every Schubert variety is toric with respect to the induced T-action. In this talk, we consider toric Schubert varieties in G/P when G is of type A.
15:00-15:30	Seonkyung Kim 김선경 Kangwon National University	The largest size of an (s,s+2)-core partition with even or odd parts only [CT] Authors: Hyoeun Cho, Seong hyeon Hwan, Seonkyung Kim, Hayan Nam Olsson and Stanton initiated the computation of the largest size of a simultaneous core partition. Since then, there have been various works on the largest size of a core partition. In particular, Nam and Yu computed the largest size of an (s,s+1)-core partition, where all the parts are of the same parity. In this paper, we evaluate the largest size of an (s,s+2)-core partition, where all the parts are of the same parity.
15:30-16:00	Coffee Break
16:00-18:00    CHAIR: Sangwook Kim 김상욱 (Chonnam National University)
16:00-17:00	Zhicong Lin Shandong University	Tree structures and combinatorics of bi-γ positivity [IS] Multiset Eulerian polynomials and 1/k-Eulerian polynomials are different generalizations of the classical Eulerian polynomials. I will talk about combinatorics of their bi-γ-positivity via tree structures.
17:00-17:30	Seunghun Lee 이승훈 IBS DIMAG	On the extension problem on the moment curve [CT] Authors: Seunghun Lee, Eran Nevo We show that for 2 ≤ d ≤ 4 every finite geometric simplicial complex Δ with vertices on the moment curve in Rd can be extended to a triangulation T of the cyclic polytope C where Δ T and C all have same vertex set. Further, for d ≥ 5 we construct complexes Δ for which no such triangulations T exist.
17:30-18:00	Seonghyeon Yu 유성현 Ajou University	Bier spheres and their full subcomplexes [CT] Authors: Suyoung Choi, Younghan Yoon, Seonghyeon Yu In 1992, Thomas Bier introduced a combinatorial construction that yields a large family of simplicial (m-2)-dimensional PL-spheres on 2m vertices. In algebraic topology, the full subcomplexes of a simplicial complex K often provide significant information about topological invariants of K or the topological space associated with K. In this talk, we will discuss full subcomplexes and the bigraded Betti numbers of Bier spheres.
18:00-	Conference Banquet at IBS

Wednesday, August 20, 2025

Time	Speaker	Title / Event
09:30-10:30    CHAIR: Young Soo Kwon 권영수 (Yeungnam University)
09:30-10:30	O-joung Kwon 권오정 Hanyang University & IBS DIMAG	On problems related to digraph width parameters [IS] Treewidth is a well-known graph parameter that plays an important role in Robertson and Seymour's graph minors project. Several width parameters inspired by treewidth have been introduced for digraphs, including directed treewidth, directed pathwidth, DAG-width, Kelly-width, cycle rank, DAG-depth, and so on. Compared to undirected width parameters, finding unavoidable structures for digraph width parameters turns out to be very difficult. Recently, we provided a collection of three obstruction families for cycle rank in terms of butterfly minors. In this talk, we present this result and related open problems. This is joint work with Meike Hatzel, Myounghwan Lee, and Sebastian Wiederrecht.
10:30-11:00	Coffee Break
11:00-12:30    CHAIR: Jongyook Park 박종육 (Kyungpook National University)
11:00-11:30	Myounghwan Lee 이명환 Hanyang University	Unavoidable butterfly minors in digraphs of large cycle rank [CT] Authors: Meike Hatzel, O-joung Kwon, Myounghwan Lee, Sebastian Wiederrecht Cycle rank is one of the depth parameters for digraphs introduced by Eggan in 1963. We show that there exists a function f:N→N such that every digraph of cycle rank at least f(k) contains a directed cycle chain, a directed ladder, or a directed tree chain of order k as a butterfly minor. Directed cycle chains and directed ladders are strongly connected digraphs that are obtained from an undirected path by splitting its edges or vertices in a specific way. A directed tree chain of order k is obtained from a directed path v1v2...v2k by adding the edge (v2ij,v2ij+2i-1) for every i∈{1,...,k} and j∈{1,...,2k-i}. We also investigate a new connection between cycle rank and a directed analogue of the weak coloring number of graphs.
11:30-12:00	Seokbeom Kim 김석범 KAIST & IBS DIMAG	Subtournaments of tournaments of large clique-width [CT] Authors: Seokbeom Kim, Taite LaGrange, Mathieu Rundström, Sophie Spirkl If a graph has large clique-width, what can we say about its induced subgraphs? From classical results on clique-width, it is not hard to deduce that the class of H-free graphs has bounded clique-width if and only if H is an induced subgraph of a four-vertex path. Here, a graph is H-free if it has no induced subgraph isomorphic to H. Motivated by this result, there have been studies on the clique-width of graphs excluding two or more graphs as induced subgraphs, as well as H-free graphs with additional structural properties. In this talk, we investigate an analogue of this question for tournaments, which are a special type of directed graph. Again, what can we say about subtournaments of a tournament with large (directed) clique-width? We present recent progress on this question along with some open problems.
12:00-12:30	Seog-Jin Kim 김석진 Konkuk University	The square of every subcubic planar graph without 4-cycles and 5-cycles is 7-choosable [CT] Authors: Ligang Jin, Yingli Kang, Seog-Jin Kim The square of a graph G, denoted G2, has the same vertex set as G and has an edge between two vertices if the distance between them in G is at most 2. Thomassen (2018) proved that χ(G2) ≤ 7 if G is a subcubic planar graph. A natural question is whether χt(G2) ≤ 7 or not if G is a subcubic planar graph. Recently, Kim and Lian (2024) proved that χl(G2) ≤ 7 if G is a subcubic planar graph of girth at least 6. In this paper, we prove that χl(G2) ≤ 7 if G is a subcubic planar graph without 4-cycles and 5-cycles, which improves the result of Kim and Lian.
12:30-13:30	Pizza Lunch