GT Combinatorics Seminar
Fall 2001
- August 31 at 4:00 pm in Skiles 255
SPEAKER: Michael Lacey, Georgia Tech
TITLE: Large sets of integers not containing arithmetic progressions of
length 5
- September 7 at 4:00 pm in Skiles 255
SPEAKER: Balaji Gopalakrishnan, Georgia Tech
TITLE: Solving Linear Programs Using Least-Squares Methods
We will talk about some of the least-squares algorithms we have
developed for solving linear programming problems. This is a
joint work by Ellis Johnson, Joel Sokol and Earl Barnes.
- September 14 at 4:00 pm in Skiles 255
SPEAKER: Russell Lyons, Georgia Tech
TITLE: Matroids and Probability I
I will survey some new connections between matroids and probability theory.
Most of these new connections are inspired by studies of the uniform
probability measure on the spanning trees of a given finite connected
graph. This probability measure and variants have been intensively studied,
with many interesting connections to other areas of mathematics. Because
of the ubiquity of matroids, however, there are now connections emerging to
homology, group representations, ergodic theory, and phase transitions.
Many open questions remain. There are continuous analogues that are
heavily studied in the theory of random matrices, but I will stay on the
discrete side. No background knowledge will be assumed.
- September 21 at 4:00 pm in Skiles 255
SPEAKER: Russell Lyons, Georgia Tech
TITLE: Matroids and Probability II
This talk is a continuation of the one given the previous week (the
abstract is shown above).
- September 28 at 4:00 pm in Skiles 255
SPEAKER: Ehud Friedgut, Hebrew University of Jerusalem
TITLE: The use of a generalization of Szemeredi's regularity lemma
to hypergraphs in order to prove the existence of a sharp threshold
of a Ramsey property of random graphs.
In this talk we will present a proof of the existence of a
sharp threshold of a Ramsey property of random graphs by using a
generalization of Szemeredi's regularity lemma to hypergraphs.
Joint work with Rodl, Rucinski and Tetali.
- October 5 at 4:00 pm in Skiles 255
SPEAKER: Rajneesh Hegde, Georgia Tech
TITLE: Finding 3-shredders efficiently
A shredder in an undirected graph is a set of vertices
whose removal results in at least three components. A
3-shredder is a shredder of size three. We present an
algorithm that, given a 3-connected graph, finds its
3-shredders in time proportional to the number of
vertices and edges, when implemented on a random access
machine.
- October 12 at 4:00 pm in Skiles 255
SPEAKER: Kenichi Kawarabayashi, Vanderbilt University
TITLE: Hadwiger's Conjecture for $7$-chromatic graph
In 1943, Hadwiger made the conjecture that every $k$-chromatic graph has
a $K_k$-minor. This conjecture is, perhaps, the most interesting conjecture
of all graph theory. It is well known that the case $k=5$ is
equivalent to the Four Colour Theorem, as proved
by Wagner in 1937. About 60 years later,
Robertson, Seymour and Thomas proved that the case $k=6$ is
also equivalent to the Four Colour Theorem. So far, the cases
$k \geq 7$ are still open and we have little hope to verify even the case
$k=7$ up to now. In fact, there are only a few theorems concerning
$7$-chromatic graphs.
In this talk, we will present the following result:
Every $7$-chromatic graph contains $K_7$ or $K_{4,4}$ as a minor,
We prove this theorem
without using the Four Colour Theorem.
This result verifies the case $m=6,n=1$ of
the $(m,n)$-Minor Conjecture which is a weaken form of
the Hadwiger's Conjecture.
Also, we will present some related problems concerning
$7$-chromatic graphs.
This is joint work with B. Toft.
- October 19 at 4:00 pm in Skiles 255
SPEAKER: Ilse Fischer, University of Klagenfurt
TITLE: The hook-length formula for shifted tableaux
Whenever combinatorialists discover two sets ${\mathcal S, \mathcal T}$
of combinatorial objects with the same finite cardinality they suspect that
this fact is just the projection of a canonical bijection between ${\mathcal
S}$ and ${\mathcal T}$. More generally: If we have $h \cdot |{\mathcal S}| =
|{\mathcal T}|$, $h$ a positive integer, a canonical $h$ to $1$
surjection from ${\mathcal T}$ onto ${\mathcal S}$ could stand behind
this equation, i.e. a map which assigns exactly $h$ elements of ${\mathcal
T}$ to every element in ${\mathcal S}$. In my talk I will present such a canonical
map for certain sets ${\mathcal S,\mathcal T}$ and with it give the
first bijective and involution principle-free proof of the beautiful hook-length
formula for shifted tableaux of a fixed shape.
Shifted tableaux are 2-dimensional
arrays of positive integers of a so-called shifted shape and with
increasing rows and columns. Shifted tableaux play a fundamental role in the
projective representation theory of the symmetric group. It is worth
mentioning that our map induces an effective algorithm for producing
shifted tableaux of a given shape subject to uniform distribution.
No backgrounds on tableaux will be assumed in my talk.
- October 26 at 4:00 pm in Skiles 255
SPEAKER: Philippe Marchal, Georgia Tech
TITLE: Loop-erased walks and heap of cycles
We use a combinatorial structure called of heap of cycles to analyze
some problems related to loop-erased walks and spanning trees. This provides an
alternative approach to some questions that should be discussed in Russ Lyons'
talks.
- November 2 at 4:00 pm in Skiles 255
SPEAKER: Martin Loebl, Georgia Tech
TITLE: Permanents and the colored Jones function
This is a joint work with Stavros Garoufalidis.
About 10 years ago, Melvin-Morton and Rozansky independently conjectured
a relation among the colored Jones function of a knot and its Alexander
polynomial. D. Bar-Natan and S. Garoufalidis reduced the
conjecture about knot invariants to a statement about their combinatorial
weight systems, and then proved it for all semisimple Lie algebras using
combinatorial methods. Over the years, the MMR Conjecture received attention
by many researchers who gave alternative proofs.
D. Bar-Natan and S. Garoufalidis gave formulas for the weight system $W_J$
of the colored Jones function and of its leading order term $W_{JJ}$
in terms of the intersection matrix of a chord diagram. In particular,
$W_{JJ}$ equals to the {\em permanent} of the intersection matrix of
the chord diagram. D. Bar-Natan and S. Garoufalidis asked for a
better understanding of the $W_J$ weight system, especially one that offers
control over the subdiagonal terms in $W_J$.
I will show two combinatorial formulas for $W_J$ which answer this question:
one in terms of the permanent of a matrix associated to a chord diagram, and
another in terms of counting paths of intersecting chords.
- November 9 at 4:00 pm in Skiles 255
SPEAKER: Kamal Jain
TITLE: Continuous Relaxations of some Flow, Cycle Cover and Chromatic number
conjectures
Starting from a semidefinite program for Tutte's flow number, we developed
a concept of unit vector flow in bounded dimension. This gives us
continuous versions of many flow conjectures, cycle cover conjectures and
chromatic number conjectures (after some combinatorial reductions). We
are aware of about a dozen of the popular conjectures
which could be relaxed to this continuous setting. We get two advantages
by doing this.
1. A suite of easier version of difficult conjectures.
2. Intuition behind those conjectures. In the discrete setting, it is not
clear why those conjectures should be true, except that they are true on
small graphs. But in the continuous setting, these conjectures mean that a
certain system of quadratic equalities (first order derivatives give linear
equalities)
has a non-trivial solution. And the intuition is that the system of equalities
has more variables than constraints.
Note: This is a joint work with Laci Lovasz. I will define the basic concepts
so that the talk is
comprehensible by a wider audience.
- November 16 at 4:00 pm in Skiles 255
SPEAKER: Timothy Chow, Tellabs
TITLE: The Ring Grooming Problem: combinatorial optimization in modern
telecommunications networks
Many modern telecommunications networks are based on so-called "bidirectional SONET rings." One
might suppose that optimal routing on a cycle graph would be a trivial problem, but this is not always true
because certain variables are constrained to assume integer values. Schrijver, Seymour, Winkler, and
others have studied the so-called "ring loading problem," in which the cost of a network is assumed to be
proportional to the amount of traffic on the edge with the heaviest load, and they have obtained good
approximation algorithms. Often, however, a more realistic assumption is that the cost of a network is
proportional to the amount of electronic hardware needed to support the traffic. This assumption leads to
the "ring grooming problem," which appears to be harder than the ring loading problem. Our main result is a
constant- factor approximation algorithm (i.e., a polynomial time algorithm that produces a solution whose
cost is within a constant multiplicative factor of the optimum) for uniform traffic. The algorithm is based on
the construction of covering designs. The problem of finding a constant- factor approximation algorithm for
an arbitrary set of traffic demands remains open. No background in telecommunications will be assumed.
This is joint work with Philip Lin.
- November 30 at 4:00 pm in Skiles 255
SPEAKER: Charles Little, Georgia Tech
TITLE: The Pfaffian Property of Graphs
Given a graph $G$ and an orientation for $G$, one may assign plus or minus
signs
to the 1-factors of $G$ according to a procedure described by Kasteleyn.
Kasteleyn's goal was to enumerate the 1-factors, and for this purpose he wanted
the orientation to be chosen so that each 1-factor had the same sign. A graph
is
said to be Pfaffian if it has such an orientation. Pfaffian bipartite graphs
have been characterised in terms of forbidden subgraphs, but a general
characterisation of Pfaffian graphs remains elusive. This talk will discuss
some recent results.
- December 7 at 4:00 pm in Skiles 255
SPEAKER: Mihai Ciucu, Georgia Tech
TITLE: A 2^d+2 vertex model generalizing the six-vertex model
We define a vertex model in d dimensions that is equivalent for
d=3 to the six-vertex model. We prove that the limit defining the free
energy exists, and we obtain bounds for it. For a particular choice of the
weights of the vertex configurations, this model is closely related to a
uniform d-hypergraph that can be regarded as a generalization to higher
dimensions of the Aztec diamond graph. Our bounds provide the free energy
in this case with a precision that increases doubly exponentially in the
number of dimensions d (15 exact digits for d=6).
Back to Combinatorics Seminar