Discrete Mathematics Group

Lars Jaffke, A complexity dichotomy for critical values of the b-chromatic number of graphs
2019-05-20 16:30 - 17:30 (Asia/Seoul) | Room B232, IBS (기초과학연구원)
A $b$-coloring of a graph $G$ is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The $b$-Coloring problem asks whether a graph $G$ has a $b$-coloring with $k$ colors.
The $b$-chromatic number of a graph $G$, denoted by $chi_b(G)$, is the maximum number $k$ such that $G$ admits a $b$-coloring with $k$ colors. We consider the complexity of the $b$-Coloring problem, whenever the value of $k$ is close to one of two upper bounds on $chi_b(G)$: The maximum degree $Delta(G)$ plus one, and the $m$-degree, denoted by $m(G)$, which is defined as the maximum number $i$ such that $G$ has $i$ vertices of degree at least $i-1$. We obtain a dichotomy result stating that for fixed $k in{Delta(G) + 1 − p, m(G) − p}$, the problem is polynomial-time solvable whenever $pin{0, 1}$ and, even when $k = 3$, it is NP-complete whenever $p ge 2$.
We furthermore consider parameterizations of the $b$-Coloring problem that involve the maximum degree $Delta(G)$ of the input graph $G$ and give two FPT-algorithms. First, we show that deciding whether a graph G has a $b$-coloring with $m(G)$ colors is FPT parameterized by $Delta(G)$. Second, we show that $b$-Coloring is FPT parameterized by $Delta(G) + ell_k(G)$, where $ell_k(G)$ denotes the number of vertices of degree at least $k$.
This is joint work with Paloma T. Lima.

Xin Zhang (张欣), On equitable tree-colorings of graphs
2019-05-16 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
An equitable tree-$k$-coloring of a graph is a vertex coloring using $k$ distinct colors such that every color class (i.e, the set of vertices in a common color) induces a forest and the sizes of any two color classes differ by at most one. The minimum integer $k$ such that a graph $G$ is equitably tree-$k$-colorable is the equitable vertex arboricity of $G$, denoted by $va_{eq}(G)$. A graph that is equitably tree-$k$-colorable may admits no equitable tree-$k’$-coloring for some $k’>k$. For example, the complete bipartite graph $K_{9,9}$ has an equitable tree-$2$-coloring but is not equitably tree-3-colorable. In view of this a new chromatic parameter so-called the equitable vertex arborable threshold is introduced. Precisely, it is the minimum integer $k$ such that $G$ has an equitable tree-$k’$-coloring for any integer $k’geq k$, and is denoted by $va_{eq}^*(G)$. The concepts of the equitable vertex arboricity and the equitable vertex arborable threshold were introduced by J.-L. Wu, X. Zhang and H. Li in 2013. In 2016, X. Zhang also introduced the list analogue of the equitable tree-$k$-coloring. There are many interesting conjectures on the equitable (list) tree-colorings, one of which, for example, conjectures that every graph with maximum degree at most $Delta$ is equitably tree-$k$-colorable for any integer $kgeq (Delta+1)/2$, i.e, $va_{eq}^*(G)leq lceil(Delta+1)/2rceil$. In this talk, I review the recent progresses on the studies of the equitable tree-colorings from theoretical results to practical algorithms, and also share some interesting problems for further research.

Sang June Lee (이상준), On strong Sidon sets of integers
2019-05-08 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Let $mathbb N$ be the set of natural numbers. A set $Asubset mathbb N$ is called a Sidon set if the sums $a_1+a_2$, with $a_1,a_2in S$ and $a_1leq a_2$, are distinct, or equivalently, if [|(x+w)-(y+z)|geq 1] for every $x,y,z,win S$ with $x<yleq z<w$. We define strong Sidon sets as follows:
For a constant $alpha$ with $0leq alpha<1$, a set $Ssubset mathbb N$ is called an $alpha$-strong Sidon set if [|(x+w)-(y+z)|geq w^alpha] for every $x,y,z,win S$ with $x<yleq z<w$.
The motivation of strong Sidon sets is that a strong Sidon set generates many Sidon sets by altering each element a bit. This infers that a dense strong Sidon set will guarantee a dense Sidon set contained in a sparse random subset of $mathbb N$.
In this talk, we are interested in how dense a strong Sidon set can be. This is joint work with Yoshiharu Kohayakawa, Carlos Gustavo Moreira and Vojtěch Rödl.

