Archive for the ‘2009’ Category

Sang-hyun Kim (김상현), On Gromov Conjecture and Topological Jigsaw Puzzle

Wednesday, December 23rd, 2009

(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
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).

Eun-Jung Kim (김은정), Solving MAX-r-SAT above a Tight Lower Bound

Monday, December 21st, 2009
Solving MAX-r-SAT above a Tight Lower Bound
Eun Jung Kim (김은정)
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) + 2O(k2) whether a given set of m clauses of size r admits a truth assignment that satisfies at least ((2r-1)m+k)/2r clauses. Our algorithm is based on a polynomial-time preprocessing procedure that reduces a problem instance to an equivalent algebraically represented problem with O(k2) 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.

Van Vu, Combinatorial problems in random matrix theory

Saturday, December 19th, 2009
Combinatorial problems in random matrix theory
Van H. Vu
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.

Uwe Schauz, Describing Polynomials as Equivalent to Explicit Solutions

Friday, November 27th, 2009
Describing Polynomials as Equivalent to Explicit Solutions
Uwe Schauz
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 P\vert_{I_1\times\cdots\times I_n} when only incomplete information about a polynomial P(X_1,\ldots,X_n) 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  P(X_1)\neq 0 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.

(Colloquium) Ken-ichi Kawarabayashi, The disjoint paths problem: Algorithm and Structure

Monday, November 9th, 2009
FYI (Department Colloquium)
The disjoint paths problem: Algorithm and Structure
Ken-ichi Kawarabayashi (河原林 健一)
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 (s1,t1),(s2,t2),…,(sk,tk) in G (which are sometimes called terminals). Are there disjoint paths P1,…,Pk in G such that Pi joins si and ti 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.