Discrete Mathematics Group

Robert Ganian, Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions
2020-08-05 16:30 - 17:30 (Asia/Seoul) | Zoom ID: 869 4632 6610 (ibsdimag)
Integer Linear Programming (ILP) is among the most successful and general paradigms for solving computationally intractable optimization problems in computer science. ILP is NP-complete, and until recently we have lacked a systematic study of the complexity of ILP through the lens of variable-constraint interactions. This changed drastically in recent years thanks to a series of results that together lay out a detailed complexity landscape for the problem centered around the structure of graphical representations of instances. The aim of this talk is to summarize these recent developments and put them into context. Special attention will be paid to the structural parameter treedepth, and at the end of the talk we will also consider how treedepth can be used to design algorithms for problems beyond ILP.

June Huh (허준이), Kazhdan-Lusztig polynomials of graphs and matroids
2020-08-04 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
I will introduce Kazhdan-Lusztig polynomials of matroids and survey combinatorial and geometric theories built around them. The focus will be on the conjecture of Gedeon, Proudfoot, and Young that all zeros of the Kazhdan-Lusztig polynomial of a matroid lie on the negative real axis.

Akanksha Agrawal, Polynomial Kernel for Interval Vertex Deletion
2020-07-29 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
Given a graph G and an integer k, the Interval Vertex Deletion (IVD) problem asks whether there exists a vertex subset S of size at most k, such that G-S is an interval graph. A polynomial kernel for a parameterized problem is a polynomial time preprocessing algorithm that outputs an equivalent instance of the problem whose size is bounded by a polynomial function of the parameter. The existence of a polynomial kernel for IVD remained a well-known open problem in Parameterized Complexity. In this talk we look at a sketch of a polynomial kernel for the problem (with the solution size as the parameter). To illustrate one of the key ingredients of our kernel, we will look at a polynomial kernel for IVD, when parameterized by the vertex cover number.

Eun Jung Kim (김은정), Solving hard cut problems via flow-augmentation
2020-07-28 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
We present a new technique for designing fixed-parameter algorithms for graph cut problems in undirected graphs, which we call flow augmentation. Our technique is applicable to problems that can be phrased as a search for an (edge) $(s, t)$-cut of cardinality at most $k$ in an undirected graph $G$ with designated terminals s and t.
More precisely, we consider problems where an (unknown) solution is a set $Z subseteq E(G)$ of size at most $k$ such that

in $G−Z$, $s$ and $t$ are indistinct connected components,
every edge of $Z$ connects two distinct connected components of $G − Z$, and
if we define the set $Z_{s,t}subseteq Z$ as these edges $e in Z$ for which there exists an (s, t)-path P_e with $E(P_e) ∩ Z = {e}$, then $Z_{s,t}$ separates s from t.

We prove that in the above scenario one can in randomized time $k^O(1)(|V (G)| + |E(G)|)$ add a number of edges to the graph so that with $2^{O(k log k)}$ probability no added edge connects two components of $G − Z$ and $Z_{s,t}$ becomes a minimum cut between $s$ and $t$.
This additional property becomes a handy lever in applications. For example, consider the question of an $(s, t)$-cut of cardinality at most k and of minimum possible weight (assuming edge weights in $G$). While the problem is NP-hard in general, it easily reduces to the maximum flow / minimum cut problem if we additionally assume that k is the minimum possible cardinality an $(s, t)$-cut in G. Hence, we immediately obtain that the aforementioned problem admits an $2^{O(k log k)}n^O(1)$-time randomized fixed-parameter algorithm.
We apply our method to obtain a randomized fixed-parameter algorithm for a notorious “hard nut” graph cut problem we call Coupled Min-Cut. This problem emerges out of the study of FPT algorithms for Min CSP problems (see below), and was unamenable to other techniques for parameterized algorithms in graph cut problems, such as Randomized Contractions, Treewidth Reduction or Shadow Removal.
In fact, we go one step further. To demonstrate the power of the approach, we consider more generally the Boolean Min CSP(Γ)-problems, a.k.a. Min SAT(Γ), parameterized by the solution cost. This is a framework of optimization problems that includes problems such as Almost 2-SAT and the notorious l-Chain SAT problem. We are able to show that every problem Min SAT(Γ) is either (1) FPT, (2) W[1]-hard, or (3) able to express the soft constraint (u → v), and thereby also the min-cut problem in directed graphs. All the W[1]-hard cases were known or immediate, and the main new result is an FPT algorithm for a generalization of Coupled Min-Cut. In other words, flow-augmentation is powerful enough to let us solve every fixed-parameter tractable problem in the class, except those that explicitly encompass directed graph cuts.
This is a joint work with Stefan Kratsch, Marcin Pilipczuk and Magnus Wahlström.