Rose McCarty, Circle graphs are polynomially chi-bounded
2019-04-26 16:00 - 17:00 | Room B232, IBS (기초과학연구원)
Circle graphs are the intersection graphs of chords on a circle; vertices correspond to chords, and two vertices are adjacent if their chords intersect. We prove that every circle graph with clique number k has chromatic number at most $4k^2$. Joint with James Davies.

Jon-Lark Kim (김종락), Introduction to Boolean functions with Artificial Neural Network
2019-04-18 11:00 - 12:00 | Room B232, IBS (기초과학연구원)
A Boolean function is a function from the set Q of binary vectors of length n (i.e., the binary n-dimensional hypercube) to $F_2={0,1}$. It has several applications to complexity theory, digital circuits, coding theory, and cryptography.
In this talk we give a connection between Boolean functions and Artificial Neural Network. We describe how to represent Boolean functions by Artificial Neural Network including linear and polynomial threshold units and sigmoid units. For example, even though a linear threshold function cannot realize XOR, a polynomial threshold function can do it. We also give currently open problems related to the number of (Boolean) linear threshold functions and polynomial threshold functions.

Andreas Holmsen, Large cliques in hypergraphs with forbidden substructures
2019-03-12 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
A result due to Gyárfás, Hubenko, and Solymosi, answering a question of Erdős, asserts that if a graph $G$ does not contain $K_{2,2}$ as an induced subgraph yet has at least $cbinom{n}{2}$ edges, then $G$ has a complete subgraph on at least $frac{c^2}{10}n$ vertices. In this paper we suggest a “higher-dimensional” analogue of the notion of an induced $K_{2,2}$, which allows us to extend their result to $k$-uniform hypergraphs. Our result also has interesting consequences in topological combinatorics and abstract convexity, where it can be used to answer questions by Bukh, Kalai, and several others.

2019-1 IBS Workshop on Graph Theory
2019-02-11 - 2019-02-12 | Room B234, IBS (기초과학연구원)
Invited Speakers

Jeong Han Kim (김정한), KIAS, Seoul
Martin Balko, Charles University, Prague
Dániel Gerbner, Alfréd Rényi Institute of Mathematics, Budapest
Cory T. Palmer, University of Montana, Missoula
Boram Park (박보람), Ajou University
Dong Yeap Kang (강동엽), KAIST

