Discrete Mathematics Group

Dillon Mayhew, Courcelle's Theorem for hypergraphs
2020-01-28 16:30 - 17:30 (Asia/Seoul) | Room B232, IBS (기초과학연구원)
Courcelle’s Theorem is an influential meta-theorem published in 1990. It tells us that a property of graph can be tested in polynomial time, as long as the property can expressed in the monadic second-order logic of graphs, and as long as the input is restricted to a class of graphs with bounded tree-width. There are several properties that are NP-complete in general, but which can be expressed in monadic logic (3-colourability, Hamiltonicity…), so Courcelle’s Theorem implies that these difficult properties can be tested in polynomial time when the structural complexity of the input is limited.
Matroids can be considered as a special class of hypergraphs. Any finite set of vectors over a field leads to a matroid, and such a matroid is said to be representable over that field. Hlineny produced a matroid analogue of Courcelle’s Theorem for input classes with bounded branch-width that are representable over a finite field.
We have now identified the structural properties of hypergraph classes that allow a proof of Hliněný’s Theorem to go through. This means that we are able to extend his theorem to several other natural classes of matroids.
This talk will contain an introduction to matroids, monadic logic, and tree-automata.
This is joint work with Daryl Funk, Mike Newman, and Geoff Whittle.

Adam Zsolt Wagner, The largest projective cube-free subsets of $Z_{2^n}$
2020-01-20 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
What is the largest subset of $Z_{2^n}$ that doesn’t contain a projective d-cube? In the Boolean lattice, Sperner’s, Erdos’s, Kleitman’s and Samotij’s theorems state that families that do not contain many chains must have a very specific layered structure. We show that if instead of $Z_2^n$ we work in $Z_{2^n}$, analogous statements hold if one replaces the word k-chain by projective cube of dimension $2^{k-1}$. The largest d-cube-free subset of $Z_{2^n}$, if d is not a power of two, exhibits a much more interesting behaviour.
This is joint work with Jason Long.

Ben Lund, Furstenberg sets over finite fields
2020-01-15 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
An important family of incidence problems are discrete analogs of deep questions in geometric measure theory. Perhaps the most famous example of this is the finite field Kakeya conjecture, proved by Dvir in 2008. Dvir’s proof introduced the polynomial method to incidence geometry, which led to the solution to many long-standing problems in the area.
I will talk about a generalization of the Kakeya conjecture posed by Ellenberg, Oberlin, and Tao. A $(k,m)$-Furstenberg set S in $mathbb F_q^n$ has the property that, parallel to every affine $k$-plane V, there is a k-plane W such that $|W cap S| > m$. Using sophisticated ideas from algebraic geometry, Ellenberg and Erman showed that if S is a $(k,m)$-Furstenberg set, then $|S| > c m^{n/k}$, for a constant c depending on n and k. In recent joint work with Manik Dhar and Zeev Dvir, we give simpler proofs of stronger bounds. For example, if $m>2^{n+7}q$, then $|S|=(1-o(1))mq^{n-k}$, which is tight up to the $o(1)$ term.

Sanjeeb Dash, Boolean decision rules via column generation
2020-01-14 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
In many applications of machine learning, interpretable or explainable models for binary classification, such as decision trees or decision lists, are preferred over potentially more accurate but less interpretable models such as random forests or support vector machines. In this talk, we consider boolean decision rule sets (equivalent to boolean functions in disjunctive normal form) as interpretable models for binary classification. We define the complexity of a rule set to be the number of rules (clauses) plus the number of conditions (literals) across all clauses, and assume that simpler or less complex models are more interpretable. We discuss an integer programming formulation for such models that trades off classification accuracy against rule simplicity, and obtain high-quality classifiers of this type using column generation techniques. Compared to some recent alternatives, our algorithm dominates the accuracy-simplicity trade-off in 8 out of 16 datasets, and also produced the winning entry in the 2018 FICO explainable machine learning challenge. When compared to rule learning methods designed for accuracy, our algorithm sometimes finds significantly simpler solutions that are no less accurate.

Jaiung Jun (전재웅), The Hall algebra of the category of matroids
2019-12-26 16:30 - 17:30 | Room 1401, Bldg. E6-1, KAIST
To an abelian category A satisfying certain finiteness conditions, one can associate an algebra H_A (the Hall algebra of A) which encodes the structures of the space of extensions between objects in A. For a non-additive setting, Dyckerhoff and Kapranov introduced the notion of proto-exact categories, as a non-additive generalization of an exact category, which is shown to suffice for the construction of an associative Hall algebra. In this talk, I will discuss the category of matroids in this perspective.

Attila Joó, Base partition for finitary-cofinitary matroid families
2019-12-19 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Let ${mathcal{M} = (M_i colon iin K)}$ be a finite or infinite family consisting of finitary and cofinitary matroids on a common ground set $E$.
We prove the following Cantor-Bernstein-type result: if $E$ can be covered by sets ${(B_i colon iin K)}$ which are bases in the corresponding matroids and there are also pairwise disjoint bases of the matroids $M_i$ then $E$ can be partitioned into bases with respect to $mathcal{M}$.

Hong Liu, A proof of Mader's conjecture on large clique subdivisions in $C_4$-free graphs
2019-12-12 16:30 - 17:30 | Room 1401, Bldg. E6-1, KAIST
Given any integers $s,tgeq 2$, we show there exists some $c=c(s,t)>0$ such that any $K_{s,t}$-free graph with average degree $d$ contains a subdivision of a clique with at least $cd^{frac{1}{2}frac{s}{s-1}}$ vertices. In particular, when $s=2$ this resolves in a strong sense the conjecture of Mader in 1999 that every $C_4$-free graph has a subdivision of a clique with order linear in the average degree of the original graph. In general, the widely conjectured asymptotic behaviour of the extremal density of $K_{s,t}$-free graphs suggests our result is tight up to the constant $c(s,t)$. This is joint work with Richard Montgomery.

Jakub Gajarský, First-order interpretations of bounded expansion classes
2019-12-10 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce classes of graphs with structurally bounded expansion, defined as first-order interpretations of classes of bounded expansion. As a first step towards their algorithmic treatment, we provide their characterization analogous to the characterization of classes of bounded expansion via low treedepth decompositions, replacing treedepth by its dense analogue called shrubdepth.

Frédéric Meunier, Topological bounds for graph representations over any field
2019-11-21 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Haviv (European Journal of Combinatorics, 2019) has recently proved that some topological lower bounds on the chromatic number of graphs are also lower bounds on their orthogonality dimension over $mathbb {R}$. We show that this holds actually for all known topological lower bounds and all fields. We also improve the topological bound he obtained for the minrank parameter over $mathbb {R}$ – an important graph invariant from coding theory – and show that this bound is actually valid for all fields as well. The notion of independent representation over a matroid is introduced and used in a general theorem having these results as corollaries. Related complexity results are also discussed.
This is joint work with Meysam Alishahi.

Ruth Luo, Induced Turán problems for hypergraphs
2019-11-19 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Let $F$ be a graph. We say that a hypergraph $mathcal H$ is an induced Berge $F$ if there exists a bijective mapping $f$ from the edges of $F$ to the hyperedges of $mathcal H$ such that for all $xy in E(F)$, $f(xy) cap V(F) = {x,y}$. In this talk, we show asymptotics for the maximum number of edges in $r$-uniform hypergraphs with no induced Berge $F$. In particular, this function is strongly related to the generalized Turán function $ex(n,K_r, F)$, i.e., the maximum number of cliques of size $r$ in $n$-vertex, $F$-free graphs. Joint work with Zoltan Füredi.

Tony Huynh, Stable sets in graphs with bounded odd cycle packing number
2019-11-12 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
It is a classic result that the maximum weight stable set problem is efficiently solvable for bipartite graphs. The recent bimodular algorithm of Artmann, Weismantel and Zenklusen shows that it is also efficiently solvable for graphs without two disjoint odd cycles. The complexity of the stable set problem for graphs without $k$ disjoint odd cycles is a long-standing open problem for all other values of $k$. We prove that under the additional assumption that the input graph is embedded in a surface of bounded genus, there is a polynomial-time algorithm for each fixed $k$. Moreover, we obtain polynomial-size extended formulations for the respective stable set polytopes.
To this end, we show that 2-sided odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed surface. This result may be of independent interest and extends a theorem of Kawarabayashi and Nakamoto asserting that odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed orientable surface.
Eventually, our findings allow us to reduce the original problem to the problem of finding a minimum-cost non-negative integer circulation of a certain homology class, which we prove to be efficiently solvable in our case.
This is joint work with Michele Conforti, Samuel Fiorini, Gwenaël Joret, and Stefan Weltge.

Combinatorial and Discrete Optimization (2019 KSIAM Annual Meeting)
2019-11-08 12:00 - 2019-11-09 19:00 | Venezia Hotel & Resort Yeosu, Yeosu, Korea (여수 베네치아 호텔)
Special Session @ 2019 KSIAM Annual Meeting
A special session on “Combinatorial and Discrete Optimization” at the 2019 KSIAM Annual Meeting is organized by Dabeen Lee. URL: https://www.ksiam.org/conference/84840fb6-87b0-4566-acc1-4802bde58fbd/welcome
Date
Nov 8, 2019 – Nov 9, 2019 Address: 61-13 Odongdo-ro, Sujeong-dong, Yeosu-si, Jeollanam-do (전남 여수시 오동도로 61-13)
Venue
Venezia Hotel & Resort Yeosu, Yeosu, Korea (여수 베네치아 호텔) Address: 61-13 Odongdo-ro, Sujeong-dong, Yeosu-si, Jeollanam-do (전남 여수시 오동도로 61-13)
Speakers

Hyung-Chan An (안형찬), Yonsei University
Tony Huynh, Monash University
Dong Yeap Kang (강동엽), KAIST / IBS Discrete Mathematics Group
Dabeen Lee (이다빈), IBS Discrete Mathematics Group
Kangbok Lee (이강복), POSTECH
Sang-il Oum (엄상일), IBS Discrete Mathematics Group / KAIST
Kedong Yan, Nanjing University of Science and Technology
Se-Young Yun (윤세영), KAIST

Schedules

Combinatorial and Discrete Optimization I: November 8, 2019 Friday, 14:20 – 15:40.

Kangbok Lee
Kedong Yan
Dabeen Lee
Se-young Yun

Combinatorial and Discrete Optimization II: November 9, 2019 Saturday, 10:00 – 11:20.

Hyung Chan An
Dong Yeap Kang
Tony Huynh
Sang-il Oum

Abstracts
Kangbok Lee (이강복), Bi-criteria scheduling

The bi-criteria scheduling problems that minimize the two most popular scheduling objectives, namely the makespan and the total completion time, are considered. Given a schedule, makespan, denoted as $C_max$, is the latest completion time of the jobs and the total completion time, denoted as $sum C_j$, is the sum of the completion times of the jobs. These two objectives have received a lot of attention in the literature because of their practical implications. Scheduling problems are somehow difficult to solve even for single criterion. On the other hand, when it comes to a bi-criteria problem, a balanced solution coordinating both objectives is indeed essential. In this paper, we consider bi-criteria scheduling problems on $m$ identical parallel machines where $m$ is 2, 3 and an arbitrary number, denoted as $P2 || (C_max,sum􏰂 C_j)$, $P3 || (C_max,􏰂sum C_j)$ and $P || (C_max,􏰂C_j)$, respectively. For each problem, we explore its inapproximability and develop an approximation algorithm with analysis of its worst performance.