Paloma T. Lima, Graph Square Roots of Small Distance from Degree One Graphs
2020-07-22 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
Given a graph class $mathcal{H}$, the task of the $mathcal{H}$-Square Root problem is to decide whether an input graph G has a square root H that belongs to $mathcal{H}$. We are interested in the parameterized complexity of the problem for classes $mathcal{H}$ that are composed by the graphs at vertex deletion distance at most $k$ from graphs of maximum degree at most one. That is, we are looking for a square root H that has a modulator S of size k such that H-S is the disjoint union of isolated vertices and disjoint edges. We show that different variants of the problems with constraints on the number of isolated vertices and edges in H-S are FPT when parameterized by k, by providing algorithms with running time $2^{2^{O(k)}}cdot n^{O(1)}$. We further show that the running time of our algorithms is asymptotically optimal and it is unlikely that the double-exponential dependence on k could be avoided. In particular, we prove that the VC-k Root problem, that asks whether an input graph has a square root with vertex cover of size at most k, cannot be solved in time $2^{2^{o(k)}}cdot n^{O(1)}$ unless the Exponential Time Hypothesis fails. Moreover, we point out that VC-k Root parameterized by k does not admit a subexponential kernel unless P=NP.
This is a joint work with Petr Golovach and Charis Papadopoulos.

Ilkyoo Choi (최일규), Flexibility of Planar Graphs
2020-07-21 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Oftentimes in chromatic graph theory, precoloring techniques are utilized in order to obtain the desired coloring result. For example, Thomassen’s proof for 5-choosability of planar graphs actually shows that two adjacent vertices on the same face can be precolored. In this vein, we investigate a precoloring extension problem formalized by Dvorak, Norin, and Postle named flexibility. Given a list assignment $L$ on a graph $G$, an $L$-request is a function on a subset $S$ of the vertices that indicates a preferred color in $L(v)$ for each vertex $vin S$. A graph $G$ is $varepsilon$-flexible for list size $k$ if given a $k$-list assignment $L$ and an $L$-request, there is an $L$-coloring of $G$ satisfying an $varepsilon$-fraction of the requests in $S$. We survey known results regarding this new concept, and prove some new results regarding flexibility of planar graphs.

Casey Tompkins, Inverse Turán Problems
2020-07-14 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
For given graphs $G$ and $F$, the Turán number $ex(G,F)$ is defined to be the maximum number of edges in an $F$-free subgraph of $G$. Briggs and Cox introduced a dual version of this problem wherein for a given number $k$, one maximizes the number of edges in a host graph $G$ for which $ex(G,H) < k$. We resolve a problem of Briggs and Cox in the negative by showing that the inverse Turán number of $C_4$ is $Theta(k^{3/2})$. More generally, we determine the order of magnitude of the inverse Turán number of $K_{s,t}$ for all $s$ and $t$. Addressing another problem of Briggs and Cox, we determine the asymptotic value of the inverse Turán number of the paths of length $4$ and $5$ and provide an improved lower bound for all paths of even length. We also obtain improved bounds on the inverse Turán number of even cycles
Joint work with Ervin Győri, Nika Salia and Oscar Zamora.

Seog-Jin Kim (김석진), Online DP-coloring of graphs
2020-07-07 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Online list coloring and DP-coloring are generalizations of list coloring that attracted considerable attention recently. Each of the paint number, $chi_P(G)$, (the minimum number of colors needed for an online coloring of $G$) and the DP-chromatic number, $chi_{DP}(G)$, (the minimum number of colors needed for a DP-coloring of $G$) is at least the list chromatic number, $chi_ell(G)$, of $G$ and can be much larger. On the other hand, each of them has a number of useful properties.
We introduce a common generalization, online DP-coloring, of online list coloring and DP-coloring and to study its properties. This is joint work with Alexandr Kostochka, Xuer Li, and Xuding Zhu.

Dennis Wong, Generating Gray codes and universal cycles for weak orders
2020-06-30 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
A weak order is a way to rank n objects where ties are allowed. Weak orders have applications in diverse areas such as linguistics, designing combination locks, and even in horse racing. In this talk, we present new and simple algorithms to generate Gray codes and universal cycles for weak orders.