Schedule
Feb. 11, 2019, Monday
1:30pm-2:20pm Jeong Han Kim: Entropy and sorting
2:20pm-3:10pm Cory T. Palmer: Generalized Turán problems – Berge hypergraphs
Coffee Break
4:00pm-4:50pm Martin Balko: Ramsey numbers of edge-ordered graphs
4:50pm-5:40pm Dong Yeap Kang: On the rational Turán exponents conjecture
Banquet
Feb. 12, 2019, Tuesday
9:30am-10:20am Boram Park: Sum-free set problem on integers
Coffee Break
11:00am-11:50am Dániel Gerbner: Generalized Turán problems – counting subgraphs
Lunch
We plan to provide meals to all participants and provide a room at a near-by hotel for invited speakers and selected participants. Please register in the following form below by January 28, Monday; please register early if you want to receive the support for the accommodation.
Abstracts
Jeong Han Kim (김정한), Entropy and Sorting
We reconsider the old problem of sorting under partial information, and give polynomial time algorithms for the following tasks: (1) Given a partial order P, find (adaptively) a sequence of comparisons (questions of the form, “is x < y?”) which sorts ( i.e., finds an unknown linear extension of) P using O(log(e(P))) comparisons in worst case (where e(P) is the number of linear extensions of P). (2) Compute (on line) answers to any comparison algorithm for sorting a partial order P which force the algorithm to use Ω(log(e(P))) comparisons. (3) Given a partial order P of size n, estimate e(P) to within a factor exponential in n. (We give upper and lower bounds which differ by the factor $n^n /n!$.) Our approach, based on entropy of the comparability graph of P and convex minimization via the ellipsoid method, is completely different from earlier attempts to deal with these questions.
Joint work with J. Kahn.
Cory T. Palmer, Generalized Turán problems – Berge hypergraphs
Let $F$ be a graph. We say that a hypergraph $H$ is a Berge-$F$ if there is a bijection $f : E(F) rightarrow E(H )$ such that $e subseteq f(e)$ for every $e in E(F)$. Note that Berge-$F$ actually denotes a class of hypergraphs. The maximum number of edges in an $n$-vertex $r$-graph with no subhypergraph isomorphic to any Berge-$F$ is denoted $operatorname{ex}_r(n,textrm{Berge-}F)$. Observe that when $r=2$, then a Berge-$F$ is simply the graph $F$ and thus again we! are investigating the Tur’an function $operatorname{ex}(n,F)$.
In this talk we will survey results on the function $operatorname{ex}_r(n,textrm{Berge-}F)$ for various graphs $F$. We will also describe several interesting open problems.
Martin Balko, Ramsey numbers of edge-ordered graphs
An edge-ordered graph is a graph with linearly ordered set of edges. We introduce and study Ramsey numbers of edge-ordered graphs, called edge-ordered Ramsey numbers. We prove some basic properties of these numbers for general edge! -ordered graphs and we provide some stronger estimates for special classes of edge-ordered graphs. We also pose some new open problems and compare edge-ordered Ramsey numbers with the standard Ramsey numbers of graphs and with ordered Ramsey numbers, which are Ramsey numbers for graphs with linearly ordered vertex sets.
Joint work with Mate Vizer.
Dong Yeap Kang (강동엽), On the rational Turán exponents conjecture
The extremal number ${rm ex}(n,F)$ of a graph $F$ is the maximum number of edges in an $n$-vertex graph not containing $F$ as a subgraph. A real number $r in [1,2]$ is realisable if there exists a graph $F$ with ${rm ex}(n , F) = Theta(n^r)$. Several decades ago, Erdős and Simonovits conjectured that every rational number in $[1,2]$ is realisable. Despite decades of effort, the only known realisable numbers are $1,frac{7}{5},2$, and the numbers of the form $1+frac{1}{m}$, $2-frac{1}{m}$, $2-frac{2}{m}$ for integers $m geq 1$. In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than two numbers 1 and 2.
We discuss some recent progress on the conjecture of Erdős and Simonovits. First, we show that $2 – frac{a}{b}$ is realisable for any integers $a,b geq 1$ with $b>a$ and $b equiv pm 1 ~({rm mod}:a)$. This includes all previously known ones, and gives infinitely many limit points $2-frac{1}{m}$ in the set of all realisable numbers as a consequence.
Secondly, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own, we show that, somewhat surprisingly, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable.
This is joint work with Jaehoon Kim and Hong Liu.
Boram Park (박보람), Sum-free set problem on integers
For an abelian group $G$, a set $A subset G$ is sum-free if there are no $x, y, z in A$ such that $x + y = z$. Sum-free sets was initiated by Schur (1916) by an attempt to prove the famous Fermat’s Last Theorem. Since then, there have been intensive and fruitful research in the field of additive combinatorics. One of great interest in the study of sum-free sets is to consider sum-free subsets of a set of integers, which has attracted a significant attention in the literature over the years.
In this talk, some recent results on sum-free sets of integers are discussed. Then we present a result on $k$-sum $bf{n}$-free set, where $bf{n}$ is an $n$-dimensional integer vector. The work is based on joint work with Ilkyoo Choi and Ringi Kim.
Dániel Gerbner, Generalized Turán problems – counting subgraphs
Given two graphs $H$ and $F$, our goal is to determine the maximum number of copies of $H$ in an $F$-free graph on $n$ vertices. The systematic research of these problems was initiated (after several sporadic results) by Alon and Shikhelman. I describe several results of mine in this area, with different sets of co-authors.
Joint work with Ervin Győri, Abhishek Methuku, Cory Palmer and Mate Vizer.

