The ACO seminar (Spring 2004).

The next speaker will be Jozsef Balogh on Thursday, April 29th.

Schedule:

TITLE: On packing Hamilton Cycles in $\epsilon$-regular Graphs
SPEAKER: Alan Frieze
WHEN: Friday, January 23, 4:30 PM
WHERE: PPB 300 (Physical Plant Building)
PAPERS:
ABSTRACT: A graph $G=(V,E)$ on $n$ vertices is $(\alpha,\epsilon)$-regular if its minimal degree is at least $\alpha n$, and for every pair of disjoint subsets $S,T\subset V$ of cardinalities at least $\epsilon n$, the number of edges $e(S,T)$ between $S$ and $T$ satisfies: $\left|\frac{e(S,T)}{|S|\,|T|}-\alpha\right|\le \epsilon$. We prove that if $\a\gg\epsilon>0$ are constants, then every $(\alpha,\epsilon)$-regular graph on $n$ vertices contains a family of $(\alpha/2-O(\epsilon))n$ edge-disjoint Hamilton cycles. As a consequence we derive that for every constant $0 < p < 1$, with high probability in the random graph $G(n,p)$, almost all edges can be packed into edge-disjoint Hamilton cycles. A similar result is proven for the directed case. We give applications to some Maker-Breaker games.

TITLE: Size Ramsey Numbers Involving Large Stars
SPEAKER: Oleg Pikhurko
WHEN: Thursday, February 5, 12:30 PM
WHERE: DH 1117
PAPERS:
ABSTRACT: The size Ramsey number of a pair (F,G) of graphs is the smallest number of edges in an (F,G)-arrowing graph H (that is, any blue-red coloring of the edge set of H yields a blue F or a red G). We will study the case when F is a fixed graph while G=K_{1,n} is a large star. Although various asymptotics results have been obtained in this case, the general answer is still unknown.

TITLE: The "Entropy Method" in Combinatorics
SPEAKER: David Galvin, Microsoft Research Group
WHEN: Thursday, February 12, 12:30 PM
WHERE: DH 1117
PAPERS:
ABSTRACT: The binary entropy of a finite-range uniform random variable is exactly the log of the size of the range space. For this reason, entropy methods have become quite popular recently for tackling certain enumerative problems in combinatorics --- any bounds that can be put on the entropy of a uniformly chosen member of a set correspond immediately to bounds on the size of the set.

In this talk I will introduce an entropy inequality due to J. B. Shearer that is proving to be a powerful tool in this direction. I will give two applications. The first is a swift entropy proof of an old result of Loomis and Whitney, bounding the volume of a body in R^d in terms the volumes of its (d-1)-dimensional projections. The second is a recent result (joint with P. Tetali of Georgia Tech) giving a tight upper bound on the number of graph homomorphisms from a regular bipartite graph to any fixed constraint graph.

TITLE: Large Convex Cones in Hypercubes
SPEAKER: Miklos Ruszinko, SZTAKI
WHEN: Thursday, February 19, 12:30 PM
WHERE: DH 1117
PAPERS:
ABSTRACT: A family of subsets of $[n]$ is {\em positive linear combination free} if the characteristic vector of neither member is the positive linear combination of the characteristic vectors of some other ones. We construct a positive linear combination free family which contains $(1-o(1))2^n$ subsets of $[n]$ and we give tight bounds on the $o(1)2^n$ term. The problem was posed by Ahlswede and Khachatrian and the result has geometric consequences.

With Z. Furedi.

TITLE: Metric Embeddings and Approximation Algorithms
SPEAKER: R. Ravi
WHEN: Thursday, February 26, 12:30 PM
WHERE: DH 1117
PAPERS:
ABSTRACT: In this talk, I will survey the various ways the concept of finite metrics and techniques for embedding one type of metric into another are useful in the design of approximation algorithms: In short, they arise (i) as data to NP-hard problems to be approximated, (ii) as relaxations for NP-hard problems and finally (iii) as the main objects of study and inspiration for the design of new algorithms.

