KAIST Discrete Math Seminar

We present an approach for structured integer programs that solves well-chosen restrictions of the problem to produce high-quality solutions quickly. Column generation is used both for automatically generating the restrictions and for producing bounds on the value of an optimal solution. We present computational experience for fixed-charge multi-commodity flow and inventory routing problems.

A path cover of a graph is a set of disjoint paths such that every vertex in the graph appears in one of the paths. We prove an upper bound for the minimum size of a path cover in a connected 4-regular graph with n vertices, confirming a conjecture by Graffiti.pc. We also determine the minimum number of vertices in a connected k-regular graph that is not Hamiltonian, and we solve the analogous problem for Hamiltonian paths.
This is a partly joint work with Gexin Yu and Rui Xu.

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 sets of coins (queries) 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≥2 and the weight w(c) of each counterfeit coin c satisfies α≤|w(c)|≤β for fixed constants α, β>0. The query complexity of the algorithm is O((m log n)/log m), which is optimal up to a constant factor. The algorithm uses, in part, random walks.
We will also discuss the problem of finding edges of a hidden weighted graph using a certain type of queries.

In this talk I will discuss two problems of Andries Brouwer.
In the first one he asked whether the minimal number of vertices you need to delete from a strongly regular graph with valency k and intersection numbers λ, μ, in order to disconnect it and such that each resulting component has at least two vertices is 2k-2-λ. We will show that there are strongly where you can use a smaller number of vertices to disconnect it in this way, but we also will give some positive results.
The second question we discuss is how connected a distance-regular graph is far from a fixed vertex.
This is joint work with Sebastian Cioaba and Kijung Kim.

The cycle counting rook numbers, hit numbers, and q-rook numberes and q-hit numbers have been studied by many people, and Briggs and Remmel introduced the theory of p-rook and p-hit numbers which is a rook theory model of the weath product of the cyclic group C_p and the symmetric group S_n.
We extend the cycle-counting q-rook numberes and q-hit numbers to the Briggs-Remmel model. In such a settinig, we define multivariable version of the cycle-counting q-rook numbers and cycle-counting q-hit numbers where we keep track of cycles of pernutation and partial permutation of C_p wearth product with S_n according to the signs of the cycles.
This work is a joint work with Jim Haglund at University of Pennsylvania and Jeff Remmel at UCSD.