Jaehoon Kim (김재훈), A resilience version of Pósa's theorem
2020-06-23 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Pósa’s theorem states that any graph G whose degree sequence $d_1leq dots leq d_n$ satisfies $d_i geq i+1$ for all $i< n/2$ has a Hamilton cycle. This degree condition is best possible. We show that a similar result holds for suitable subgraphs $G$ of random graphs. This is joint work with Padraig Condon, Alberto Espuny Diaz, Daniela Kühn and Deryk Osthus.

Andreas Holmsen, Fractional Helly and topological complexity
2020-06-16 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
The fractional Helly theorem is a simple yet remarkable generalization of Helly’s classical theorem on the intersection of convex sets, and it is of considerable interest to extend the fractional Helly theorem beyond the setting of convexity. In this talk I will discuss a recent result which shows that the fractional Helly theorem holds for families of subsets of $mathbb R^d$ which satisfy only very weak topological assumptions. The proofs combine a number of tools such as homological minors, stair-convexity, supersaturation in hypergraphs, Radon dimension, and Ramsey-type arguments. This is joint work with Xavier Goaoc and Zuzana Patáková.

Jiseung Kim (김지승), Hardness and concrete security in cryptography
2020-06-09 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Computationally hard problems have been widely used to construct cryptographic primitives such as encryptions, digital signatures. For example, provably secure primitives are based on a reduction from the hardness problems. However, the concrete instantiation of primitives does not follow the results of hardness problems due to its efficiency. In this talk, we introduce cryptographic hardness problems widely used in cryptography and the gap between hardness results and concrete security of cryptographic primitives based on our recent works.

Huy-Tung Nguyen, The average cut-rank of graphs
2020-06-02 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
The cut-rank of a set X of vertices in a graph G is defined as the rank of the X×(V(G)∖X) matrix over the binary field whose (i,j)-entry is 1 if the vertex i in X is adjacent to the vertex j in V(G)∖X and 0 otherwise. We introduce the graph parameter called the average cut-rank of a graph, defined as the expected value of the cut-rank of a random set of vertices. We show that this parameter does not increase when taking vertex-minors of graphs and a class of graphs has bounded average cut-rank if and only if it has bounded neighborhood diversity. This allows us to deduce that for each real α, the list of induced-subgraph-minimal graphs having average cut-rank larger than (or at least) α is finite. We further refine this by providing an upper bound on the size of obstruction and a lower bound on the number of obstructions for average cut-rank at most (or smaller than) α for each real α≥0. Finally, we describe explicitly all graphs of average cut-rank at most 3/2 and determine up to 3/2 all possible values that can be realized as the average cut-rank of some graph. This is joint work with Sang-il Oum.

Hong Liu (刘鸿), Asymptotic Structure for the Clique Density Theorem
2020-05-26 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
The famous Erdős-Rademacher problem asks for the smallest number of r-cliques in a graph with the given number of vertices and edges. Despite decades of active attempts, the asymptotic value of this extremal function for all r was determined only recently, by Reiher [Annals of Mathematics, 184 (2016) 683-707]. Here we describe the asymptotic structure of all almost extremal graphs. This task for r=3 was previously accomplished by Pikhurko and Razborov [Combinatorics, Probability and Computing, 26 (2017) 138–160].

O-joung Kwon (권오정), Mim-width: a width parameter beyond rank-width
2020-05-19 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Vatshelle (2012) introduced a width parameter called mim-width. It is based on the following cut function : for a vertex partition (A,B) of a graph, the complexity of this partition is computed by the size of a maximum induced matching of the bipartite subgraph induced by edges between A and B. This parameter naturally extends the expressibility power of the graph parameters clique-width and rank-width, which have been well-developed in recent years. In a series of papers, we explored the computational complexity of several problems, parameterized by mim-width. We summarize known structural properties and algorithmic applications of mim-width, and give some open problems at the end. This is joint work with Lars Jaffke, Torstein Strømme, and Jan Arne Telle.