This talk is an abridged version of one I gave at a workshop on metric embeddings at Princeton University and the slides can be found in www.gsia.cmu.edu/andrew/ravi/public/metrics2.pdf

A more detailed discussion of many of the topics discussed in this talk are available as scribe notes in a class I co-taught with Prof. Anupam Gupta at Carnegie-Mellon during Fall '03 which can be found in www.cs.cmu.edu/~anupamg/metrics/

TITLE: Multicommodity Facility Location
SPEAKER: Amitabh Sinha
WHEN: Thursday, March 4, 12:30 PM
WHERE: DH 1117
PAPERS:
ABSTRACT: Multicommodity facility location refers to the extension of facility location to allow for different clients having demand for different goods, from among a finite set of goods. This leads to several optimization problems, depending on the costs of opening facilities (now a function of the commodities it produces). In this paper, we introduce and study some variants of multicommodity facility location, and provide approximation algorithms and hardness results for them.

Joint work with R. Ravi, appeared in SODA 2004.

TITLE: Permutation classes, an overview
SPEAKER: Michael Albert, University of Otago
WHEN: Thursday, April 15, 12:30 PM
WHERE: DH 1117
PAPERS:
ABSTRACT: If data items 1, 2, and 3 are processed by a stack, they can be output in any order except 312. More generally, if items 1,2,...,n are processed by a stack they can be output in any order not containing the pattern 312, i.e. no three elements a < b < c of the input can occur in the order cab in the output. This observation of Knuth's, extended to other data structures by Tarjan and Pratt, became the foundation of the study of permutation classes. Subsequent investigations in this area were of a more abstract combinatorial nature, focused on enumeration problems and the, recently resolved, Wilf-Stanley conjecture.

We will provide an overview of the study of permutation classes, biased towards the original viewpoint, and including recent results connecting permutation classes with regular and context free languages.

TITLE: Balanced Graph Partitioning
SPEAKER: Konstantin Andreev
WHEN: Thursday, April 22, 12:30 PM
WHERE: DH 1117
PAPERS:
ABSTRACT: In this talk we consider the problem of $(k,\nu)$-balanced graph partitioning - dividing the vertices of a graph into $k$ almost equal size components (each of size less than $\nu \cdot \frac{n}{k}$) so that the capacity of edges between different components is minimized. This problem is a natural generalization of several other problems such as minimum bisection, which is the $(2,1)$-balanced partitioning problem. We present a bicriteria polynomial time approximation algorithm with an $O(\log^2{n})$-approximation for any constant $\nu>1$. For $\nu =1$ we show that no polytime approximation algorithm can guarantee a finite approximation ratio unless $P=NP$. Previous work has only considered the $(k,\nu)$-balanced partitioning problem for $\nu \geq 2$.

Joint work with H. Raecke, to appear in SPAA 2004

TITLE: Disjoint Representability of sets
SPEAKER: Jozsef Balogh, Ohio State University
WHEN: Thursday, April 29, 12:30 PM
WHERE: DH 1117
PAPERS:
ABSTRACT: For a hypergraph H and a set S, the trace of H on S is defined to be the set of all intersections of edges of H with S.

We will consider forbidden trace problems, in which we want to find the largest hypergraph H that does not contain some list of forbidden configurations as traces, possibly with some restriction on the number of vertices or the size of the edges in H. Write $[k]^l$ for the set of all l-subsets of [k]={1,\cdots,k}. Note that H has k disjointly representable sets exactly when it has a $[k]^1$ trace.

We will focus on three forbidden configurations: the k-singleton $[k]^1$, the k-co-singleton $[k]^(k-1)$ and the k-chain $C_k = \{ \emptyset, [1], [2], \cdots , [k-1] \}$. We prove a number of results on the size of the largest hypergraph H with some combination of these traces forbidden, sometimes with restrictions on the number of vertices or the size of the edges. We obtain exact results in the case k=3, both for uniform and non-uniform hypergraphs, and classify the extremal examples, and asymptotical results for larger values of k.

This is joint work with P. Keevash and B. Sudakov.

Back to the ACO home page