Seminars in December 2009

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

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

  • Eun-Jung Kim (김은정), Solving MAX-r-SAT above a Tight Lower Bound
    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.

    Tags:

  • Van Vu, Combinatorial problems in random matrix theory
    Combinatorial problems in random matrix theory
    Van H. Vu
    Dept. of Mathematics</a>, 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.

    Tags:

  • Uwe Schauz, Describing Polynomials as Equivalent to Explicit Solutions
    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.

    Tags:

Monthly Archives