Eun Jung Kim (김은정), Twin-width: tractable FO model checking
2020-05-12 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Inspired by a width invariant defined on permutations by Guillemot and Marx [SODA ’14], we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes, bounded rank-width graphs, map graphs, $K_t$-free unit $d$-dimensional ball graphs, posets with antichains of bounded size, and proper subclasses of dimension-2 posets all have bounded twin-width. On all these classes (except map graphs without geometric embedding) we show how to compute in polynomial time a sequence of $d$-contractions, witness that the twin-width is at most $d$. We show that FO model checking, that is deciding if a given first-order formula $phi$ evaluates to true for a given binary structure $G$ on a domain $D$, is FPT in $|phi|$ on classes of bounded twin-width, provided the witness is given. More precisely, being given a $d$-contraction sequence for $G$, our algorithm runs in time $f(d,|phi|) cdot |D|$ where $f$ is a computable but non-elementary function. We also prove that bounded twin-width is preserved by FO interpretations and transductions (allowing operations such as squaring or complementing a graph). This unifies and significantly extends the knowledge on fixed-parameter tractability of FO model checking on non-monotone classes, such as the FPT algorithm on bounded-width posets by Gajarský et al. [FOCS ’15].
In order to explore the limits of twin-width, we generalize to bounded twin-width classes a result by Norine et al. [JCTB ’06] stating that proper minor-free classes are small (i.e., they contain at most $n! c^n$ graphs on $n$ vertices, for some constant $c$). This implies by a counting argument that bounded-degree graphs, interval graphs, and unit disk graphs have unbounded twin-width.
Joint work with Stéphan Thomassé, Édouard Bonnet, and Rémi Watrigant.

KSIAM 2020 Spring Conference (cancelled)
2020-05-08 - 2020-05-09 | IBS Science Culture Center
KSIAM 2020 Spring Conference will be held at IBS from May 8, 2020 to May 9, 2020.
Organized by Korean Society for Industrial and Applied Mathematics.
Organizing Committee

Myungjoo Kang (Seoul National University) (chair)
Ahn, Jaemyung (KAIST)
Kwon, Hee-Dae (Inha University)
Lee, Eun Jung (Yonsei University)
Jang, Bongsoo (UNIST)
Jung, Miyoun (Hankuk University of Foreign Studies)
Kim, Junseok (Korea University)
Oum, Sang-il (IBS, KAIST)

Seunghun Lee (이승훈), Leray numbers of complexes of graphs with bounded matching number
2020-04-28 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Given a graph $G$ on the vertex set $V$, the non-matching complex of $G$, $mathsf{NM}_k(G)$, is the family of subgraphs $G’ subset G$ whose matching number $
u(G’)$ is strictly less than $k$. As an attempt to generalize the result by Linusson, Shareshian and Welker on the homotopy types of $mathsf{NM}_k(K_n)$ and $mathsf{NM}_k(K_{r,s})$ to arbitrary graphs $G$, we show that (i) $mathsf{NM}_k(G)$ is $(3k-3)$-Leray, and (ii) if $G$ is bipartite, then $mathsf{NM}_k(G)$ is $(2k-2)$-Leray. This result is obtained by analyzing the homology of the links of non-empty faces of the complex $mathsf{NM}_k(G)$, which vanishes in all dimensions $dgeq 3k-4$, and all dimensions $d geq 2k-3$ when $G$ is bipartite. As a corollary, we have the following rainbow matching theorem which generalizes the result by Aharoni et. al. and Drisko’s theorem: Let $E_1, dots, E_{3k-2}$ be non-empty edge subsets of a graph and suppose that $
u(E_icup E_j)geq k$ for every $i
e j$. Then $E=bigcup E_i$ has a rainbow matching of size $k$. Furthermore, the number of edge sets $E_i$ can be reduced to $2k-1$ when $E$ is the edge set of a bipartite graph.
This is a joint work with Andreas Holmsen.

Sang-il Oum (엄상일), Survey on vertex-minors
2020-04-21 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
For a vertex v of a graph G, the local complementation at v is an operation to obtain a new graph denoted by G*v from G such that two distinct vertices x, y are adjacent in G*v if and only if both x, y are neighbors of v and x, y are non-adjacent, or at least one of x, y is not a neighbor of v and x, y are adjacent. A graph H is a vertex-minor of a graph G if H is obtained from G by a sequence of local complementation and vertex deletions. Interestingly vertex-minors have been used in the study of measurement-based quantum computing on graph states.
Motivated by the big success of the graph minor structure theory developed deeply by Robertson and Seymour since 1980s, we propose a similar theory for vertex-minors. This talk will illustrate similarities between graph minors and graph vertex-minors and give a survey of known theorems and open problems on vertex-minors of graphs.

