2014 Archives - Page 3 of 9 - KAIST Discrete Math Seminar KAIST Discrete Math Seminar

Archive for the ‘2014’ Category

Mamadou Moustapha Kanté, On the enumeration of minimal transversals in hypergraphs

Thursday, October 16th, 2014

On the enumeration of minimal transversals
in hypergraphs
(a.k.a. minimal dominating sets in graphs)

Mamadou Moustapha Kanté
Université Blaise Pascal, France

2014/10/28 Tuesday 4PM-5PM
Room 1409

A hypergraph on V is a collection E of a subsets of a ground set V. A transversal in a hypergraph H=(V,E) is a subset T of V that intersects every set in E. We are interested in an output-polynomial algorithm for listing the set (inclusion wise) minimal transversals in a given hypergraph (known as Hypergraph Dualization or Transversal Problem). An enumeration algorithm for a set C is an algorithm that lists the elements of C without repetitions; it is said output-polynomial if it can enumerate the set C in time polynomial in the size of C and the input. The Transversal problem is a fifty-year open problem and until now not so many tractable cases are known and has deep connections with several areas of computer science: dualization of monotone functions, data mining, artificial intelligence, etc.

In this talk I will review some known results. In particular I will show that the Transversal problem is polynomially reduced to the enumeration of minimal dominating sets in co-bipartite graphs. A dominating set in a graph is a subset of vertices that intersect the closed neighborhood of every vertex. This interesting connection, we hope, will help in solving the Transversal problem by bringing structural graph theory into this area. I will also review new graph classes where we obtain polynomial delay algorithm for listing the minimal dominating sets. The talk will emphasize on the known techniques rather than a listing of known tractable cases.

Tags:MamadouMoustaphaKanté
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

Matthieu Josuat-Verges, Ehrhart polynomials and Eulerian statistic on permutations

Sunday, October 5th, 2014

Ehrhart polynomials and Eulerian statistic on permutations

Matthieu Josuat-Verges
CNRS, France

2014/10/14 Tuesday 4PM-5PM
Room 3433

Consider a polytope P with integer vertices, then one can define its Ehrhart polynomial f(t) by counting integer points in t.P. After a change of basis, it becomes a polynomial with positive integer coefficients, called the h*-polynomial. It is then a problem to find the combinatorial meaning of these coefficients for special polytopes. For example, the n-dimensional hypercube gives the n-th Eulerian polynomial, counting descents in permutations. The goal of this work is to refine this result by considering slices of hypercube and considering descents and excedences in permutations, that are two different Eulerian statistics.

Tags:MatthieuJosuat-Verges
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

Seungsang Oh, Enumeration of multiple self-avoiding polygons in a confined square lattice

Tuesday, September 23rd, 2014

Enumeration of multiple self-avoiding polygons in a confined square lattice

Seungsang Oh (오승상)
Korea University

2014/10/07 *Tuesday 5PM-6PM*
Room 1409

$\mathbb{Z}_{m \times n}$ is the rectangle of size $m \times n$ in the square lattice. $p_{m \times n}$ denotes the cardinality of multiple self-avoiding polygons in $\mathbb{Z}_{m \times n}$ .

In this talk, we construct an algorithm producing the precise value of $p_{m \times n}$ for positive integers m,n that uses recurrence relations of state matrices which turn out to be remarkably efficient to count such polygons. $$ p_{m \times n} = \mbox{(1,1)-entry of the matrix } (X_m)^n -1$$ where the matrix $X_m$ is defined by $$ X_{k+1} = \left( \begin{array}{cc} X_k & O_k \\ O_k & X_k \end{array}\right) \ \ \mbox{and} \ \ \ O_{k+1} = \left( \begin{array}{cc} O_k & X_k \\ X_k & 0 \end{array} \right) $$ for $k=1, \cdots, m-1$ , with $1 \times 1$ matrices $X_1 = \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right)$ and $O_1 = \left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right)$ .

Tags:오승상
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

(Colloquium) Matt DeVos, On the structure of very small product sets

Monday, September 1st, 2014

FYI (Colloquium)

On the structure of very small product sets

Matt DeVos
Simon Fraser University, Canada

2014/09/25 Thursday 4:30PM – 5:30PM
Room 1501

(SLIDE)

Let A and B be finite nonempty subsets of a multiplicative group G, and consider the product set AB = { ab | a in A and b in B }. When |G| is prime, a famous theorem of Cauchy and Davenport asserts that |AB| is at least the minimum of {|G|, |A| + |B| – 1}. This lower bound was refined by Vosper, who characterized all pairs (A,B) in such a group for which |AB| < |A| + |B|. Kneser generalized the Cauchy-Davenport theorem by providing a natural lower bound on |AB| which holds in every abelian group. Shortly afterward, Kemperman determined the structure of those pairs (A,B) with |AB| < |A| + |B| in abelian groups. Here we present a further generalization of these results to arbitrary groups. Namely we generalize Kneser’s Theorem, and we determine the structure of those pairs with |AB| < |A| + |B| in arbitrary groups.

Tags:colloquium, MattDeVos
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

Seog-Jin Kim, Bipartite graphs whose squares are not chromatic-choosable

Sunday, August 31st, 2014

Bipartite graphs whose squares are not chromatic-choosable

Seog-Jin Kim
Konkuk University

2014/09/19 *Friday* 4PM-5PM
Room 3433

The square $G^2$ of a graph $G$ is the graph defined on $V(G)$ such that two vertices $u$ and $v$ are adjacent in $G^2$ if the distance between $u$ and $v$ in $G$ is at most 2. Let $\chi(H)$ and $\chi_{\ell}(H)$ be the chromatic number and the list chromatic number of $H$ , respectively. A graph $H$ is called ${chromatic-choosable}$ if $\chi_{\ell} (H) = \chi(H)$ . It is an interesting problem to find graphs that are chromatic-choosable.

Motivated by the List Total Coloring Conjecture, Kostochka and Woodall (2001) proposed the List Square Coloring Conjecture which states that $G^2$ is chromatic-choosable for every graph $G$ . Recently, Kim and Park showed that the List Square Coloring Conjecture does not hold in general by finding a family of graphs whose squares are complete multipartite graphs with partite sets of unbounded size. It is a well-known fact that the List Total Coloring Conjecture is true if the List Square Coloring Conjecture holds for special class of bipartite graphs. On the other hand, the counterexamples to the List Square Coloring Conjecture are not bipartite graphs. Hence a natural question is whether $G^2$ is chromatic-choosable or not for every bipartite graph $G$ .

In this paper, we give a bipartite graph $G$ such that $\chi_{\ell} (G^2) \neq \chi(G^2)$ . Moreover, we show that the value $\chi_{\ell}(G^2) - \chi(G^2)$ can be arbitrarily large. This is joint work with Boram Park.

Tags:김석진
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

KAIST Discrete Math Seminar