Seog-Jin Kim (김석진), Signed colouring and list colouring of k-chromatic graphs
2019-01-28 16:00 - 17:00 | Room B232, IBS (기초과학연구원)
A signed graph is a pair (G, σ), where G is a graph and σ: E(G) → {1,-1} is a signature of G. A set S of integers is symmetric if I∈S implies that -i∈S. A k-colouring of (G,σ) is a mapping f:V(G) → Nk such that for each edge e=uv, f(x)≠σ(e) f(y), where Nk is a symmetric integer set of size k. We define the signed chromatic number of a graph G to be the minimum integer k such that for any signature σ of G, (G, σ) has a k-colouring.
Let f(n,k) be the maximum signed chromatic number of an n-vertex k-chromatic graph. This paper determines the value of f(n,k) for all positive integers n ≥ k. Then we study list colouring of signed graphs. A list assignment L of G is called symmetric if L(v) is a symmetric integer set for each vertex v. The weak signed choice number ch±w(G) of a graph G is defined to be the minimum integer k such that for any symmetric k-list assignment L of G, for any signature σ on G, there is a proper L-colouring of (G, σ). We prove that the difference ch±w(G)-χ±(G) can be arbitrarily large. On the other hand, ch±w(G) is bounded from above by twice the list vertex arboricity of G. Using this result, we prove that ch±w(K2⋆n)= χ±(K2⋆n) = ⌈2n/3⌉ + ⌊2n/3⌋. This is joint work with Ringi Kim and Xuding Zhu.

Eun Jung Kim (김은정), New algorithm for multiway cut guided by strong min-max duality
2019-01-04 16:00 - 17:00 | Room B232, IBS (기초과학연구원)
Problems such as Vertex Cover and Multiway Cut have been well-studied in parameterized complexity. Cygan et al. 2011 drastically improved the running time of several problems including Multiway Cut and Almost 2SAT by employing LP-guided branching and aiming for FPT algorithms parameterized above LP lower bounds. Since then, LP-guided branching has been studied in depth and established as a powerful technique for parameterized algorithms design.
In this talk, we make a brief overview of LP-guided branching technique and introduce the latest results whose parameterization is above even stronger lower bounds, namely μ(I)=2LP(I)-IP(dual-I). Here, LP(I) is the value of an optimal fractional solution and IP(dual-I) is the value of an optimal integral dual solution. Tutte-Berge formula for Maximum Matching (or equivalently Edmonds-Gallai decomposition) and its generalization Mader’s min-max formula are exploited to this end. As a result, we obtain an algorithm running in time 4k-μ(I) for multiway cut and its generalizations, where k is the budget for a solution.
This talk is based on a joint work with Yoichi Iwata and Yuichi Yoshida from NII.

Joonkyung Lee (이준경), Sidorenko’s conjecture for blow-ups
2019-01-03 16:00 - 17:00 | Room B232, IBS (기초과학연구원)
A celebrated conjecture of Sidorenko and Erdős–Simonovits states that, for all bipartite graphs H, quasirandom graphs contain asymptotically the minimum number of copies of H taken over all graphs with the same order and edge density. This conjecture has attracted considerable interest over the last decade and is now known to hold for a broad range of bipartite graphs, with the overall trend saying that a graph satisfies the conjecture if it can be built from simple building blocks such as trees in a certain recursive fashion.
Our contribution here, which goes beyond this paradigm, is to show that the conjecture holds for any bipartite graph H with bipartition A∪B where the number of vertices in B of degree k satisfies a certain divisibility condition for each k. As a corollary, we have that for every bipartite graph H with bipartition A∪B, there is a positive integer p such that the blow-up HAp formed by taking p vertex-disjoint copies of H and gluing all copies of A along corresponding vertices satisfies the conjecture. Joint work with David Conlon.

Hong Liu, Polynomial Schur’s Theorem
2018-12-13 17:00 - 18:00 | Room B109, IBS (기초과학연구원)
I will discuss the Ramsey problem for {x,y,z:x+y=p(z)} for polynomials p over ℤ. This is joint work with Peter Pach and Csaba Sandor.

Tony Huynh, A tight Erdős-Pósa function for planar minors
2018-12-10 17:00 - 18:00 | Room B109, IBS (기초과학연구원)
Let H be a planar graph. By a classical result of Robertson and Seymour, there is a function f(k) such that for all k and all graphs G, either G contains k vertex-disjoint subgraphs each containing H as a minor, or there is a subset X of at most f(k) vertices such that G−X has no H-minor. We prove that this remains true with f(k)=ck log k for some constant c depending on H. This bound is best possible, up to the value of c, and improves upon a recent bound of Chekuri and Chuzhoy. The proof is constructive and yields the first polynomial-time O(log 𝖮𝖯𝖳)-approximation algorithm for packing subgraphs containing an H-minor.
This is joint work with Wouter Cames van Batenburg, Gwenaël Joret, and Jean-Florent Raymond.
