(Joint Topology & Discrete Math Seminar)

Dept. of Mathematics, University of Texas at Austin, Austin, Texas

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

(Joint Topology & Discrete Math Seminar)

On Gromov Conjecture and Topological Jigsaw Puzzle

Sang-hyun Kim

Dept. of Mathematics, University of Texas at Austin, Austin, Texas

Dept. of Mathematics, University of Texas at Austin, Austin, Texas

2009/12/28 Mon, 4PM-5PM

Inspired by the famous virtual Haken conjecture in 3–manifold theory, Gromov asked whether every one-ended word-hyperbolic group contains a surface group. One simple, but still captivating case, is when the word-hyperbolic group is given as the double of a free group with a cyclic edge group. In the first part of the talk, I will describe the polygonality of a word in a free group, and a relation between polygonality and Gromov’s question. Polygonality is a combinatorial property, which is very much like solving a “topological jigsaw puzzle”. In the second part, I will describe a reduction to a purely (finite) graph theoretic conjecture using the Whitehead graph. Part I is a joint word with Henry Wilton (Caltech).

Solving MAX-r-SAT above a Tight Lower Bound

Eun Jung Kim (김은정)

Dept. of Computer Science, Royal Holloway, University of London, Egham, UK.

Dept. of Computer Science, Royal Holloway, University of London, Egham, UK.

2009/12/23 Wed, 4PM-5PM (Room 2411)

We consider the problem Max-r-SAT, an extensively studied variant of the classic satisfiability problem. Given an instance of CNF (Conjunctive normal form) in which each clause consists of exactly r literals, we seek to find a satisfying truth assignment that maximizes the number of satisfied clauses. Even when r=2, the problem is intractable unless P=NP. Hence the next quest is how close we can get to optimality with moderate usage of computation time/space.

We present an algorithm that decides, for every fixed r≥2 in time O(m) + 2^{O(k2)} whether a given set of m clauses of size r admits a truth assignment that satisfies at least ((2^{r}-1)m+k)/2^{r} clauses. Our algorithm is based on a polynomial-time preprocessing procedure that reduces a problem instance to an equivalent algebraically represented problem with O(k^{2}) variables. Moreover, by combining another probabilistic argument with tools from graph matching theory and signed graphs, we show that an instance of Max-2-Sat either is a YES-instance or can be transformed into an equivalent instance of size at most 3k.

This is a joint work with Noga Alon, Gregory Gutin, Stefan Szeider, and Anders Yeo.

Combinatorial problems in random matrix theory

Van H. Vu

Dept. of Mathematics, Rutgers University, New Jersey, USA

Dept. of Mathematics, Rutgers University, New Jersey, USA

2009/12/21 Mon, 3PM-4PM (E6-1, Room 2412)

I am going to give a survey on several basic problems of combinatorial nature concerning random Bernoulli matrices, including:

(1) The singularity problem: What is the probability that a random Bernoulli matrix is singular?

(2) The determinant problem: What is the typical value of the determinant?

(3) The permanent problem: What is the typical value of the permanent?

(4) The eigenvector problem: How does a typical eigenvector look like?

If time allows, I will discuss connections to other areas of mathematics, most importantly additive combinatorics.

Describing Polynomials as Equivalent to Explicit Solutions

Uwe Schauz

Department of Mathematics and Statistics, King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia

Department of Mathematics and Statistics, King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia

2009/12/*2 Wednesday* 4PM-5PM

We present a coefficient formula which provides some information about the polynomial map when only incomplete information about a polynomial is given. It is an integrative generalization and sharpening of several known results and has many applications, among these are:

1. The fact that polynomials in just one variable have at most deg(P) roots.

2. Alon and Tarsi’s Combinatorial Nullstellensatz.

3. Chevalley and Warning’s Theorem about the number of simultaneous zeros of systems of polynomials over finite fields.

4. Ryser’s Permanent Formula.

5. Alon’s Permanent Lemma.

6. Alon and Tarsi’s Theorem about orientations and colorings of graphs.

7. Scheim’s formula for the number of edge n-colorings of planar n-regular graphs.

8. Alon, Friedland and Kalai’s Theorem about regular subgraphs.

9. Alon and Füredi’s Theorem about cube covers.

10. Cauchy and Davenport’s Theorem from additive number theory.

11. Erdős, Ginzburg and Ziv’s Theorem from additive number theory.

The disjoint paths problem: Algorithm and Structure

Ken-ichi Kawarabayashi (河原林 健一)

National Institute of Informatics, Tokyo, Japan.

National Institute of Informatics, Tokyo, Japan.

2009/11/26 Thursday 4:30PM-5:30PM (Room 1501)

In this talk, we shall discuss the following well-known problem, which

is called the *disjoint paths problem*.

Given a graph G with n vertices and m edges, k pairs of vertices (s

_{1},t_{1}),(s_{2},t_{2}),…,(s_{k},t_{k}) in G (which are sometimes calledterminals). Are there disjoint paths P_{1},…,P_{k}in G such that P_{i}joins s_{i}and t_{i}for i=1,2,…,k?

We discuss recent progress on this topic, including algorithmic aspect of the disjoint paths problem.

We also discuss some structure theorems without the k disjoint paths. Topics include the uniquely linkage problem and the connectivity function that guarantees the existence of the k disjoint paths.