Casey Tompkins, Saturation problems in the Ramsey theory of graphs, posets and point sets
2020-04-14 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
In 1964, Erdős, Hajnal and Moon introduced a saturation version of Turán’s classical theorem in extremal graph theory. In particular, they determined the minimum number of edges in a $K_r$-free, $n$-vertex graph with the property that the addition of any further edge yields a copy of $K_r$. We consider analogues of this problem in other settings. We prove a saturation version of the Erdős-Szekeres theorem about monotone subsequences and saturation versions of some Ramsey-type theorems on graphs and Dilworth-type theorems on posets.
We also consider semisaturation problems, wherein we allow the family to have the forbidden configuration, but insist that any addition to the family yields a new copy of the forbidden configuration. In this setting, we prove a semisaturation version of the Erdős-Szekeres theorem on convex $k$-gons, as well as multiple semisaturation theorems for sequences and posets.
This project was joint work with Gábor Damásdi, Balázs Keszegh, David Malec, Zhiyu Wang and Oscar Zamora.

Pascal Gollin, Disjoint dijoins for classes of dibonds in finite and infinite digraphs
2020-04-07 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
A dibond in a directed graph is a bond (i.e. a minimal non-empty cut) for which all of its edges are directed to a common side of the cut. A famous theorem of Lucchesi and Younger states that in every finite digraph the least size of an edge set meeting every dicut equals the maximum number of disjoint dibonds in that digraph. We call such sets dijoins.
Woodall conjectured a dual statement. He asked whether the maximum number of disjoint dijoins in a digraph equals the minimum size of a dibond.
We study a modification of this question where we restrict our attention to certain classes of dibonds, i.e. whether for a class $mathfrak{B}$ of dibonds of a digraph the maximum number of disjoint edge sets meeting every dibond in $mathfrak{B}$ equal the size a minimum dibond in $mathfrak{B}$.
In particular, we verify this questions for nested classes of dibonds, for the class of dibonds of minimum size, and for classes of infinite dibonds.

Ringi Kim (김린기), The strong clique number of graphs with forbidden cycles
2020-03-31 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
The strong clique number of a graph $G$ is the maximum size of a set of edges of which every pair has distance at most two.
In this talk, we prove that every ${C_5,C_{2k}}$-free graph has strong clique number at most $kDelta(G)-(k-1)$, which resolves a conjecture by Cames van Batenburg et al. We also prove that every $C_{2k}$-free graph has strong clique number at most $(2k−1)Delta(G) + (2k−1)^2$, improving the previous known upper bound $10k^2 (Delta(G)-1)$ due to Cames van Batenburg et al. This is joint work with Eun-Kyung Cho, Ilkyoo Choi, and Boram Park.

Kevin Hendrey, Covering radius in the Hamming permutation space
2020-03-24 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Our problem can be described in terms of a two player game, played with the set $mathcal{S}_n$ of permutations on ${1,2,dots,n}$. First, Player 1 selects a subset $S$ of $mathcal{S}_n$ and shows it to Player 2. Next, Player 2 selects a permutation $p$ from $mathcal{S}_n$ as different as possible from the permutations in $S$, and shows it to Player 1. Finally, Player 1 selects a permutation $q$ from $S$, and they compare $p$ and $q$. The aim of Player 1 is to ensure that $p$ and $q$ differ in few positions, while keeping the size of $S$ small. The function $f(n,s)$ can be defined as the minimum size of a set $Ssubseteq mathcal{S}_n$ that Player 1 can select in order to gaurantee that $p$ and $q$ will differ in at most $s$ positions.
I will present some recent results on the function $f(n,s)$. We are particularly interested in determining the value $f(n,2)$, which would resolve a conjecture of Kézdy and Snevily that implies several famous conjectures for Latin squares. Here we improve the best known lower bound, showing that $f(n,2)geqslant 3n/4$. This talk is based on joint work with Ian M. Wanless.

Dabeen Lee (이다빈), On a generalization of the Chvátal-Gomory closure
2020-03-17 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Integer programming is the problem of optimizing a linear function over the set of integer solutions satisfying a system of inequalities. The most successful technique in practice is the so-called “cutting-plane” algorithm in combination with branch-and-bound enumeration. Cutting-planes for an integer linear program are linear inequalities that are valid for all integer feasible solutions but cut off intermediate fractional solutions.
The Chvátal-Gomory cuts, introduced by Gomory in 1958 and further studied by Chvátal in 1973 in relation to their applications in combinatorial optimization, are the first class of general-purpose cutting-planes in the literature. The split cuts, whose name was coined by Cook, Kannan, and Schrijver in 1980, are another class of important cutting-planes in modern integer programming. Although there are infinitely many cuts in each class, it is known that only finitely many of them are nonredundant, which is related to designing a finite-convergent cutting-plane algorithm. In this talk, we introduce a new class of cutting-planes that generalizes the Chvátal-Gomory cuts and generalizes a special case of the split cuts. As the two classic classes of cutting-planes, we show that only a finite number of cuts can be redundant.
This talk is based on a joint work with Sanjeeb Dash and Oktay Günlük.