Kedong Yan, Cliques for multi-term linearization of 0-1 multilinear program for boolean logical pattern generation

Logical Analysis of Data (LAD) is a combinatorial optimization-based machine learning method. A key stage of LAD is pattern generation, where useful knowledge in a training dataset of two types of, say, + and − data under analysis is discovered. LAD pattern generation can be cast as a 0-1 multilinear program (MP) with a single 0-1 multilinear constraint: $$(PG): maxlimits_{xin{0,1}^{2n}}f(x):=sum_{iin S^+}Pi_{jin J_i}(1-x_j)~~text{subject to}~~g(x):=sum_{iin S^-}Pi_{jin J_i}(1-x_j)=0$$

The unconstrained maximization of $f$ (without $g$) is straightforward, thus the main difficulty of globally maximizing $(PG)$ arises primarily from the presence of g and the interaction between $f$ and $g$. We dealt with the task of linearizing $g$. Namely, we employed a graph theoretic analysis of data to discover sufficient conditions among neighboring data and also neighboring groups of data for ‘compactly linearizing’ $g$ in terms of a small number of stronger valid inequalities, as compared to those that can be obtained via 0-1 linearization techniques from the literature. In an earlier work, we analyzed + and − data (that is, terms of $f$ and $g$ together) on a graph to develop a polyhedral overestimation scheme for $f$. Extending this line of research, this paper proposes a new graph representation of monomials in f in conjunction with terms in $g$ to more aggressively aggregate a set of terms/data through each maximal clique in the graph into yielding a stronger valid inequality. This is achieved by means of a new notion of ‘neighbors’ that allows us to join two data that are more than 1-Hamming distance away from each other by an edge in the graph. We show that new inequalities generalize and subsume those from the earlier paper. Furthermore, with using six benchmark data mining datasets, we demonstrate that new inequalities are superior to their predecessors in terms of a more efficient global maximization of $(PG)$; that is, for a more efficient analysis and classification of real-life datasets.

Dabeen Lee (이다빈), Joint Chance-constrained programs and the intersection of mixing sets through a submodularity lens
The intersection of mixing sets with common binary variables arise when modeling joint linear chance-constrained programs with random right-hand sides and finite sample space. In this talk, we first establish a strong and previously unrecognized connection of mixing sets to submodularity. This viewpoint enables us to unify and extend existing results on polyhedral structures of mixing sets. Then we study the intersection of mixing sets with common binary variables and also linking constraint lower bounding a linear function of the continuous variables. We propose a new class of valid inequalities and characterize when this new class along with the mixing inequalities are sufficient to describe the convex hull.
Se-Young Yun (윤세영), Optimal sampling and clustering algorithms in the stochastic block model

This paper investigates the design of joint adaptive sampling and clustering algorithms in the Stochastic Block Model (SBM). To extract hidden clusters from the data, such algorithms sample edges sequentially in an adaptive manner, and after gathering edge samples, return cluster estimates. We derive information-theoretical upper bounds on the cluster recovery rate. These bounds reveal the optimal sequential edge sampling strategy, and interestingly, the latter does not depend on the sampling budget, but only the parameters of the SBM. We devise a joint sampling and clustering algorithm matching the recovery rate upper bounds. The algorithm initially uses a fraction of the sampling budget to estimate the SBM parameters, and to learn the optimal sampling strategy. This strategy then guides the remaining sampling process, which confers the optimality of the algorithm.

Hyung-Chan An (안형찬), Constant-factor approximation algorithms for parity-constrained facility location problems

Facility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest, little is known on how the problem behaves in conjunction with parity constraints. This shortfall of understanding was rather disturbing when we consider the central role of parity in the field of combinatorics. In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of facilities and clients, the opening cost of each facility, and the parity requirement—$mathsf{odd}$, $mathsf{even}$, or $mathsf{unconstrained}$—of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement. Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a $T$-join on an auxiliary graph constructed by the algorithm. This graph does not satisfy the triangle inequality, but we show that a carefully chosen set of shortcutting operations leads to a cheap and sparse $T$-join. Finally, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound. At the end of this paper, we also present the first constant-factor approximation algorithm for the parity-constrained $k$-center problem, the bottleneck optimization variant.

Dong Yeap Kang (강동엽), On minimal highly connected spanning subgraphs in dense digraphs
In 1985, Mader showed that every $n(geq4k+3)$-vertex strongly $k$-connected digraph contains a spanning strongly $k$-connected subgraph with at most $2kn-2k^2$ edges, and the only extremal digraph is a complete bipartite digraph $DK_{k,n−k}$. Nevertheless, since the extremal graph is sparse, Bang-Jensen asked whether there exists g(k) such that every strongly $k$-connected $n$-vertex tournament contains a spanning strongly $k$-connected subgraph with $kn + g(k)$ edges, which is an “almost $k$-regular” subgraph.

Recently, the question of Bang-Jensen was answered in the affirmative with $g(k) = O(k^2log k)$, which is best possible up to logarithmic factor. In this talk, we discuss how to find minimal highly connected spanning subgraphs in dense digraphs as well as tournaments. In particular, we show that every highly connected dense digraph contains a spanning highly connected subgraph that is almost $k$-regular, which yields $g(k) = O(k^2)$ that is best possible for tournaments.

Tony Huynh, Stable sets in graphs with bounded odd cycle packing number

It is a classic result that the maximum weight stable set problem is efficiently solvable for bipartite graphs. The recent bimodular algorithm of Artmann, Weismantel and Zenklusen shows that it is also efficiently solvable for graphs without two disjoint odd cycles. The complexity of the stable set problem for graphs without $k$ disjoint odd cycles is a long-standing open problem for all other values of $k$. We prove that under the additional assumption that the input graph is embedded in a surface of bounded genus, there is a polynomial-time algorithm for each fixed $k$. Moreover, we obtain polynomial-size extended formulations for the respective stable set polytopes. To this end, we show that 2-sided odd cycles satisfy the Erdos-Posa property in graphs embedded in a fixed surface. This result may be of independent interest and extends a theorem of Kawarabayashi and Nakamoto asserting that odd cycles satisfy the Erdos-Posa property in graphs embedded in a fixed orientable surface Eventually, our findings allow us to reduce the original problem to the problem of finding a minimum-cost non-negative integer circulation of a certain homology class, which we prove to be efficiently solvable in our case.

Sang-il Oum, Rank-width: Algorithmic and structural results

Rank-width is a width parameter of graphs describing whether it is possible to decompose a graph into a tree-like structure by ‘simple’ cuts. This talk aims to survey known algorithmic and structural results on rank-width of graphs. This talk is based on a survey paper with further remarks on the recent developments.

Sun Kim (김선), Two identities in Ramanujan’s Lost Notebook with Bessel function series
2019-11-05 16:30 - 17:30 | Room 1401, Bldg. E6-1, KAIST
On page 335 in his lost notebook, Ramanujan recorded without proofs two identities involving finite trigonometric sums and doubly infinite series of Bessel functions. We proved each of these identities under three different interpretations for the double series, and showed that they are intimately connected with the classical circle and divisor problems in number theory. Furthermore, we established many analogues and generalizations of them. This is joint work with Bruce C. Berndt and Alexandru Zaharescu.

The 2nd East Asia Workshop on Extremal and Structural Graph Theory
2019-10-31 - 2019-11-04 | UTOP UBLESS Hotel, Jeju, Korea (유탑유블레스호텔제주)
The 2nd East Asia Workshop on Extremal and Structural Graph Theory is a workshop to bring active researchers in the field of extremal and structural graph theory, especially in the East Asia such as China, Japan, and Korea.
Date
Oct 31, 2019 (Arrival Day) – Nov 4, 2019 (Departure Day)
Venue and Date
1st floor Diamond Hall
UTOP UBLESS Hotel, Jeju, Korea (유탑유블레스호텔제주) Address: 502 Johamhaean-ro, Jocheon-eup, Jeju, Korea (제주특별자치도 제주시 조천읍 조함해안로 502) We plan to support the accommodation for invited participants.
The UTOP UBLESS Hotel is located at the beautiful Hamdeok Beach of the Jeju Island.
Invited Speakers

Ping Hu, Sun Yat-Sen University, China
Jaehoon Kim, KAIST, Korea
O-joung Kwon, Incheon National University and IBS Discrete Mathematics Group, Korea
Joonkyung Lee, University of Hamburg, Germany
Binlong Li, Northwestern Polytechnical University, China
Hongliang Lu, Xi’an Jiaotong University, China
Abhishek Methuku, IBS Discrete Mathematics Group, Korea
Atsuhiro Nakamoto, Yokohama National University, Japan
Kenta Noguchi, Tokyo University of Science, Japan
Kenta Ozeki, Yokohama National University, Japan
Boram Park, Ajou University, Korea
Yuejian Peng, Hunan University, China
Zi-Xia Song, University of Central Florida, U.S.A.
Tomáš Kaiser, University of West Bohemia, Czech Republic.
Maho Yokota, Tokyo University of Science, Japan.
Xuding Zhu, Zhejiang Normal University, China

More speakers to be announced as soon as confirmed. Last update: September 10.
Program
Day 0 (Oct. 31 Thursday)

4:00PM-6:00Pm Registration and Discussions

Day 1 (Nov. 1 Friday)

9:00AM-9:20AM Opening address
9:20AM-9:50AM Jaehoon Kim, A quantitative result on the polynomial Schur’s theorem
10:00AM-10:30AM Yuejian Peng, Lagrangian densities of hypergraphs
10:30AM-10:50AM Coffee Break
10:50AM-11:20AM Atsuhiro Nakamoto, Geometric quadrangulations on the plane
11:30AM-12:00PM Ping Hu, The inducibility of oriented stars
2:00PM-2:30PM Boram Park, 5-star coloring of some sparse graphs
2:40PM-3:10PM Kenta Ozeki, An orientation of graphs with out-degree constraint
3:10PM-3:30PM Coffee Break
3:30PM-5:30PM Problem session

Day 2 (Nov. 2 Saturday)

9:20AM-9:50AM Xuding Zhu, List colouring and Alon-Tarsi number of planar graphs
10:00AM-10:30AM O-joung Kwon, A survey of recent progress on Erdős-Pósa type problems
10:30AM-10:50AM Coffee Break
10:50AM-11:20AM Kenta Noguchi, Extension of a quadrangulation to triangulations, and spanning quadrangulations of a triangulation
11:30AM-12:00PM Zi-Xia Song, Ramsey numbers of cycles under Gallai colorings
2:00PM-2:30PM Binlong Li, Cycles through all finite vertex sets in infinite graphs
2:40PM-3:10PM Tomáš Kaiser, Hamilton cycles in tough chordal graphs
3:20PM-3:50PM Abhishek Methuku, On a hypergraph bipartite Turán problem
3:50PM-4:10PM Coffee Break
4:10PM-6:00PM Problem session and discussion

Day 3 (Nov. 3 Sunday)

