Jinyoung Park (박진영), The number of maximal independent sets in the Hamming cube

April 16th, 2019

IBS/KAIST Joint Discrete Math Seminar

The number of maximal independent sets in the Hamming cube
Jinyoung Park (박진영)
Department of Mathematics, Rutgers University, USA
2019/06/03 Monday 4:30PM-5:30PM (IBS, Room B232)
Let $Q_n$ be the $n$-dimensional Hamming cube (hypercube) and $N=2^n$. We prove that the number of maximal independent sets in $Q_n$ is asymptotically $2n2^{N/4}$, as was conjectured by Ilinca and Kahn in connection with a question of Duffus, Frankl and Rödl. The value is a natural lower bound derived from a connection between maximal independent sets and induced matchings. The proof of the upper bound draws on various tools, among them “stability” results for maximal independent set counts and old and new results on isoperimetric behavior in $Q_n$. This is joint work with Jeff Kahn.

Lars Jaffke, A complexity dichotomy for critical values of the b-chromatic number of graphs

April 16th, 2019

IBS/KAIST Joint Discrete Math Seminar

A complexity dichotomy for critical values of the b-chromatic number of graphs
Lars Jaffke
University of Bergen
2019/05/20 Mon 4:30PM-5:30PM (IBS, B232)
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 χ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 χb(G): The maximum degree Δ(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∈{Δ(G)+1−p,m(G)−p}, the problem is polynomial-time solvable whenever p∈{0,1} and, even when k=3, it is NP-complete whenever p≥2.
We furthermore consider parameterizations of the b-Coloring problem that involve the maximum degree Δ(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 Δ(G). Second, we show that b-Coloring is FPT parameterized by Δ(G)+ℓk(G), where ℓ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

April 16th, 2019

IBS/KAIST Joint Discrete Math Seminar

On equitable tree-colorings of graphs
Xin Zhang (张欣)
Xidian Univeristy, China
2019/05/16 4:30PM-5:30PM (IBS, B232)
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 vaeq(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 K9,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′≥k, and is denoted by vaeq(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 Δ is equitably tree-k-colorable for any integer k≥(Δ+1)/2, i.e, vaeq(G)≤⌈(Δ+1)/2⌉. 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

April 16th, 2019

IBS/KAIST Joint Discrete Math Seminar

On strong Sidon sets of integers
Sang June Lee
Duksung Women’s University, Seoul
2019/05/08 Wed 4:30PM-5:30PM (IBS, Room B232)
Let N be the set of natural numbers. A set A⊂N is called a Sidon set if the sums a1+a2, with a1,a2∈S and a1≤a2, are distinct, or equivalently, if
|(x+w)−(y+z)|≥1
for every x,y,z,w∈S with x<y≤z<w. We define strong Sidon sets as follows:

For a constant α with 0≤α<1, a set S⊂N is called an α-strong Sidon set if
|(x+w)−(y+z)|≥wα
for every x,y,z,w∈S with x<y≤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 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

April 16th, 2019

IBS/KAIST Joint Discrete Math Seminar

Circle graphs are polynomially chi-bounded
Rose McCarty
University of Waterloo, Waterloo, Canada
2019/04/26 Fri 4PM-5PM (IBS, Room B232)
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 4k2. Joint with James Davies.