NIMS

**4:30PM-5:30PM**

Room 1409

Seminar series on discrete mathematics @ Dept. of Mathematical Sciences, KAIST.

Enumeration of symmetric hex trees and the related polynomials

Hana Kim

NIMS

NIMS

2014/11/25 Tuesday **4:30PM-5:30PM**

Room 1409

Room 1409

A hex tree is an ordered tree of which each vertex has updegree 0, 1, or 2, and an edge from a vertex of updegree 1 is either left, median, or right. In this talk, we introduce an enumeration problem of symmetric hex trees and describe a bijection between symmetric hex trees and a certain class of supertrees. Some algebraic properties of the polynomials arising in this procedure also will be discussed.

Generalized Davenport-Schinzel Sequences: Regaining Linearity

Bryan Wilkinson

Aarhus University, Danmark

Aarhus University, Danmark

2014/11/18 Tuesday 4PM-5PM

Room 1409

Room 1409

We prove the linearity (of the lengths) of some generalized Davenport-Schinzel sequences. Standard Davenport-Schinzel sequences of order 2 (avoiding abab) are linear, while those of order 3 (avoiding ababa) and higher can be superlinear. Our goal is to determine what pattern(s), in addition to ababa, must be forbidden to regain linearity. This work is motivated by an intriguing open problem: does the lower envelope of any set of degree 3 polynomials have linear complexity?

FYI (CS Colloquium)

How to Find Counterfeit Coins?

An Algorithmic Version

An Algorithmic Version

Jeong Han Kim

KIAS

KIAS

2014/11/17 Monday 4PM – 5:30PM

E3-1 CS Bldg. Room 1501

E3-1 CS Bldg. Room 1501

In this talk, we consider a well-known combinatorial search problem. Suppose that there are n identical looking coins and some of them are counterfeit. The weights of all authentic coins are the same and known a

priori. The weights of counterfeit coins vary but different from the weight of an authentic coin. Without loss of generality, we may assume the weight of authentic coins is 0. The problem is to find all counterfeit coins by weighing (queries) sets of coins on a spring scale. Finding the optimal number of queries is difficult even when there are only 2 counterfeit coins. We introduce a polynomial time randomized algorithm to find all counterfeit coins when the number of them is known to be at most \(m \geq 2\) and the weight \(w(c)\) of each counterfeit coin c satisfies \(\alpha \leq |w(c)| \leq \beta\) for fixed constants \(\alpha, \beta>0\). The query complexity of the algorithm is \(O(\frac{m \log n }{\log m})\), which is optimal up to a constant factor. The algorithm uses, in part, random walks. The algorithm may be generalized to find all edges of a hidden weighted graph using a similar type of queries. This graph finding algorithm has various applications including DNA sequencing.

priori. The weights of counterfeit coins vary but different from the weight of an authentic coin. Without loss of generality, we may assume the weight of authentic coins is 0. The problem is to find all counterfeit coins by weighing (queries) sets of coins on a spring scale. Finding the optimal number of queries is difficult even when there are only 2 counterfeit coins. We introduce a polynomial time randomized algorithm to find all counterfeit coins when the number of them is known to be at most \(m \geq 2\) and the weight \(w(c)\) of each counterfeit coin c satisfies \(\alpha \leq |w(c)| \leq \beta\) for fixed constants \(\alpha, \beta>0\). The query complexity of the algorithm is \(O(\frac{m \log n }{\log m})\), which is optimal up to a constant factor. The algorithm uses, in part, random walks. The algorithm may be generalized to find all edges of a hidden weighted graph using a similar type of queries. This graph finding algorithm has various applications including DNA sequencing.

The topology of restricted partition posets

JiYoon Jung

NIMS

NIMS

2014/11/04 Tuesday 4PM-5PM

Room 1409

Room 1409

For each composition \(\vec{c}\) we show that the order complex of the poset of pointed set partitions \(\Pi_{\vec{c}}^{\bullet}\) is a wedge of spheres of the same dimension with the multiplicity given by the number of permutations with descent composition \(\vec{c}\). Furthermore, the action of the symmetric group on the top homology is isomorphic to the Specht module \(S^B\) where \(B\) is a border strip associated to the composition. We also study the filter of pointed set partitions generated by a knapsack integer partition and show the analogous results on homotopy type and action on the top homology.

On the enumeration of minimal transversals

in hypergraphs

(a.k.a. minimal dominating sets in graphs)

in hypergraphs

(a.k.a. minimal dominating sets in graphs)

Mamadou Moustapha Kanté

Université Blaise Pascal, France

Université Blaise Pascal, France

2014/10/28 Tuesday 4PM-5PM

Room 1409

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.