9:20AM-9:50AM Joonkyung Lee, Odd cycles in subgraphs of sparse pseudorandom graphs
10:00AM-10:30AM Maho Yokota, Connectivity, toughness and forbidden subgraph conditions
10:30AM-10:50AM Coffee Break
10:50AM-11:20AM Hongliang Lu, On minimum degree thresholds for fractional perfect matchings and near perfect matchings in hypergraphs
11:30AM-12:00PM Contributed Talks
2:00PM-6:00PM Problem session / Discussions / Hike

Day 4 (Nov. 4 Monday)

9:00AM-10:30AM Discussions

History

1st East Asia Workshop on Extremal and Structural Graph Theory

Nov. 30-Dec. 2, 2018.
Held at and sponsored by Shanghai Center for Mathematical Sciences in China, under the name “2018 SCMS Workshop on Extremal and Structural Graph Theory”.
Organizers: Ping Hu, Seog-Jin Kim, Kenta Ozeki, Hehui Wu.

Organizers

Seog-Jin Kim, Konkuk University, Korea.
Sang-il Oum, IBS Discrete Mathematics Group, Korea and KAIST, Korea.
Kenta Ozeki, Yokohama National University, Japan.
Hehui Wu, Shanghai Center for Mathematical Sciences, China.

Sponsor
IBS Discrete Mathematics Group, Korea.
Abstracts
Ping Hu, The inducibility of oriented stars
Let $S_{k,ell}$ denote the oriented star with $k+ell$ edges, where the center has out-degree $k$ and in-degree $ell$. For all $k,ell$ with $k+ell$ large, we determine n-vertex digraphs $G$ which maximize the number of induced $S_{k,ell}$. This extends a result of Huang (2014) for all $S_{k,0}$, and a result of Hladký, Král’ and Norin for $S_{1,1}$. Joint work with Jie Ma, Sergey Norin, and Hehui Wu.
Jaehoon Kim, A quantitative result on the polynomial Schur’s theorem
Recently, Liu, Pach, and Sándor [arXiv:1811.05200] proved that for a polynomial $p(z)in mathbb{Z}[z]$, any $2$-coloring of $mathbb{N}$ has infinitely many monochromatic solutions of the equatoin $x+y=p(z)$ if and only if $2mid p(0)p(1)$. We improve their result in a quantitative way. We prove that if $p(z)$ has degree $d
eq 3$ and $2mid p(0)p(1)$, then any $2$-coloring of $[n]={1,dots, n}$ contains at least $n^{2/d^2 -o(1)}$ monochromatic solutions. This is sharp as there exists a coloring of $[n]$ with $O(n^{2/d^2})$ monochromatic solutions. Our method also gives some bound for the case when $d=3$, but it is not sharp. We also prove that if $2mid p(0)p(1)$, then the interval $[n, p(lceil frac{p(n)}{2} rceil)]$ contains at least one monochromatic solution of $x+y=p(z)$. This is sharp up to multiplicative constant at most two as one can color $[n, frac{1}{2}p(lceil frac{p(n)}{2} rceil)-1]$ with no monochromatic solutions. Joint work with Hong Liu and Péter Pál Pach.
O-joung Kwon, A survey of recent progress on Erdős-Pósa type problems
A graph family $mathcal{F}$ is said to have the Erdős-Pósa property if there is a function $f$ such that for every graph $G$ and an integer $k$, either $G$ contains $k$ disjoint copies of graphs in $mathcal{F}$, or it has a vertex set of size at most $f(k)$ that hits all copies of graphs in $mathcal{F}$. This name is motivated from the Erdős-Pósa theorem (1965) which says that the set of cycles has the Erdős-Pósa property. In this talk, we survey on progress of finding various graph families that have the Erdős-Pósa property, and would like to pose interesting open problems.
Joonkyung Lee, Odd cycles in subgraphs of sparse pseudorandom graphs
We answer two extremal questions about odd cycles that naturally arise in the study of sparse pseudorandom graphs. Let $Gamma$ be an $(n,d,lambda)$-graph, i.e., $n$-vertex, $d$-regular graphs with all nontrivial eigenvalues in the interval $[-lambda,lambda]$. Krivelevich, Lee, and Sudakov conjectured that, whenever $lambda^{2k-1}ll d^{2k}/n$, every subgraph $G$ of $Gamma$ with $(1/2+o(1))e(Gamma)$ edges contains an odd cycle $C_{2k+1}$. Aigner-Horev, Hàn, and the third author proved a weaker statment by allowing an extra polylogarithmic factor in the assumption $lambda^{2k-1}ll d^{2k}/n$, but we completely remove it and hence settle the conjecture. This also generalises Sudakov, Szabo, and Vu’s Turán-type theorem for triangles. Secondly, we obtain a Ramsey multiplicity result for odd cycles. Namely, in the same range of parameters, we prove that every 2-edge-colouring of $Gamma$ contains at least $(1-o(1))2^{-2k}d^{2k+1}$ monochromatic copies of $C_{2k+1}$. Both results are asymptotically best possible by Alon and Kahale’s construction of $C_{2k+1}$-free pseudorandom graphs. Joint work with Sören Berger, Mathias Schacht.
Binlong Li, Cycles through all finite vertex sets in infinite graphs
A closed curve in the Freudenthal compactification $|G|$ of an infinite locally finite graph $G$ is called a Hamiltonian curve if it meets every vertex of $G$ exactly once (and hence it meets every end at least once). We prove that $|G|$ has a Hamiltonian curve if and only if every finite vertex set of $G$ is contained in a cycle of $G$. We apply this to extend a number of results and conjectures on finite graphs to Hamiltonian curves in infinite locally finite graphs. For example, Barnette’s conjecture (that every finite planar cubic 3-connected bipartite graph is Hamiltonian) is equivalent to the statement that every one-ended planar cubic 3-connected bipartite graph has a Hamiltonian curve. It is also equivalent to the statement that every planar cubic 3-connected bipartite graph with a nowhere-zero 3-flow (with no restriction on the number of ends) has a Hamiltonian curve. However, there are 7-ended planar cubic 3-connected bipartite graphs that do not have a Hamiltonian curve. Joint work with André Kündgen and Carsten Thomassen.
Hongliang Lu, On minimum degree thresholds for fractional perfect matchings and near perfect matchings in hypergraphs
We study degree conditions for the existence of large matchings and fractional perfect matching in uniform hypergraphs. Firstly, we give some sufficient conditions for $k$-graphs to have fractional perfect matching in terms of minimum degree. Secondly, we prove that for integers $k,l,n$ with $kge 3$, $k/2<l<k$, and $n$ large, if $H$ is a $k$-uniform hypergraph on $n$ vertices and $delta_{l}(H)>{n-lchoose k-l}-{(n-l)-(lceil n/k rceil-2)choose 2}$, then $H$ has a matching covering all but a constant number of vertices. When $l=k-2$ and $kge 5$, such a matching is near perfect and our bound on $delta_l(H)$ is best possible. When $k=3$, with the help of an absorbing lemma of Hàn, Person, and Schacht, our proof also implies that $H$ has a perfect matching, a result proved by Kühn, Osthus, and Treglown and, independently, of Kahn. Joint work with Xingxing Yu and Xiaofan Yuan.
Abhishek Methuku, On a hypergraph bipartite Turán problem
Let $t$ be an integer such that $tgeq 2$. Let $K_{2,t}^{(3)}$ denote the triple system consisting of the $2t$ triples ${a,x_i,y_i}$, ${b,x_i,y_i}$ for $ 1 le i le t$, where the elements $a, b, x_1, x_2, ldots, x_t,$ $y_1, y_2, ldots, y_t$ are all distinct. Let $ex(n,K_{2,t}^{(3)})$ denote the maximum size of a triple system on $n$ elements that does not contain $K_{2,t}^{(3)}$. This function was studied by Mubayi and Verstraëte, where the special case $t=2$ was a problem of Erdős that was studied by various authors. Mubayi and Verstraëte proved that $ex(n,K_{2,t}^{(3)})<t^4binom{n}{2}$ and that for infinitely many $n$, $ex(n,K_{2,t}^{(3)})geq frac{2t-1}{3} binom{n}{2}$. These bounds together with a standard argument show that $g(t):=lim_{nto infty} ex(n,K_{2,t}^{(3)})/binom{n}{2}$ exists and that [frac{2t-1}{3}leq g(t)leq t^4.] Addressing a 15 year old question of Mubayi and Verstraëte on the growth rate of $g(t)$, we prove that as $t to infty$, [g(t) = Theta(t^{1+o(1)}).] Joint work with Beka Ergemlidze and Tao Jiang.
Atsuhiro Nakamoto, Geometric quadrangulations on the plane
Let $P$ be a point set on the plane with $|P| geq 4$ in a general position (i.e., no three points lie on the same straight line). A geometric quadrangulation $Q$ on $P$ is a geometric plane graph (i.e., every edge is a straight segment) such that the outer cycle of $Q$ coincides with the boundary of the convex hull ${rm Conv}(P)$ of $P$ and that each finite face of $Q$ is quadrilateral. We say that $P$ is quadrangulatable if $P$ admits a geometric quadrangulation. It is easy to see that if $P$ has an even number of points on the boundary of ${rm Conv}(P)$, then $P$ is quadrangulatable. Suppose that $P$ is $k$-colored for $k geq 2$, and that no two consecutive points on the boundary of ${rm Conv}(P)$ have the same color. Let us consider whether $P$ is quadrangulatable with no edge joining two points with the same color. Then we see that $P$ is not necessarily quadrangulatable. Hence, introducing Steiner points $S$ for $P$, which are ones put in the interior of ${rm Conv}(P)$ as we like, we consider whether $P cup S$ is quadrangulatable. Intuitively, for any $k$-colored $P$, adding sufficiently large Steiner points $S$, we wonder if $P cup S$ is quadrangulatable. However, we surprisingly see that it is impossible when $k=3$ (Alvarez et al., 2007). In my talk, we summarize these researches on quadrangulatability of point sets with Steiner points, and describe a relation with coloring of topological quadrangulations (Alvarez and Nakamoto, 2012 and Kato et al., 2014). Moreover, we describe a recent progress on a similar topic on quadrangulatability of a polygon with Steiner points.
Kenta Noguchi, Extension of a quadrangulation to triangulations, and spanning quadrangulations of a triangulation
A triangulation (resp., a quadrangulation) on a surface $S$ is a map of a graph (possibly with multiple edges and loops) on $S$ with each face bounded by a closed walk of length $3$ (resp., $4$). In this talk, we focus on the relationship between triangulations and quadrangulations on a surface. (I) An extension of a graph $G$ is the construction of a new graph by adding edges to some pairs of vertices in $G$. It is easy to see that every quadrangulation $G$ on any surface can be extended to a triangulation by adding a diagonal to each face of $G$. If we require the resulting triangulation to have more properties, the problem might be difficult and interesting. Our two main results are as follows. Every quadrangulation on any surface can be extended to an even (i.e. Eulerian) triangulation. Furthermore, we give the explicit formula for the number of distinct even triangulations extended from a given quadrangulation on a surface. These completely solves the problem raised by Zhang and He (2005). (II) It is easy to see that every loopless triangulation $G$ on any surface has a quadrangulation as a spanning subgraph of $G$. As well as (I), if we require the resulting quadrangulation to have more properties, the problem might be difficult and interesting. Kündgen and Thomassen (2017) proved that every loopless even triangulation $G$ on the torus has a spanning nonbipartite quadrangulation, and that if $G$ has sufficiently large face width, then $G$ also has a bipartite one. We prove that a loopless even triangulation $G$ on the torus has a spanning bipartite quadrangulation if and only if $G$ does not have $K_7$ as a subgraph. This talk is based on the papers (2015, 2019, 2019). Joint work with Atsuhiro Nakamoto and Kenta Ozeki.
Kenta Ozeki, An orientation of graphs with out-degree constraint
An orientation of an (undirected) graph $G$ is an assignment of directions to each edge of $G$. An orientation with certain properties has much attracted because of its applications, such as a list-coloring, and Tutte’s $3$-flow conjecture. In this talk, we consider an orientation such that the out-degree of each vertex is contained in a given list. For an orientation $O$ of $G$ and a vertex $v$, we denote by $d_O^+(v)$ the out-degree of $v$ in the digraph $G$ with respect to the orientation $O$. Recall that the number of outgoing edges is the out-degree. We denote by $mathbb{N}$ the set of natural numbers (including $0$). For a graph $G$ and a mapping $L: V(G)rightarrow 2^{mathbb{N}}$, an orientation $O$ of $G$ such that [d_O^+(v) in L(v)] for each vertex $v$ is called an $L$-orientation. In this talk, we pose the following conjecture. Conjecture. Let $G$ be a graph and let $L: V(G) rightarrow 2^{mathbb{N}}$ be a mapping. If [|L(v)| geq frac{1}{2}Big(d_G(v) +3Big)]for each vertex $v$, then $G$ has an $L$-orientation. I will explain some results related to Conjecture; the best possibility if it is true, and partial solutions for bipartite graphs. However, it is open even for complete graphs. This talk is based on the paper https://doi.org/10.1002/jgt.22498. Joint work with S. Akbari, M. Dalirrooyfard, K.Ehsani, and R. Sherkati.
Boram Park, 5-star coloring of some sparse graphs
A star $k$-coloring of a graph $G$ is a proper (vertex) $k$-coloring of $G$ such that the vertices on a path of length three receive at least three colors. Given a graph $G$, its star chromatic number, denoted $chi_s(G)$, is the minimum integer $k$ for which $G$ admits a star $k$-coloring. Studying star coloring of sparse graphs is an active area of research, especially in terms of the maximum average degree $mathrm{mad}(G)$ of a graph $G$. It is known that for a graph $G$, if $mathrm{mad}(G)<frac{8}{3}$, then $chi_s(G)leq 6$ (Kündgen and Timmons, 2010), and if $mathrm{mad}(G)< frac{18}{7}$ and its girth is at least 6, then $chi_s(G)le 5$ (Bu et al., 2009). We improve both results by showing that for a graph $G$ with $mathrm{mad}(G)le frac{8}{3}$, then $chi_s(G)le 5$. As an immediate corollary, we obtain that a planar graph with girth at least 8 has a star 5-coloring, improving the best known girth condition for a planar graph to have a star 5-coloring (Kündgen and Timmons, 2010 and Timmons, 2008). Joint work with Ilkyoo Choi.
Yuejian Peng, Lagrangian densities of hypergraphs
Given a positive integer $n$ and an $r$-uniform hypergraph $H$, the Turán number $ex(n, H)$ is the maximum number of edges in an $H$-free $r$-uniform hypergraph on $n$ vertices. The Turán density of $H$ is defined as [pi(H)=lim_{nrightarrowinfty} { ex(n,H) over {n choose r } }.] The Lagrangian density of an $r$-uniform graph $H$ is [pi_{lambda}(H)=sup {r! lambda(G):G;text{is};Htext{-free}},] where $lambda(G)$ is the Lagrangian of $G$. The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. Recently, Lagrangian densities of hypergraphs and Turán numbers of their extensions have been studied actively. The Lagrangian density of an $r$-uniform hypergraph $H$ is the same as the Turán density of the extension of $H$. Therefore, these two densities of $H$ equal if every pair of vertices of $H$ is contained in an edge. For example, to determine the Lagrangian density of $K_4^{3}$ is equivalent to determine the Turán density of $K_4^{3}$. For an $r$-uniform graph $H$ on $t$ vertices, it is clear that $pi_{lambda}(H)ge r!lambda{(K_{t-1}^r)}$, where $K_{t-1}^r$ is the complete $r$-uniform graph on $t-1$ vertices. We say that an $r$-uniform hypergraph $H$ on $t$ vertices is $lambda$-perfect if $pi_{lambda}(H)= r!lambda{(K_{t-1}^r)}$. A result of Motzkin and Straus implies that all graphs are $lambda$-perfect. It is interesting to explore what kind of hypergraphs are $lambda$-perfect. We present some open problems and recent results.
Zi-Xia Song, Ramsey numbers of cycles under Gallai colorings
For a graph $H$ and an integer $kge1$, the $k$-color Ramsey number $R_k(H)$ is the least integer $N$ such that every $k$-coloring of the edges of the complete graph $K_N$ contains a monochromatic copy of $H$. Let $C_m$ denote the cycle on $mge4 $ vertices. For odd cycles, Bondy and Erdős in 1973 conjectured that for all $kge1$ and $nge2$, $R_k(C_{2n+1})=ncdot 2^k+1$. Recently, this conjecture has been verified to be true for all fixed $k$ and all $n$ sufficiently large by Jenssen and Skokan; and false for all fixed $n$ and all $k$ sufficiently large by Day and Johnson (2017). Even cycles behave rather differently in this context. Little is known about the behavior of $R_k(C_{2n})$ in general. In this talk we will present our recent results on Ramsey numbers of cycles under Gallai colorings, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles. We prove that the aforementioned conjecture holds for all $k$ and all $n$ under Gallai colorings. We also completely determine the Ramsey number of even cycles under Gallai colorings. Joint work with Yaojun Chen and Fangfang Zhang.
Tomáš Kaiser, Hamilton cycles in tough chordal graphs
Chvátal conjectured in 1973 that all graphs with sufficiently high toughness are Hamiltonian. The conjecture remains open, but it is known to be true for various classes of graphs, including chordal graphs, claw-free graphs or planar graphs. We will discuss the case of chordal graphs and outline our proof that 10-tough chordal graphs are Hamiltonian, relying on a hypergraph version of Hall’s Theorem as our main tool. This improves a previous result due to Chen et al. (1998) where the constant $10$ is replaced by $18$. Joint work with Adam Kabela.
Maho Yokota, Connectivity, toughness and forbidden subgraph conditions
Let $textrm{conn}(G)$ and $textrm{tough}(G)$ denote the connectivity and the toughness of $G$. We know that low connectivity implies low toughness; if $textrm{conn}(G)leq k$, then $textrm{tough}(G) leq k/2$. On the other hand, we also know the converse is not true. We can construct a graph with high connectivity and low toughness. About this, we have next proposition. Proposition 1. Let $G$ be a graph, $k$ be an integer with $kgeq 1$ and $r$ be a real number with $r>1$. If $G$ is $k$-connected and $K_{1,lfloor r rfloor +1}$-free, then $textrm{tough}(G)geq k/r$. It means high connectivity implies high toughness under the star-free condition. Our purpose is to prove assertions which can be regarded as a converse of this statement; that is say, we ask what we can say about $mathcal H$ if high connectivity implies high toughness in the family of $mathcal H$-free graphs. About this question, Ota and Sueiro (2013) proved the following theorem. Theorem 1 (Ota and Sueiro). Let $H$ be a connected graph and $tau$ be a real number with $0<tauleq 1/2$. Almost all $H$-free connected graphs $G$ satisfy $textrm{tough}(G)geq tau$ if and only if $K_{1,lfloor 1/tau rfloor +1}$ contains $H$ as an induced subgraph. Our main result is high connectivity versions of this theorem. We proved the following theorems. Theorem 2. Let $H$ be a connected graph, $k$ be an integer with $kgeq 1$ and $r$ be a real number with $r>1$. Almost all $H$-free $k$-connected graphs $G$ satisfy $textrm{tough}(G)geq k/r$ if and only if $K_{1,lfloor 1/tau rfloor +1}$ contains $H$ as an induced subgraph. Theorem 3. Let $mathcal H={H_1,H_2}$ be a family of connected graphs, $k$ be an integer with $kgeq 1$ and $r$ be a real number with $r>1$. Almost all $mathcal H$-free $k$-connected graphs $G$ satisfy $textrm{tough}(G)geq k/r$ if and only if $K_{1,lfloor 1/tau rfloor +1}$ contains one of $H$ as an induced subgraph.
Xuding Zhu, List colouring and Alon-Tarsi number of planar graphs
A $d$-defective colouring of a graph $G$ is a colouring of the vertices of $G$ such that each vertex $v$ has at most $d$ neighbours coloured the same colour as $v$. We say $G$ is $d$-defective $k$-choosable if for any $k$-assignment $L$ of $G$, there exists a $d$-defective $L$-colouring, i.e., a $d$-defective colouring $f$ with $f(v) in L(v)$ for each vertex $v$. It was proved by Eaton and Hull (1999) and Škrekovski (1999) that every planar graph is $2$-defective $3$-choosable, and proved by Cushing and Kierstead (2010) that every planar graph is $1$-defective $4$-choosable. In other words, for a planar graph $G$, for any $3$-assigment $L$ of $G$, there is a subgraph $H$ with $Delta(H) le 2$ such that $G-E(H)$ is $L$-colourable; and for any $4$-list assignment $L$ of $G$, there is a subgraph $H$ with $Delta(H) le 1$ such that $G-E(H)$ is $L$-colourable. An interesting problem is whether there is a subgraph $H$ with $Delta(H) le 2$ such that $G-E(H)$ is $3$-choosable, and whether there is a subgraph $H$ with $Delta(H) le 1$ such that $G-E(H)$ is $4$-choosable. It turns out that the answer to the first question is negative and the answer to the second question is positive. Kim, Kim and I proved that there is a planar graph $G$ such that for any subgraph $H$ with $Delta(H)=3$, $G-E(H)$ is not $3$-choosable. Grytczuk and I proved that every planar graph $G$ has a matching $M$ such that $G-M$ has Alon-Tarsi number at most $4$, and hence is $4$-choosable. The late result also implies that every planar graph is $1$-defective $4$-paintable. For a subset $X$ of $V(G)$, let $f_X$ be the function defined as $f_X(v)=4$ for $v in X$ and $f_X(v)=5$ for $v in V(G)-X$. Our proof also shows that every planar graph $G$ has a subset $X$ of size $|X| ge |V(G)|/2$ such that $G$ is $f_X$-AT, which implies that $G$ is $f_X$-choosable and also $f_X$-paintable. In this talk, we shall present the proof and discuss possible strengthening of this result.

