Seminars and Colloquia by Series

Submodular Function Minimization

Series
Combinatorics Seminar
Time
Wednesday, August 19, 2009 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Satoru IwataKyoto University
In this lecture, I will review combinatorial algorithms for minimizing submodular functions. In particular, I will present a new combinatorial algorithm obtained in my recent joint work with Jim Orlin.

Submodular Functions in Graph Theory

Series
Combinatorics Seminar
Time
Friday, August 14, 2009 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Prof. Satoru IwataKyoto University
In this lecture, I will explain connections between graph theory and submodular optimization. The topics include theorems of Nash-Williams on orientation and detachment of graphs.

Liar Games, Optimal Codes, and Deterministic Simulation of Random Walks

Series
Combinatorics Seminar
Time
Thursday, May 21, 2009 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Joshua CooperDepartment of Mathematics, University of South Carolina
We consider the Ulam "liar" and "pathological liar" games, natural and well-studied variants of "20 questions" in which the adversarial respondent is permitted to lie some fraction of the time. We give an improved upper bound for the optimal strategy (aka minimum-size covering code), coming within a triply iterated log factor of the so-called "sphere covering" lower bound. The approach is twofold: (1) use a greedy-type strategy until the game is nearly over, then (2) switch to applying the "liar machine" to the remaining Berlekamp position vector. The liar machine is a deterministic (countable) automaton which we show to be very close in behavior to a simple random walk, and this resemblance translates into a nearly optimal strategy for the pathological liar game.

A New Look at the Compound Poisson Distribution and Compound Poisson Approximation

Series
Combinatorics Seminar
Time
Friday, April 24, 2009 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Mokshay MadimanDepartment of Statistics, Yale University
We develop an information-theoretic foundation for compound Poisson approximation and limit theorems (analogous to the corresponding developments for the central limit theorem and for simple Poisson approximation). First, sufficient conditions are given under which the compound Poisson distribution has maximal entropy within a natural class of probability measures on the nonnegative integers. In particular, it is shown that a maximum entropy property is valid if the measures under consideration are log-concave, but that it fails in general. Second, approximation bounds in the (strong) relative entropy sense are given for distributional approximation of sums of independent nonnegative integer valued random variables by compound Poisson distributions. The proof techniques involve the use of a notion of local information quantities that generalize the classical Fisher information used for normal approximation, as well as the use of ingredients from Stein's method for compound Poisson approximation. This work is joint with Andrew Barbour (Zurich), Oliver Johnson (Bristol) and Ioannis Kontoyiannis (AUEB).

Toric geometry of series-parallel graphs

Series
Combinatorics Seminar
Time
Friday, April 17, 2009 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Guantao ChenGeorgia State University
Let G be a graph and K be a field. We associate to G a projective toric variety X_G over K, the cut variety of the graph G. The cut ideal I_G of the graph G is the ideal defining the cut variety. In this talk, we show that, if G is a subgraph of a subdivision of a book or an outerplanar graph, then the minimal generators are quadrics. Furthermore we describe the generators of the cut ideal of a subdivision of a book.

Entropy and Sumsets

Series
Combinatorics Seminar
Time
Tuesday, April 7, 2009 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Adam MarcusYale University
The entropy function has a number of nice properties that make it a useful counting tool, especially when one wants to bound a set with respect to the set's projections. In this talk, I will show a method developed by Mokshay Madiman, Prasad Tetali, and myself that builds on the work of Gyarmati, Matolcsi and Ruzsa as well as the work of Ballister and Bollobas. The goal will be to give a black-box method for generating projection bounds and to show some applications by giving new bounds on the sizes of Abelian and non-Abelian sumsets.

Graph Patches (Partial Sparsifiers) and their applications to designing cost-effective, expanding networks

Series
Combinatorics Seminar
Time
Friday, April 3, 2009 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Alexandra KollaUC Berkeley
I will present an approximation algorithm for the following problem: Given a graph G and a parameter k, find k edges to add to G as to maximize its algebraic connectivity. This problem is known to be NP-hard and prior to this work no algorithm was known with provable approximation guarantee. The algorithm uses a novel way of sparsifying (patching) part of a graph using few edges.

On the chromatic number of a random d-regular graph

Series
Combinatorics Seminar
Time
Friday, March 27, 2009 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Graeme KemkesUCSD
Choose a graph uniformly at random from all d-regular graphs on n vertices. We determine the chromatic number of the graph for about half of all values of d, asymptotically almost surely (a.a.s.) as n grows large. Letting k be the smallest integer satisfying d < 2(k-1)\log(k-1), we show that a random d-regular graph is k-colorable a.a.s. Together with previous results of Molloy and Reed, this establishes the chromatic number as a.a.s. k-1 or k. If furthermore d>(2k-3)\log(k-1) then the chromatic number is a.a.s. k. This is an improvement upon results recently announced by Achlioptas and Moore. The method used is "small subgraph conditioning'' of Robinson and Wormald, applied to count colorings where all color classes have the same size. It is the first rigorously proved result about the chromatic number of random graphs that was proved by small subgraph conditioning. This is joint work with Xavier Perez-Gimenez and Nick Wormald.

Tolerance Graphs and Orders

Series
Combinatorics Seminar
Time
Wednesday, March 11, 2009 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Ann TrenkDepartment of Mathematics, Wellesley College
Tolerance graphs were introduced in 1982 by Golumbic and Monma as a generalization of the class of interval graphs. A graph G= (V, E) is an interval graph if each vertex v \in V can be assigned a real interval I_v so that xy \in E(G) iff I_x \cap I_y \neq \emptyset. Interval graphs are important both because they arise in a variety of applications and also because some well-known recognition problems that are NP-complete for general graphs can be solved in polynomial time when restricted to the class of interval graphs. In certain applications it can be useful to allow a representation of a graph using real intervals in which there can be some overlap between the intervals assigned to non-adjacent vertices. This motivates the following definition: a graph G= (V, E) is a tolerance graph if each vertex v \in V can be assigned a real interval I_v and a positive tolerance t_v \in {\bf R} so that xy \in E(G) iff |I_x \cap I_y| \ge \min\{t_x,t_y\}. These topics can also be studied from the perspective of ordered sets, giving rise to the classes of Interval Orders and Tolerance Orders. In this talk we give an overview of work done in tolerance graphs and orders . We use hierarchy diagrams and geometric arguments as unifying themes.

Graph parallel rigidity

Series
Combinatorics Seminar
Time
Friday, March 6, 2009 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Alexey SpiridonovMIT
This is joint work with Alex Postnikov. Imagine that you are to build a system of space stations (graph vertices), which communicate via laser beams (edges). The edge directions were already chosen, but you must place the stations so that none of the beams miss their targets. In this talk, we let the edge directions be generic and independent, a choice that constrains vertex placement the most. For K_{3} in \mathbb{R}^{2}, the edges specify a unique triangle, but its size is arbitrary --- D_{2}(K_{3})=1 degree of freedom; we say that K_{3} is rigid in \mathbb{R}^{2}. We call D_{n}(G) the degree of parallel rigidity of the graph for generic edge directions. We found an elegant combinatorial characterization of D_{n}(G) --- it is equal to the minimal number of edges in the intersection of n spanning trees of G. In this talk, I will give a linear-algebraic proof of this result, and of some other properties of D_{n}(G). The notion of parallel graph rigidity was previously studied by Whiteley and Develin-Martin-Reiner. The papers worked with the generic parallel rigidity matroid; I will briefly compare our results in terms of D_{n}(G) with the previous work.

Pages