Eun-Kyung Cho (조은경), Decomposition of a planar graph into a $d$-degenerate graph and a graph with maximum degree at most $h$
2020-03-03 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Given a graph $G$, a decomposition of $G$ is a collection of spanning subgraphs $H_1, ldots, H_t$ of $G$ such that each edge of $G$ is an edge of $H_i$ for exactly one $i in {1, ldots, t}$. Given a positive integer $d$, a graph is said to be $d$-degenerate if every subgraph of it has a vertex of degree at most $d$. Given a non-negative integer $h$, we say that a graph $G$ is $(d,h)$-decomposable if there is a decomposition of $G$ into two spanning subgraphs, where one is a $d$-degenerate graph, and the other is a graph with maximum degree at most $h$.
It is known that a planar graph is $5$-degenerate, but not always $4$-degenerate. This implies that a planar graph is $(5,0)$-decomposable, but not always $(4,0)$-decomposable. Moreover, by related previous results, it is known that a planar graph is $(3,4)$- and $(2,8)$-decomposable.
In this talk, we improve these results by showing that every planar graph is $(4,1)$-, $(3,2)$-, and $(2,6)$-decomposable. The $(4,1)$- and $(3,2)$-decomposabilities are sharp in the sense that the maximum degree condition cannot be reduced more.
This is joint work with Ilkyoo Choi, Ringi Kim, Boram Park, Tingting Shan, and Xuding Zhu.

Xin Zhang (张欣), On the equitable tree-coloring of graphs with low degeneracy
2020-02-25 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
A (vertex) $k$-coloring of a graph $G$ is a tree-coloring if each color class induces a forest, and is equitable if the sizes of any two color classes differ by at most 1. The first relative result concerning the equitable tree-coloring of graphs is due to H. Fan, H. A. Kierstead, G. Liu, T. Molla, J.-L. Wu, and X. Zhang (2011), who proved that any graph with maximum degree at most $Delta$ has a $Delta$-coloring so that each color class induces a graph with maximum degree at most 1. After that, many results on this topic were published in the literature. For example, L. Esperet, L. Lemoine, and F. Maffray (2015) showed that any planar graph admits an equitable tree-$k$-coloring for every integer $kge 4$，and G. Chen, Y. Gao, S. Shan, G. Wang, and J.-L. Wu (2017) proved that any 5-degenerate graph with maximum degree at most $Delta$ admits an equitable tree-$k$-coloring for every $kgeq lceilfrac{Delta+1}{2}rceil$.
In this talk, we review part of the known results and the conjectures on the equitable tree-coloring of graphs, and then show the sketch proofs of our three new results as follows:
(a) the vertex set of any graph $G$ can be equitably partitioned into $k$ subsets for any integer $kgeqmax{lceilfrac{Delta(G)+1}{2}rceil,lceilfrac{|G|}{4}rceil}$ so that each of them induces a linear forest;
(b) any plane graph with independent crossings admits an equitable tree-$k$-coloring for every integer $kge 8$;
(c) any $d$-degenerate graph with maximum degree at most $Delta$ admits an equitable tree-$k$-coloring for every integer $kgeq (Delta+1)/2$ provided that $Deltageq 10d$.
This is a joint work with Yuping Gao, Bi Li, Yan Li, and Bei Niu.

Dong Yeap Kang (강동엽), Fragile minor-monotone parameters under random edge perturbation
2020-02-18 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
We investigate how minor-monotone graph parameters change if we add a few random edges to a connected graph $H$. Surprisingly, after adding a few random edges, its treewidth, treedepth, genus, and the size of a largest complete minor become very large regardless of the shape of $H$. Our results are close to best possible for various cases. We also discuss analogous results for randomly perturbed bipartite graphs as well as the size of a largest complete odd minor in randomly perturbed graphs.

Dillon Mayhew, Courcelle's Theorem for hypergraphs
2020-01-28 16:30 - 17:30 | 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.