Pascal Gollin, A Cantor-Bernstein-type theorem for spanning trees in infinite graphs
2019-10-29 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Given a cardinal $lambda$, a $lambda$-packing of a graph $G$ is a family of $lambda$ many edge-disjoint spanning trees of $G$, and a $lambda$-covering of $G$ is a family of spanning trees covering $E(G)$.
We show that if a graph admits a $lambda$-packing and a $lambda$-covering then the graph also admits a decomposition into $lambda$ many spanning trees. In this talk, we concentrate on the case of $lambda$ being an infinite cardinal. Moreover, we will provide a new and simple proof for a theorem of Laviolette characterising the existence of a $lambda$-packing, as well as for a theorem of Erdős and Hajnal characterising the existence of a $lambda$-covering.
Joint work with Joshua Erde, Attila Joó, Paul Knappe and Max Pitz.

Extremal and Structural Graph Theory (2019 KMS Annual Meeting)
2019-10-26 - 2019-10-27 | Room 426, Hong-Mun Hall, Hongik University, Seoul
Focus Session @ 2019 KMS Annual Meeting
A focus session “Extremal and Structural Graph Theory” at the 2019 KMS Annual Meeting is organized by Sang-il Oum. URL: http://www.kms.or.kr/meetings/fall2019/
Speakers

Ilkyoo Choi (최일규), Hankuk University of Foreign Studies
Kevin Hendrey, IBS Discrete Mathematics Group
Pascal Gollin, IBS Discrete Mathematics Group
Jaehoon Kim (김재훈), KAIST
Ringi Kim (김린기), KAIST
Seog-Jin Kim (김석진), Konkuk University
O-joung Kwon (권오정), Incheon National University / IBS Discrete Mathematics Group
Zi-Xia Song (宋梓霞), University of Central Florida
Casey Tompkins, IBS Discrete Mathematics Group

Schedules

Slot A: October 26, 2019 Saturday, 9:00am-10:15am

Seog-Jin Kim
Kevin Hendrey
Ilkyoo Choi

Slot B: October 26, 2019 Saturday, 10:40am-11:55pm

Jaehoon Kim
Ringi Kim
Casey Tompkins

Slot D: October 27, 2019 Sunday, 9:00am-10:15am

Zi-Xia Song
Pascal Gollin
O-joung Kwon

Abstracts
Ilkyoo Choi (최일규), Degeneracy and colorings of squares of planar graphs without 4-cycles
We prove several results on coloring squares of planar graphs without 4-cycles. First, we show that if $G$ is such a graph, then $G^2$ is $(Delta(G)+72)$-degenerate. This implies an upper bound of $Delta(G)+73$ on the chromatic number of $G^2$ as well as on several variants of the chromatic number such as the list-chromatic number, paint number, Alon–Tarsi number, and correspondence chromatic number. We also show that if $Delta(G)$ is sufficiently large, then the upper bounds on each of these parameters of $G^2$ can all be lowered to $Delta(G)+2$ (which is best possible). To complement these results, we show that 4-cycles are unique in having this property. Specifically, let $S$ be a finite list of positive integers, with $4
otin S$. For each constant $C$, we construct a planar graph $G_{S,C}$ with no cycle with length in $S$, but for which $chi(G_{S,C}^2) > Delta(G_{S,C})+C$. This is joint work with Dan Cranston and Theo Pierron.
Kevin Hendrey, Defective and clustered choosability of sparse graphs
An (improper) graph colouring has defect $d$ if each monochromatic subgraph has maximum degree at most $d$, and has clustering $c$ if each monochromatic component has at most $c$ vertices. Given an infinite class of graphs $mathcal{G}$, it is interesting to ask for the minimum integer $chi_{Delta}(mathcal{G})$ for which there exist an integer $d$ such that every graph in $mathcal{G}$ has a $chi_{Delta}(mathcal{G})$-colouring with defect at most $d$, and the minimum integer $chi_{star}(mathcal{G})$-colouring for which there exist an integer $c$ such that every graph in $mathcal{G}$ has a $chi_{star}(mathcal{G})$-colouring with clustering at most $c$. We explore clustered and defective colouring in graph classes with bounded maximum average degree. As an example, our results show that every earth-moon graph has an 8-colouring with clustering at most 405. Our results hold in the stronger setting of list-colouring. Joint work with David Wood.
Pascal Gollin, Progress on the Ubiquity Conjecture
A classic result of Halin says that if a graph $G$ contains for every $n in mathbb{N}$ as subgraphs $n$ disjoint rays, i.e., one-way infinite paths, then $G$ already contains infinitely many disjoint rays as subgraphs. We say a graph $G$ is ubiquitous with respect to the subgraph relation if whenever a graph $Gamma$ contains $n$ disjoint copies of $G$ as a subgraph for all $n in mathbb{N}$, then $Gamma$ already contains infinitely many disjoint copies of $G$ as a subgraph. We define ubiquity w.r.t. the minor relation or topological minor relation analogously. A fundamental conjecture about infinite graphs due to Andreae is the Ubiquity Conjecture. It states that every locally finite connected graph is ubiquitous w.r.t. the minor relation. In a series of papers we make progress on the conjecture proving various ubiquity results w.r.t. both the topological minor relation and the minor relation, making use of well-quasi ordering techniques.
Jaehoon Kim (김재훈), A rainbow version of Dirac’s theorem
For a collection $mathbf{G}={G_1,dots, G_s}$ of graphs, we say that a graph $H$ is $mathbf{G}$-transversal, or $mathbf{G}$-rainbow, if there exists a bijection $phi:E(H)rightarrow [s]$ with $ein G_{phi(e)}$ for all $ein E(H)$. Aharoni conjectured that if for each $iin [r]$, then graph $G_i$ is an $n$-vertex graph on the same vertex set $V$ and $delta(G_i)geq n/2$ for all $iin [s]$, then there exists a $mathbf{G}$-transversal Hamilton cycle on $V$. We prove this conjecture. We also prove a similar result for $K_r$-factors. This is joint work with Felix Joos.
Ringi Kim (김린기), Obstructions for partitioning into forests
For a class $mathcal{C}$ of graphs, we de fine $mathcal{C}$-edge-brittleness of a graph $G$ as the minimum $ell$ such that the vertex set of $G$ can be partitioned into sets inducing a subgraph in $mathcal{C}$ and there are $ell$ edges having ends in distinct parts. In this talk, we characterize classes of graphs having bounded $mathcal{C}$-edge-brittleness for a class $mathcal{C}$ of forests in terms of forbidden obstructions. This is joint work with Sang-il Oum and Sergey Norin.
Seog-Jin Kim (김석진), The Alon-Tarsi number of subgraphs of a planar graph
This paper constructs a planar graph $G_1$ such that for any subgraph $H$ of $G_1$ with maximum degree $Delta(H) le 3$, $G_1-E(H)$ is not $3$-choosable, and a planar graph $G_2$ such that for any star forest $F$ in $G_2$, $G_2-E(F)$ contains a copy of $K_4$ and hence $G_2-E(F)$ is not $3$-colourable. On the other hand, we prove that every planar graph $G$ contains a forest $F$ such that the Alon-Tarsi number of $G – E(F)$ is at most $3$, and hence $G – E(F)$ is 3-paintable and 3-choosable. This is joint work with Ringi Kim and Xuding Zhu.
O-joung Kwon (권오정), Erdős-Pósa property of H-induced subdivisions
A class $mathcal{F}$ of graphs has the induced Erdős-Pósa property if there exists a function $f$ such that for every graph $G$ and every positive integer $k$, $G$ contains either $k$ pairwise vertex-disjoint induced subgraphs that belong to $mathcal{F}$, or a vertex set of size at most $f(k)$ hitting all induced copies of graphs in $mathcal{F}$. Kim and Kwon (SODA’18) showed that for a cycle $C_{ell}$ of length $ell$, the class of $C_{ell}$-subdivisions has the induced Erdős-Pósa property if and only if $ellle 4$. In this paper, we investigate whether or not the class of $H$-subdivisions has the induced Erdős-Pósa property for other graphs $H$. We completely settle the case when $H$ is a forest or a complete bipartite graph. Regarding the general case, we identify necessary conditions on $H$ for the class of $H$-subdivisions to have the induced Erdős-Pósa property. For this, we provide three basic constructions that are useful to prove that the class of the subdivisions of a graph does not have the induced Erdős-Pósa property. Among remaining graphs, we prove that if $H$ is either the diamond, the $1$-pan, or the $2$-pan, then the class of $H$-subdivisions has the induced Erdős-Pósa property.
Zi-Xia Song, On the size of $(K_t,mathcal{T}_k)$-co-critical graphs
Given an integer $rge1$ and graphs $G, H_1, ldots, H_r$, we write $G rightarrow ({H}_1, ldots, {H}_r)$ if every $r$-coloring of the edges of $G$ contains a monochromatic copy of $H_i$ in color $i$ for some $iin{1, ldots, r}$. A non-complete graph $G$ is $(H_1, ldots, H_r)$-co-critical if $G
rightarrow ({H}_1, ldots, {H}_r)$, but $G+erightarrow ({H}_1, ldots, {H}_r)$ for every edge $e$ in $overline{G}$. Motivated by Hanson and Toft’s conjecture, we study the minimum number of edges over all $(K_t, mathcal{T}_k)$-co-critical graphs on $n$ vertices, where $mathcal{T}_k$ denotes the family of all trees on $k$ vertices. In this talk, we will present our recent results on this topic. This is joint work with Jingmei Zhang.
Casey Tompkins, Generalizations of the Erdős-Gallai theorem
A classical result of Erdős and Gallai bounds the number of edges in an $n$-vertex graph with no path of length $k$ (denoted $P_k$). In this talk, I will discuss generalizations of this result in multiple settings. In one direction, I will consider so-called generalized Turán problems for $P_k$-free graphs. That is, rather than maximizing the number of edges, we consider maximizing the number of copies of some graph $H$. Building on results of Luo where $H$ is a clique, we consider the case when $H$ is also a path. In another direction, I will consider Erdős-Gallai type problems in a hypergraph setting. Here I will discuss recent results involving forbidding Berge copies of a path, including the solution to some problems and conjectures of Győri, Katona and Lemons as well Füredi, Kostochka and Luo. I will also mention some Kopylov-type variants of this problem where the hypergraph is assumed to be connected. Moreover, I will discuss some recent work on forbidding Berge copies of a tree. Finally, as time permits I will mention some colored variants of the Erdős-Gallai problem. The new results presented are joint work with various subsets of the authors Akbar Davoodi, Beka Ergemlidze, Ervin Győri, Abhishek Methuku, Nika Salia, Mate Vizer, Oscar Zamora.

Joonkyung Lee (이준경), On some properties of graph norms
2019-10-22 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
For a graph $H$, its homomorphism density in graphs naturally extends to the space of two-variable symmetric functions $W$ in $L^p$, $pgeq e(H)$, denoted by $t_H(W)$. One may then define corresponding functionals $|W|_{H}:=|t_H(W)|^{1/e(H)}$ and $|W|_{r(H)}:=t_H(|W|)^{1/e(H)}$ and say that $H$ is (semi-)norming if $|.|_{H}$ is a (semi-)norm and that $H$ is weakly norming if $|.|_{r(H)}$ is a norm.
We obtain some results that contribute to the theory of (weakly) norming graphs. Firstly, we show that ‘twisted’ blow-ups of cycles, which include $K_{5,5}setminus C_{10}$ and $C_6square K_2$, are not weakly norming. This answers two questions of Hatami, who asked whether the two graphs are weakly norming. Secondly, we prove that $|.|_{r(H)}$ is not uniformly convex nor uniformly smooth, provided that $H$ is weakly norming. This answers another question of Hatami, who estimated the modulus of convexity and smoothness of $|.|_{H}$. We also prove that every graph $H$ without isolated vertices is (weakly) norming if and only if each component is an isomorphic copy of a (weakly) norming graph. This strong factorisation result allows us to assume connectivity of $H$ when studying graph norms. Based on joint work with Frederik Garbe, Jan Hladký, and Bjarne Schülke.

Zi-Xia Song (宋梓霞), Ramsey numbers of cycles under Gallai colorings
2019-10-15 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
For a graph $H$ and an integer $kge1$, the $k$-color Ramsey number $R_k(H)$ is the least integer $N$ such that every $k$-coloring of the edges of the complete graph $K_N$ contains a monochromatic copy of $H$. Let $C_m$ denote the cycle on $mge4 $ vertices. For odd cycles, Bondy and ErdH{o}s in 1973 conjectured that for all $kge1$ and $nge2$, $R_k(C_{2n+1})=ncdot 2^k+1$. Recently, this conjecture has been verified to be true for all fixed $k$ and all $n$ sufficiently large by Jenssen and Skokan; and false for all fixed $n$ and all $k$ sufficiently large by Day and Johnson. Even cycles behave rather differently in this context. Little is known about the behavior of $R_k(C_{2n})$ in general. In this talk we will present our recent results on Ramsey numbers of cycles under Gallai colorings, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles. We prove that the aforementioned conjecture holds for all $k$ and all $n$ under Gallai colorings. We also completely determine the Ramsey number of even cycles under Gallai colorings.
Joint work with Dylan Bruce, Christian Bosse, Yaojun Chen and Fangfang Zhang.

Alexandr V. Kostochka, Reconstructing graphs from smaller subgraphs
2019-10-10 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
A graph or graph property is $ell$-reconstructible if it is determined by the multiset of all subgraphs obtained by deleting $ell$ vertices. Apart from the famous Graph Reconstruction Conjecture, Kelly conjectured in 1957 that for each $ellinmathbb N$, there is an integer $n=n(ell)$ such that every graph with at least $n$ vertices is $ell$-reconstructible.
We show that for each $nge7$ and every $n$-vertex graph $G$, the degree list and connectedness of $G$ are $3$-reconstructible, and the threshold $ngeq 7$ is sharp for both properties.‌ We also show that all $3$-regular graphs are $2$-reconstructible.

Alexandr V. Kostochka, On Ramsey-type problems for paths and cycles in dense graphs
2019-10-08 16:30 - 17:30 | Room 1501, Bldg. E6-1, KAIST
A well-known Ramsey-type puzzle for children is to prove that among any 6 people either there are 3 who know each other or there are 3 who do not know each other. More generally, a graph $G$ arrows a graph $H$ if for any coloring of the edges of $G$ with two colors, there is a monochromatic copy of $H$. In these terms, the above puzzle claims that the complete $6$-vertex graph $K_6$ arrows the complete $3$-vertex graph $K_3$.
We consider sufficient conditions on the dense host graphs $G$ to arrow long paths and even cycles. In particular, for large $n$ we describe all multipartite graphs that arrow paths and cycles with $2n$ edges. This implies a conjecture by Gyárfás, Ruszinkó, Sárkőzy and Szemerédi from 2007 for such $n$. Also for large $n$ we find which minimum degree in a $(3n-1)$-vertex graph $G$ guarantees that $G$ arrows the $2n$-vertex path. This yields a more recent conjecture of Schelp.
This is joint work with Jozsef Balogh, Mikhail Lavrov and Xujun Liu.

Casey Tompkins, Extremal problems for Berge hypergraphs
2019-10-01 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Given a graph $G$, there are several natural hypergraph families one can define. Among the least restrictive is the family $BG$ of so-called Berge copies of the graph $G$. In this talk, we discuss Turán problems for families $BG$ in $r$-uniform hypergraphs for various graphs $G$. In particular, we are interested in general results in two settings: the case when $r$ is large and $G$ is any graph where this Turán number is shown to be eventually subquadratic, as well as the case when $G$ is a tree where several exact results can be obtained. The results in the first part are joint with Grósz and Methuku, and the second part with Győri, Salia and Zamora.

Cory Palmer, A survey of Turán-type subgraph counting problems
2019-09-19 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Let $F$ and $H$ be graphs. The subgraph counting function $operatorname{ex}(n,H,F)$ is defined as the maximum possible number of subgraphs $H$ in an $n$-vertex $F$-free graph. This function is a direct generalization of the Turán function as $operatorname{ex}(n,F)=operatorname{ex}(n,K_2,F)$. The systematic study of $operatorname{ex}(n,H,F)$ was initiated by Alon and Shikhelman in 2016 who generalized several classical results in extremal graph theory to the subgraph counting setting. Prior to their paper, a number of individual cases were investigated; a well-known example is the question to determine the maximum number of pentagons in a triangle-free graph. In this talk we will survey results on the function $operatorname{ex}(n,H,F)$ including a number of recent papers. We will also discuss this function’s connection to hypergraph Turán problems.

Kevin Hendrey, The minimum connectivity forcing forest minors in large graphs
2019-09-10 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Given a graph $G$, we define $textrm{ex}_c(G)$ to be the minimum value of $t$ for which there exists a constant $N(t,G)$ such that every $t$-connected graph with at least $N(t,G)$ vertices contains $G$ as a minor. The value of $textrm{ex}_c(G)$ is known to be tied to the vertex cover number $tau(G)$, and in fact $tau(G)leq textrm{ex}_c(G)leq frac{31}{2}(tau(G)+1)$. We give the precise value of $textrm{ex}_c(G)$ when $G$ is a forest. In particular we find that $textrm{ex}_c(G)leq tau(G)+2$ in this setting, which is tight for infinitely many forests.

Mihyun Kang (강미현), The genus of a random graph and the fragile genus property
2019-08-20 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
In this talk we shall discuss how quickly the genus of the Erdős-Rényi random graph grows as the number of edges increases and how dramatically a small number of random edges can increase the genus of a randomly perturbed graph. (Joint work with Chris Dowden and Michael Krivelevich)

2019 Combinatorics Workshop
2019-08-13 - 2019-08-15 | Hotel Skypark, Songdo, Incheon, Korea (송도 스카이파크호텔)
The annual conference on Combinatorics Workshop (조합론 학술대회) began in 2004 by the Yonsei University BK21 Research Group. This year it will take place in Songdo, Incheon, August 13-15, 2019.

Due to the capacity (50 persons) of the place, we are able to limit your registration. In principle, registration is on a first-come, first-served basis.

Title 2019 Combinatorics Workshop (2019 조합론 학술대회)
Date August 13-15 (Tue-Thu), 2019
Venue Hotel Skypark, Songdo, Incheon
Web https://cw2019.combinatorics.kr

We are going to

give six 50-minute talks and ten 25-minute talks in Korean.
distribute the program and abstracts of CW2019.
provide for the accommodations for all participants.
provide for six meals (two breakfasts, two luncheons, one dinner, and one banquet) for all participants.

Plenary Speaker

Mihyun Kang, Graz University of Technology

Keynote Speakers

Jaehoon Kim, KAIST
Seung Jin Lee, Seoul National University
Meesue Yoo, Dankook University

Invited Speakers

Eun-Kyung Cho, Hankuk University of Foreign Studies
Soogang Eoh, Seoul National University
JiSun Huh, Sungkyunkwan University
Jihyeug Jang, Sungkyunkwan University
Dong Yeap Kang, KAIST and IBS Discrete Mathematics Group
Min Jeong Kang, Incheon National University
Dabeen Lee, IBS Discrete Mathematics Group
Kang-Ju Lee, Seoul National University
Myeonghwan Lee, Incheon National University
Jihye Park, Yeungnam University
Sun-mi Yun, Sungkyunkwan University

Organizing Committee

O-joung Kwon, Incheon National University and IBS Discrete Mathematics Group
Suil O, SUNY Korea
Sang-il Oum, IBS Discrete Mathematics Group and KAIST
Heesung Shin, Inha University

Advisory Committee

Committee of Discrete Mathematics, The Korean Mathematical Society (Chair: Seog-Jin Kim, Konkuk University)

Sponsors

IBS Discrete Mathematics Group
NRF (National Research Foundation of Korea)

2019-2 IBS One-Day Conference on Extremal Graph Theory
2019-08-12 11:00 - 20:00 | Room B232, IBS (기초과학연구원)
Invited Speakers

Jaehoon Kim (김재훈), KAIST
Hong Liu (刘鸿), University of Warwick
Abhishek Methuku, IBS Discrete Mathematics Group
Péter Pál Pach, Budapest University of Technology and Economics

Schedule
August 12, Monday
11:00am-12:00pm Jaehoon Kim (김재훈): Tree decompositions of graphs without large bipartite holes
12:00pm-1:30pm Lunch
1:30pm-2:30pm Abhishek Methuku: Bipartite Turán problems for ordered graphs
3:00pm-4:00pm Péter Pál Pach: On some applications of graph theory to number theoretic problems
4:30pm-5:30pm Hong Liu: Recent advance in Ramsey-Turán theory
6:00pm-8:00pm Banquet
Abstract
Jaehoon Kim (김재훈), Tree decompositions of graphs without large bipartite holes
A recent result of Condon, Kim, Kühn and Osthus implies that for any $rgeq (frac{1}{2}+o(1))n$, an $n$-vertex almost $r$-regular graph $G$ has an approximate decomposition into any collections of $n$-vertex bounded degree trees. In this talk, we prove that a similar result holds for an almost $alpha n$-regular graph $G$ with any $alpha>0$ and a collection of bounded degree trees on at most $(1-o(1))n$ vertices if $G$ does not contain large bipartite holes. This result is sharp in the sense that it is necessary to exclude large bipartite holes and we cannot hope for an approximate decomposition into $n$-vertex trees. This is joint work with Younjin Kim and Hong Liu.
Abhishek Methuku, Bipartite Turán problems for ordered graphs
A zero-one matrix $M$ contains a zero-one matrix $A$ if one can delete rows and columns of $M$, and turn 1-entries into 0-entries such that the resulting matrix is $A$. The extremal number of $A$, denoted by $ex(n,A)$, is the maximum number of $1$-entries in an $ntimes n$ sized matrix $M$ that does not contain $A$.
A matrix $A$ is column-$t$-partite (or row-$t$-partite), if it can be cut along the columns (or rows) into $t$ submatrices such that every row (or column) of these submatrices contains at most one $1$-entry. We prove that if $A$ is column-$t$-partite, then $operatorname{ex}(n,A)<n^{2-frac{1}{t}+frac{1}{2t^{2}}+o(1)}$, and if $A$ is both column- and row-$t$-partite, then $operatorname{ex}(n,A)<n^{2-frac{1}{t}+o(1)}$, and this bound is close to being optimal. Our proof introduces a new density-increment-type argument which is combined with the celebrated dependent random choice method.
Results about the extremal numbers of zero-one matrices translate into results about the Turán numbers of bipartite ordered graphs. In particular, a zero-one matrix with at most $t$ 1-entries in each row corresponds to an ordered graph with maximum degree $t$ in one of its vertex classes. The aim of this talk is to establish general results about the extremal numbers of ordered graphs. Our results are partially motivated by a well known result of Füredi (1991) and Alon, Krivelevich, Sudakov (2003) stating that if $H$ is a bipartite graph with maximum degree $t$ in one of the vertex classes, then $operatorname{ex}(n,H)=O(n^{2-frac{1}{t}})$. This is joint work with Tomon.
Péter Pál Pach, On some applications of graph theory to number theoretic problems
How large can a set of integers be, if the equation $a_1a_2dots a_h=b_1b_2dots b_h$ has no solution consisting of distinct elements of this set? How large can a set of integers be, if none of them divides the product of $h$ others? How small can a multiplicative basis for ${1, 2, dots, n}$ be? The first question is about a generalization of the multiplicative Sidon sets, the second one is of the primitive sets, while the third one is the multiplicative version of the well-studied analogue problem for additive bases.
In answering the above mentioned questions graph theory plays an important role and in most of our results not only the asymptotics are found, but very tight bounds are obtained for the error terms, as well. We will also discuss the counting version of these questions.
Hong Liu, Recent advance in Ramsey-Turán theory
We will talk about Ramsey-Turán theory and some recent development. More specifically, we will talk about graphs with $alpha_r(G)=o(n)$, where $alpha_r(G)$ is the largest size subset with no $K_r$. Two major open problems in this area from the 80s ask: (1) whether Bollobas-Erdos graph can be generalised to densities other than $1/2$; (2) whether the asymptotic extremal structure for $alpha_r(G)$ resembles that of $alpha_2(G)$. We settle the first conjecture by constructing Bollobas-Erdos type graph with density $a$ for arbitrary rational number $ale 1/2$; and refute the second conjecture by witnessing asymptotic extremal structures that are drastically different from the $alpha_2(G)$ problem via a ”Mobius product” construction.
Joint work with Christian Reiher, Maryam Sharifzadeh, and Katherine Staden.

2019 IBS Summer Research Program on Algorithms and Complexity in Discrete Structures
2019-07-21 - 2019-08-10 | Room B232, IBS (기초과학연구원)
Schedule
July 22 Monday
10:00-11:00 Introduction, 11:00-12:00 Open Problems
July 23 Tuesday
10:00-10:30 Stefan Kratsch, Humboldt-Universität zu Berlin, Germany
Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
10:45-11:15 Benjamin Bergougnoux, University Clermont Auvergne, France
More applications of the d-neighbor equivalence
11:30-12:00 Yixin Cao, Hong Kong Polytechnic University, China
Enumerating Maximal Induced Subgraphs
13:30-14:30 Open Problems
July 24 Wednesday
We will go to KAIST for June Huh‘s two talks 15:00-16:00, 16:30-17:30. A IBS shuttle bus @14:30 from the lobby.
July 25 Thursday
10:00-11:00 Nick Brettell, Durham University, UK
Recent work on characterising matroids representable over finite fields
11:30-12:00 Mamadou M. Kanté, University Clermont Auvergne, France
On recognising k-letter graphs
July 26 Friday
10:00-11:00 O-joung Kwon (권오정), Incheon National University, Korea
The grid theorem for vertex-minors
11:00-12:00 Progress Report
July 27 Saturday
8:30 Excursion to Damyang (departure from the accommodation)
July 29 Monday
10:00-11:00 Archontia Giannopoulou, National and Kapodistrian University of Athens, Greece
The directed flat wall theorem
11:30-12:00 Eunjung Kim (김은정), LAMSADE-CNRS, France
Subcubic even-hole-free graphs have a constant treewidth
July 30 Tuesday
10:00-11:00 Pierre Aboulker, ENS Ulm, France
Generalizations of the geometric de Bruijn Erdős Theorem
11:30-12:00 Michael Dobbins, Binghamton University, USA
Barycenters of points in polytope skeleta
July 31 Wednesday
10:00-11:00 Magnus Wahlström, Royal Holloway, University of London, UK
FPT-algorithms via LP-relaxations
11:30-12:00 Édouard Bonnet, ENS Lyon, France
The FPT/W[1]-hard dichotomy of Max Independent Set in H-free graphs
August 1 Thursday
10:00-11:00 Euiwoong Lee (이의웅), NYU, USA
Losing treewidth by separating subsets
11:30-12:00 Sang-il Oum (엄상일), IBS Discrete Mathematics Group and KAIST, Korea
Branch-depth: Generalizing tree-depth of graphs
August 2 Friday
10:00-11:00 Dabeen Lee (이다빈), IBS Discrete Mathematics Group, Korea
t-perfect graphs and the stable set problem
11:00-12:00 Progress Report
August 5-9: Free Discussions / Research Collaborations / Progress Report
Tea time: Every weekday 3:30pm
Abstracts
July 23 Tuesday
Stefan Kratsch, Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
The Vertex Cover problem plays an essential role in the study of polynomial kernelization in parameterized complexity, i.e., the study of provable and efficient preprocessing for NP-hard problems. Motivated by the great variety of positive and negative results for kernelization for Vertex Cover subject to different parameters and graph classes, we seek to unify and generalize them using so-called blocking sets, which have played implicit and explicit roles in many results. We show that in the most-studied setting, parameterized by the size of a deletion set to a specified graph class ${cal C}$, bounded minimal blocking set size is necessary but not sufficient to get a polynomial kernelization. Under mild technical assumptions, bounded minimal blocking set size is showed to allow an essentially tight efficient reduction in the number of connected components. We then determine the exact maximum size of minimal blocking sets for graphs of bounded elimination distance to any hereditary class ${cal C}$, including the case of graphs of bounded treedepth. We get similar but not tight bounds for certain non-hereditary classes ${cal C}$, including the class ${cal C}_{LP}$ of graphs where integral and fractional vertex cover size coincide. These bounds allow us to derive polynomial kernels for Vertex Cover parameterized by the size of a deletion set to graphs of bounded elimination distance to, e.g., forest, bipartite, or ${cal C}_{LP}$ graphs.
Benjamin Bergougnoux, More applications of the d-neighbor equivalence
In this talk, I will present a framework which gives efficient algorithms for several connectivity problems such as Connected Dominating Set, Node Weighted Steiner Tree, Maximum Induced Tree, Longest Induced Path, and Feedback Vertex Set. For all these problems, we obtain efficient algorithms parameterized respectively by tree-width, clique-width, Q-rank-width, rank-width and maximum induced matching width. Our approach simplifies and unifies the known algorithms for each of the parameters and match asymptotically also the running time of the best algorithms for Vertex Cover and Dominating Set. Our framework is based on the d-neighbor equivalence defined in [Bui-Xuan, Telle and Vatshelle, TCS 2013]. The results we obtain highlight the importance and the generalizing power of this equivalence relation on width measures. We also prove that this equivalence relation could be useful for Max Cut: a W[1]-hard problem parameterized by clique-width.
Paper available on HAL : https://hal.archives-ouvertes.fr/hal-01799573
Yixin Cao, Enumerating Maximal Induced Subgraphs
We study efficient algorithms for the maximal induced subgraphs problem: Given a graph on $n$ vertices, enumerate all its maximal induced subgraphs that belong to a particular hereditary graph class. While its optimization version, known as the vertex deletion problem in literature, has been intensively studied, algorithms for the enumeration version exist only for few simple graph classes, e.g., independent sets and cliques. Enumeration algorithms are mainly categorized in three complexity classes, polynomial total time (polynomial on $n$ and the total number of solutions), incremental polynomial time (for all $s$, the time to output the first $s$ solutions is polynomial on $n$ and $s$), and polynomial delay (for all $s$, the time to output the first $s$ solutions is polynomial on $n$ and linear on $s$). We first show that the maximal induced subgraphs problem can be solved in polynomial total time if and only if it can be solved in incremental polynomial time. We then propose general approaches to develop polynomial-delay algorithms and incremental-polynomial-time algorithms for the problem. They enable us to develop simple algorithms to solve the problem with polynomial delay for a large number of graph classes, and in incremental polynomial time for interval graphs, chordal graphs as well as two of its well-studied subclasses, and all graph classes with finite forbidden induced subgraphs.
July 25 Thursday
Nick Brettell, Recent work on characterising matroids representable over finite fields
Characterising when a matroid is representable over a certain field or set of fields is one of the oldest problems in matroid theory, dating back to Whitney’s 1935 paper. In this talk, I will discuss some of the more recent work in this area, with a focus on work I have been involved with towards characterising matroids representable over all fields of size at least four.
Mamadou M. Kanté, On recognising k-letter graphs
$k$-letter graphs are a subclass of graphs of linear clique-width $k$, but are well-quasi-ordered by the induced subgraph ordering. I present a simple FPT algorithm for recognising $k$-letter graphs and also an upper bound on the size of minimal obstructions. The characterisation is based on a simple observation allowing an MSOL-definability. (joint work with V. Lozin)
July 26 Friday
O-joung Kwon (권오정), The grid theorem for vertex-minors
We prove that, for a circle graph $H$, every graph with sufficiently large rank-width contains a vertex-minor isomorphic to $H$. This is joint work with Jim Geelen, Rose McCarty, and Paul Wollan.
July 29 Monday
Archontia Giannopoulou, The directed flat wall theorem
At the core of the Robertson-Seymour theory of Graph Minors lies a powerful structure theorem which captures, for any fixed graph $H$, the common structural features of all the graphs not containing $H$ as a minor [Neil Robertson, Paul D. Seymour: Graph Minors. XVI. Excluding a non-planar graph. J. Comb. Theory, Ser. B 89(1): 43-76 (2003)]. An important step towards this structure theorem is the Flat Wall Theorem [Neil Robertson, Paul D. Seymour: Graph Minors .XIII. The Disjoint Paths Problem. J. Comb. Theory, Ser. B 63(1): 65-110 (1995)], which has a lot of algorithmic applications (for example, the minor-testing and the disjoint paths problem with fixed number terminals).
In this paper, we prove the directed analogue of this Flat Wall Theorem. Our result builds on the recent Directed Grid Theorem by two of the authors (Kawarabayashi and Kreutzer), and we hope that this is an important and significant step toward the directed structure theorem, as with the case for the undirected graph for the graph minor project.
Joint work with Ken-ichi Kawarabayashi, Stephan Kreutzer, and O-joung Kwon.
Eunjung Kim (김은정), Subcubic even-hole-free graphs have a constant treewidth
It is known that even-hole-free graphs can have arbitrarily large rankwidth, but all known constructions have many high-degree vertices. It has been believed in the structural graph theory community that the rankwidth shall be bounded if the maximum degree is bounded. We prove that there exists a universal constant $c$ such that every even-hole-free graph of degree at most three has treewidth at most $c$. As a by-product of the proof, we also show that there exists a function $f$ such that for any $r$, $K_r$-minor-free and even-hole-free graph has treewidth at most $f(r)$; this extends the result of Silva et. al. (Discrete Applied Mathematics 2010) addressing the case of planar graphs.
This is a joint work with Pierre Aboulker and Isolde Adler.
July 30 Tuesday
Pierre Aboulker, Generalizations of the geometric de Bruijn Erdős Theorem
A classic Theorem of de Bruijn and Erdős states that every noncollinear set of n points in the plane determines at least n distinct lines. The line $L(u,v)$ determined by two points $u$, $v$ in the plane consists of all points $p$ such that

$operatorname{dist}(p, u)+operatorname{dist}(u, v)=operatorname{dist}(p, v)$ (i.e. $u$ is between $p$ and $v$) or
$operatorname{dist}(u, p)+operatorname{dist}(p, v)=operatorname{dist}(u, v)$ (i.e. $p$ is between $u$ and $v$) or
$operatorname{dist}(u, v)+operatorname{dist}(v, p)=operatorname{dist}(u, p)$ (i.e. $v$ is between $u$ and $p$).

With this definition of line $L(uv)$ in an arbitrary metric space $(V, operatorname{dist})$, Chen and Chvátal conjectured that every metric space on n points, where n is at least 2, has at least n distinct lines or a line that consists of all n points. The talk will survey results on and around this conjecture.
Michael Dobbins, Barycenters of points in polytope skeleta
In this talk I will classify the n-tuples of dimensions such that any target point in any d-polytope is the barycenter of points in faces of the prescribed dimensions. Specifically, for a $(nk+r)$-polytope and target point, we can always find $r$ points in faces of dimension $k+1$, and $n-r$ points in faces of dimension $k$, that have their barycenter at the given target. This is tight in the sense that we cannot require even one of the points to be in a face of dimension less than $k$, and we cannot require more than $n-r$ of the points to be in faces of dimension $k$. This is joint work with Florian Frick.
July 31 Wednesday
Magnus Wahlström, FPT-algorithms via LP-relaxations
LP-relaxations are traditionally (within theoretical computer science) used for computing approximate solutions to NP-hard problems, but across the last few years there have been several examples where LP-relaxations have been used to guide FPT-algorithms — that is, exact (non-approximate) algorithms whose running time is bounded in terms of a “parameter” of the input instance. This approach has given algorithms that are simultaneously simpler and faster for a range of central problems in parameterized complexity. At the same time, this is applicable only to specific problems and relaxations; an arbitrary LP-relaxation, even one that has good properties in an approximation sense, will in general give no useful guidance with respect to exact solutions.
In this talk, we give an overview of these FPT applications, and the conditions they impose on the LP-relaxation. Our main focus is on an approach of “discrete relaxation” referred to as Valued CSPs, but we also briefly survey more immediately combinatorial conditions, as well as related algorithms that solve these problems more efficiently (e.g., so-called linear-time FPT algorithms) by bypassing the LP-solver.
Édouard Bonnet, The FPT/W[1]-hard dichotomy of Max Independent Set in H-free graphs
Maximum Independent Set (MIS) is in general graphs the paradigmatic W[1]-hard problem. In stark contrast, polynomial-time algorithms are known when the inputs are restricted to structured graph classes such as, for instance, perfect graphs (which includes bipartite graphs, chordal graphs, co-graphs, etc.) or claw-free graphs. In this talk, we introduce some variants of co-graphs with “parameterized noise”, that is, graphs that can be turned into disjoint unions or complete sums by the removal of a certain number of vertices and the edition of a certain number of edges per incident vertex, both controlled by the parameter. We give a series of FPT Turing-reductions on these classes and use them to make some progress on the parameterized complexity of MIS in $H$-free graphs. We present the current state of the (randomized) FPT vs W[1]-hard dichotomy of MIS in $H$-free graphs. We then show that for every fixed $t geq 1$, MIS is FPT in $P(1,t,t,t)$-free graphs, where $P(1,t,t,t)$ is the graph obtained by substituting all the vertices of a four-vertex path but one end of the path by cliques of size t. In particular, this helped finishing the classification when H has at most five vertices.
This follows joint works with Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, and Rémi Watrigant.
August 1 Thursday
Euiwoong Lee (이의웅), Losing treewidth by separating subsets
We study the problem of deleting the smallest set S of vertices (resp. edges) from a given graph $G$ such that the induced subgraph (resp. subgraph) $G setminus S$ belongs to some class of graphs $H$. When graphs in H have treewidth bounded by $t$, we construct a framework for both vertex and edge deletion versions where approximation algorithms for these problems can be obtained from approximation algorithms for natural graph partitioning problems called $k$-Subset Vertex Separator and $k$-Subset Edge Separator.
For the vertex deletion, our framework, combined with the previous best result for $k$-Subset Vertex Separator, yields improved approximation ratios for fundamental problems such as $k$-Treewidth Vertex Deletion and Planar-$F$ Vertex Deletion. For the edge deletion, we give improved approximation algorithms for $k$-Subset Edge Separator and their applications to various problems in bounded-degree graphs.
Joint work with Anupam Gupta, Jason Li, Pasin Manurangsi, and Michal Wlodarczyk.
Sang-il Oum (엄상일), Branch-depth: Generalizing tree-depth of graphs
We present a concept called the branch-depth of a connectivity function, that generalizes the tree-depth of graphs. Then we prove two theorems showing that this concept aligns closely with the notions of tree-depth and shrub-depth of graphs as follows. For a graph $G = (V,E)$ and a subset $A $ of $E$ we let $lambda_G (A)$ be the number of vertices incident with an edge in $A$ and an edge in $E setminus A$. For a subset $X$ of $V$, let $rho_G(X)$ be the rank of the adjacency matrix between $X$ and $V setminus X$ over the binary field. We prove that a class of graphs has bounded tree-depth if and only if the corresponding class of functions $lambda_G$ has bounded branch-depth and similarly a class of graphs has bounded shrub-depth if and only if the corresponding class of functions $rho_G$ has bounded branch-depth, which we call the rank-depth of graphs.
Furthermore we investigate various potential generalizations of tree-depth to matroids and prove that matroids representable over a fixed finite field having no large circuits are well-quasi-ordered by the restriction.
This is a joint work with Matt DeVos and O-joung Kwon.
August 2 Friday
Dabeen Lee (이다빈), t-perfect graphs and the stable set problem
A graph $G$ is called $t$-perfect if the stable set polytope of $G$ can be obtained after adding the odd cycle inequalities to the standard edge formulation for the problem. A motivation for studying $t$-perfect graphs is algorithmic: as the odd cycle inequalities can be separated in polynomial time, one can compute a maximum weight stable set in a $t$-perfect graph by an LP algorithm in polynomial time. There are rich classes of $t$-perfect graphs, but a complete characterization of $t$-perfect graphs is still open. Due to this, no graph-theoretic / combinatorial algorithm is known, although there is an algorithm for the unweighted case based on a combinatorial approximate LP algorithm. In this survey talk, I will (i) review classes of known $t$-perfect graphs, (ii) briefly explain the algorithm for the unweighted case and a possibility of extending it to the weighted case, and (iii) discuss some research directions towards finding a graph-theoretic algorithm for computing a maximum weight stable set in a $t$-perfect graph.
Participants (not including IBS researchers)

Pierre Aboulker, ENS Ulm, France
Rémy Belmonte, University of Electro-Communications, Japan
Benjamin Bergougnoux, University of Paris Diderot, France
Édouard Bonnet, ENS Lyon, France
Nick Brettell, Durham University, UK
Yixin Cao, Hong Kong Polytechnic University, China
Michael Dobbins, Binghamton University, USA
Chris Eppolito, Binghamton University, USA
Archontia Giannopoulou, National and Kapodistrian University of Athens, Greece
Mamadou M. Kante, University Clermont Auvergne, France
Eunjung Kim (김은정), LAMSADE-CNRS, France
Stefan Kratsch, Humboldt-Universität zu Berlin, Germany
O-joung Kwon (권오정), Incheon National University, Korea
Michael Lampis, Université Paris-Dauphine, France
Euiwoong Lee (이의웅), NYU, USA
Valia Mitsou, Université Paris-Diderot, France
Florian Sikora, University Paris Dauphine, France
Magnus Wahlström, Royal Holloway, University of London, UK

An invitation-only summer research program will be held in the summer of 2019. There will be 10-20 participants to work together at DIMAG. Talks are open.
Accommodation
Everyone will stay at the Daedeok Innopolis Guest House (대덕특구게스트하우스).

Address: 27-5, Expo-ro 123beon-gil, Yuseong-gu, Daejeon, 34125, Republic of Korea (대전광역시 유성구 엑스포로 123번길 27-5)
Tel: (+82)-042-865-2500

Organizers

Eunjung Kim (김은정), LAMSADE-CNRS, France
Sang-il Oum (엄상일), IBS Discrete Mathematics Group and KAIST, Korea

Dabeen Lee (이다빈), Integrality of set covering polyhedra and clutter minors
2019-07-16 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Given a finite set of elements $V$ and a family $mathcal{C}$ of subsets of $V$, the set covering problem is to find a minimum cardinality subset of $V$ intersecting every subset in the family $mathcal{C}$. The set covering problem, also known as the hitting set problem, admits a simple integer linear programming formulation. The constraint system of the integer linear programming formulation defines a polyhedron, and we call it the set covering polyhedron of $mathcal{C}$. We say that a set covering polyhedron is integral if every extreme point is an integer lattice point. Although the set covering problem is NP-hard in general, conditions under which the problem becomes polynomially solvable have been studied. If the set covering polyhedron is integral, then it is straightforward that the problem can be solved using a polynomial-time algorithm for linear programming.
In this talk, we will focus on the question of when the set covering polyhedron is integral. We say that the family $mathcal{C}$ is a clutter if every subset in $mathcal{C}$ is inclusion-wise minimal. As taking out non-minimal subsets preserves integrality, we may assume that $mathcal{C}$ is a clutter. We call $mathcal{C}$ ideal if the set covering polyhedron of it is integral. To understand when a clutter is ideal, the notion of clutter minors is important in that $mathcal{C}$ is ideal if and only if so is every minor of it. We will study two fundamental classes of non-ideal clutters, namely, deltas and the blockers of extended odd holes. We will characterize when a clutter contains either a delta or the blocker of an extended odd hole as a minor.
This talk is based on joint works with Ahmad Abdi and Gérard Cornuéjols.

Patrice Ossona de Mendez, A model theoretical approach to sparsity
2019-06-25 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
We discuss how the model theoretic notion of first-order transduction allows to define a notion of structural sparsity, and give some example of applications, like existence of low shrub-depth decompositions for tranductions of bounded expansion classes, characterization of transductions of classes with bounded pathwidth, decompositions of graphs with bounded rank-width into cographs.

Suil O (오수일), An odd [1,b]-factor in regular graphs from eigenvalues
2019-06-19 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
An odd $[1,b]$-factor of a graph is a spanning subgraph $H$ such that for every vertex $v in V(G)$, $1 le d_H(v) le b$, and $d_H(v)$ is odd. For positive integers $r ge 3$ and $b le r$, Lu, Wu, and Yang gave an upper bound for the third largest eigenvalue in an $r$-regular graph with even number of vertices to guarantee the existence of an odd [1,b]-factor.
In this talk, we improve their bound.
