The ACO Seminar (Spring 2006).
The ACO Seminar (Spring 2006).
The next speaker will be David Kravitz on Monday, April 17, at 1:30pm in DH 4303 .
SPEAKER: David Kravitz
WHEN: April 17, 1:30pm
WHERE: DH 4303
ABSTRACT:
We introduce and study online versions of two classical random structures. The first is a variation on the classical random graph
model, the second is the satisfiability model.
We begin with the random graph. Let $c$ be a constant and $(e_1,f_1)$, $(e_2,f_2), \dots$, $(e_{cn},f_{cn})$ be a sequence of ordered pairs of edges on vertex set $[n]$ chosen uniformly and independently at random. Let \(A\) be an algorithm for the online choice of one edge from each presented pair, and for \( i= 1, \dots, cn \) let \( G_A(i) \) be the graph on vertex set \( [n] \) consisting of the first \( i \) edges chosen by \(A\). We prove that all algorithms in a certain class have a critical value \( c_A \) for the emergence of a giant component in \( G_A( cn ) \) (i.e. if \( c < c_A \) then with high probability the largest component in \( G_A(cn) \) has \( o(n) \) vertices and if \( c > c_A \) then with high probability there is a component of size \( \Omega(n) \) in \( G_A(cn) \)). We show that a particular algorithm in this class with high probability produces a giant component before \( 0.385 n \) steps in the process (i.e. we exhibit an algorithm that creates a giant component relatively quickly). The fact that another specific algorithm that is in this class has a critical value resolves a conjecture of Spencer. In addition, we establish a lower bound on the time of emergence of a giant component in any process produced by an online algorithm and show that there is a phase transition for the offline version of the problem of creating a giant component.
Now we consider satisfiability. Given $n$ Boolean variables $x_1,\dots,x_n$, a $k$-clause is a disjunction of $k$ literals, where a literal is a variable or its negation. Suppose random $k$-clauses are generated one at a time and an online algorithm accepts or rejects each clause as it is generated. Our goal is to accept as many randomly generated $k$-clauses as possible with the condition that it must be possible to satisfy every clause which is accepted. When $cn$ random $k$-clauses on $n$ variables are given, a natural online algorithm known as \emph{Online-Lazy} accepts an expected $(1-\frac{1}{2^k})cn+z_kn$ clauses for some constant $z_k$. If these clauses are given offline, it is possible to do much better, $(1-\frac{1}{2^k})cn+\Omega(\sqrt c)n$ can be accepted \whp. The question of closing the gap between $(1-\frac{1}{2^k})cn+z_kn$ and $(1-\frac{1}{2^k})cn+\Omega(\sqrt c)n$ for the online version was posed by Coppersmith, Gamarnik, Hajiaghayi, and Sorkin. We show that for any $k \geq 1$, any online algorithm will accept less than $(1-\frac{1}{2^k})cn+(\ln 2)n$ $k$-clauses \whp, furthermore we show that this bound is asymptotically tight as $k \to \infty$.
We also introduce a new random model for random $2-SAT$. It is well-known that inn the standard model there is a sharp phase transition, the probability of satisfiability quickly drops as the number of clauses exceeds the number of variables. The location of this phase transition suggests that there is a direct connection between the appearance of a giant in the corresponding $2n$-vertex graph and satisfiability. Here we show that the giant has nothing to do with satisfiability, and in fact the expected degree of a randomly chosen vertex is the important parameter.
TITLE: Chain Programming
SPEAKER: K. Subramani (West Virginia University)
WHEN: April 13, 4:30pm
WHERE: PPB 300
ABSTRACT: Chain Programming is a restricted form of Linear Programming; in a Chain Program, there exists a total ordering on the program variables. In other words, the constraints $x_{1} \le x_{2} \ldots x_{n}$ are either implicitly or explicitly part of the constraint system. At the present juncture, it is not clear whether an arbitrary linear program augmented with a chain is easier to solve than linear programs in general, either asymptotically or computationally. However, if the linear program is constituted entirely of difference constraints, then the total ordering results in an elegant divide and conquer algorithm for the problem of feasibility testing. This approach can be parallelized in straightforward fashion to run on any SIMD or MIMD architecture, thereby greatly enhancing its effectiveness. Inasmuch as difference constraint logic is an integral part of a number of verification problems in both model-checking and real-time scheduling, our result is of particular importance to these communities. One of the surprising consequences of our research is the establishment of a link between Chain Programs over Difference Constraints and a specialized class of Totally Unimoduluar (TUM) matrices called {\em interval} matrices.
TITLE: Disrepancy games
SPEAKER: Michael Krivelevich
WHEN: March 2, 4:30pm
WHERE: PPB 300
ABSTRACT: A discrepancy game played on a hypergraph H=(V,E) by two players, Balancer and Unbalancer. They select one element of the vertex set V alternately, until all vertices are selected. Balancer wins if at the end of the game all edges e in E are roughly equally distributed between the two players.
We derive a criteria for Balancer's win in a general discrepancy game. In particular, it follows from our result that if H is n-uniform and has m edges, then Balancer can achieve having between n/2-c\sqrt{n\ln m} and n/2+c\sqrt{n\ln m} of his vertices on every edge e of H.
We also discuss applications in positional game theory.
A joint work with Noga Alon, Joel Spencer and Tibor Szab\'o.
TITLE: Decompositions of graphs
SPEAKER: Teresa Sousa
WHEN: February 9, 4pm
WHERE: Posner Hall Room 259
ABSTRACT:The subject of graph decompositions is a vast topic and has been studied for the past 40 years by numerous people. Given two graphs G and H, an H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H. We allow partitions only, that is, every edge of G appears in precisely one part. Let $\phi_H(G)$ be the smallest possible number of parts in an H-decomposition of G. We study the function $\phi_H(n)$ which is the smallest number such that any graph G of order n admits an H-decomposition with at most $\phi_H(n)$ elements.
Erdos, Goodman and Posa proved that $\phi_{K_{3}}(n)=t_2(n)$, where $t_ {r-1}(n)$ denotes the number of edges in the Turan Graph, $T_{r-1}(n) $. This result was extended by Bollobas, who proved that $\phi_{K_{r}} (n)=t_{r-1}(n)$, for all n \geq r \geq 3.
We managed to obtain the exact value of $\phi_H(n)$ for some graphs H, namely the cycle of length 5, the cycle of length 5 with one chord and any clique-extension of order r+1. For r\geq 3 a clique-extension of order r+1 is a connected graph that consists of a K_r plus another vertex adjacent to at most r-1 vertices of K_r. For all fixed H with chromatic number r\geq 3 we will prove an asymptotic result about $\phi_H(n)$, that is we show that $\phi_H(n)= t_{r-1}(n)+o(n^2)$. For a non-empty graph H we denote by gcd(H) the greatest common divisor of the degrees of H. For a bipartite graph with gcd(H)=1 the exact value of the function $\phi_H(n)$ will be obtained, for n sufficiently large.
The proofs presented use Turan's Theorem, the Regularity Lemma, results of Pippenger and Spencer, Gustavsson's Decomposition Theorem for dense graphs and results about packing vertex disjoint copies of a fixed graph H into a large graph G.
This is joint work with Oleg Pikhurko.
TITLE: Hamilton cycles in random graphs
SPEAKER: Kelley Burgin
WHEN: January 30, 1:30pm
WHERE: Porter Hall A19
ABSTRACT: We discuss the existence of Hamilton cycles in three different models of random graphs. In doing so, we present general proof techniques which include the differential equation method.
The first model is the random lift model introduced by Linial and Amit. For a fixed base graph K=(V,E), a random lift has vertex set V x [n] and for each edge (i,j) in E, there is a random perfect matching between {i} x [n] and {j} x [n]. We show that random lifts of the complete graph and complete bipartite graph contain a Hamilton cycle whp.
The second model is a random graph on n vertices in which (1-b)n vertices have degree 4 and the other bn vertices have degree 5. We show that for certain values of b, the graph is Hamiltonian whp.
The last model is a sparse random graph on n vertices with cn/2 random edges and minimum degree 3. We show that this random graph is Hamiltonian for c at least 3.01.
TITLE: Approximating k-MultiCut Problem
SPEAKER: Mohit Singh
WHEN: December 8, 4-5:30pm
WHERE: PPB 300
ABSTRACT: Given an undirected graph, a set of t pairs of vertices, the multi-cut problem is to find the minimum set of edges to remove which separate all pairs. The k-multicut problem is a generalization of the multicut problem in which one is given a target k\leq t and asked to remove only k pairs. We use techiniques from combinatorial optimization: Lagrangian relaxation and Total unimodularity, to obtain constant factor approximation for the k-multicut problem on trees. This also leads to O(log^2n loglogn) -approximation for the k-multicut problem on general graphs, where $n$ is the number of vertices in the graph. We also give bicriterion approximation algorithm for the k-multicut problem. Our techniques also give a simple $2$-approximation algorithm for the multicut problem on trees matching the best known algorithm of Garg, Vazirani and Yannakakis'94.
Joint Work with Viswanath Nagarajan and Daniel Golovin. To appear in SODA'06.
TITLE: Stopping Rules and Time Reversal for Random Walks on Graphs
SPEAKER: Andrew Beveridge
WHEN: December 1, 3:30-4:30pm
WHERE: PPB 300
ABSTRACT: Consider a directed graph $G$ and a random walk on it. Looking at such a walk in reverse gives a random walk on a related directed graph $\hat{G}$. When $G$ is an undirected graph, we have $G=\hat{G}$. One can use and intelligent stopping rule that "looks where it is going" to halt a random walk so that the distribution of the final state is a desired distribution $\tau$. This leads to a number of exact mixing measures that are related to the classical mixing measures (such as the relaxation time). We discuss the effect of time reversal on stopping rules by considering families of rules from singletons to a specified target distribution. We describe a duality between stopping rules on $G$ and stopping rules on $\hat{G}$. In particular, we give a natural proof that the "average mixing time" of a random walk on $G$ is equal to the time it takes for a random walk on $\hat{G}$ to "forget where it started," which was originally proved by Lovasz and Winkler via linear programming.
Joint work with Laszlo Lovasz.
TITLE: Matching Algorithms are Fast in Sparse Random Graphs
SPEAKER: Guido Schaefer, Technische Universitat Berlin
WHEN: November 17, 4-5:30pm
WHERE: PPB 300
ABSTRACT: We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on $n$ vertices, with high probability every non-maximum matching has an augmenting path of length $O(\log n)$. This implies that augmenting path algorithms like the Hopcroft--Karp algorithm for bipartite graphs and the Micali--Vazirani algorithm for general graphs, which have a worst case running time of $O(m\sqrt{n})$, run in time $O(m \log n)$ with high probability, where $m$ is the number of edges in the graph. Motwani proved these results for random graphs when the average degree is at least $\ln (n)$ [\emph{Average Case Analysis of Algorithms for Matchings and Related Problems}, Journal of the ACM, \textbf{41}(6), 1994]. Our results hold, if only the average degree is a large enough constant. At the same time we simplify the analysis of Motwani.
This is joint work with Holger Bast, Kurt Mehlhorn and Hisao Tamaki.
TITLE: On a conjecture of Berge and Simonovits on hypergraph products
SPEAKER: Dhruv Mubayi, University of Illinois, Chicago
WHEN: October 27, 12-1pm
WHERE: Wean Hall 5403
ABSTRACT: The product of hypergraphs G and H has vertex set equal to the cartesian product of V(G) and V(H), and edge set equal to the set of all cartesian products of edges in G with edges in H. We construct a hypergraph sequence G_n for which the chromatic number of G_n approaches infinity, and yet the chromatic number of the product of G_n wth itself is 2. This disproves a conjecture of Berge and Simonovits from the early 70's. On the other hand, we show that if G and H are hypergraphs with infinite chromatic number and finite edge sizes, then the chromatic number of the product of G and H is also infinite. We also provide a counterexample to a "dual" version of their conjecture, by constructing a graph sequence G_n for which the independence ratio tends to 0, and yet the independence ratio of the product tends to 1/2. The constant 1/2 cannot be replaced by a larger number. The construction is obtained via connections to Ramsey-Turan theory, and addresses a question of Kostochka. We will end with some open problems.
This is joint work with Vojtech Rodl.
TITLE: Embedding into $l_p$ with constant average distortion
SPEAKER: Ofer Neiman, Hebrew University of Jerusalem
WHEN: October 20, 12-1pm
WHERE: Wean Hall 5403
ABSTRACT: An embedding is a function between metric spaces, usualy from an arbitrary one into a more simple and structured space (such a Euclidean space). The distortion is the multiplicative amount by which distances change. A well known theorem of Bourgain states that every metric space embeds into Euclidean space with O(log n) distortion, which is tight. Our result is a strengthening of Bourgain's Theorem, providing a CO-Lipschitz embedding with constant average distortion. As a matter of fact, it provides for any $\epsilon$ the best $\epsilon$-slack distortion simultaneously.
This is joint work with Yair Bartal and Ittai Abraham.
TITLE: Anti-Ramsey and Canonical Ramsey type problems
SPEAKER: Tao Jiang, Miami University, Oxford, OH
WHEN: October 20, 4:00pm-5:30pm
WHERE: PPB 300
ABSTACT: We discuss a collection of problems that deal with color patterns in edge-colorings of the complete graph under various constraints. A subgraph $H$ in an edge-colored host graph $G$ is monochromatic if all edges of $H$ have the same color, rainbow if all the edges of $H$ have different colors, and properly colored if no two incident edges have the same color.
Here are some examples of the problems to be discussed.
(1) Given a graph $H$ and a positive integer $n$, what is the maximum number $R^*(n,H)$ of colors in an edge-coloring of $K_n$ that does not contain a rainbow copy of $H$? This maximum number is called the anti-Ramsey number of $H$. Anti-Ramsey numbers are closely related to the Turan numbers.
(2) Given two graphs $G$ and $H$, what is the smallest $n$ such that in every edge-coloring of $K_n$ (using any number of colors) there must exist either a monochromatic copy of $G$ or a rainbow copy of $H$? This problem is motivated by the Erdos-Rado Canonical Ramsey Theorem and has been studied by various researchers in different contexts.
(3) Given a graph $H$ and a positive integer $n$, what is the maximum $k$ such that in every edge-coloring of K_n in which each color appears at most $k$ times at each vertex there must exist a properly colored copy of $H$? a rainbow copy of $H$?
We will give a brief history of these problems, their connection to each other, and mention some results and open problems.
TITLE: The game chromatic number of random graphs
SPEAKER: Alan Frieze
WHEN: Thursday, October 6, 4:00pm-5:30pm
WHERE: 300 PPB
ABSTACT: Two players take turns in coloring the vertices of a graph G with k colors. They are constrained so that the partial coloring is always proper, i.e., neighboring vertices get different colors. In one version of this game, the two players are called Maker and Breaker. Maker wins if all the vertices of G are eventually colored. Breaker wins if at some stage the current partial coloring cannot be extended to a complete coloring of G, i.e., if at some stage there is an uncolored vertex such that each of the k colors appears at least once in its neighbourhood.
Our results will not be sensitive to who gets first and so let us assume that Maker goes first. The Game Chromatic Number is the minimum k for which Maker has a winning strategy. This parameter was introduced by Bodlaender and we discuss its size in the context of random graphs.
This is joint work with Tom Bohman and Benny Sudakov.
TITLE: Random Sampling Auctions
SPEAKER: Abie Flaxman
WHEN: Thursday, September 29, 3:00pm-4:00pm
WHERE: 300 PPB
ABSTACT: Random Sampling is the most prevalent technique for designing incentive-compatible auctions to maximize the auctioneer's profit when the bidders' valuations are a priori unknown. The first and simplest application of random sampling to auctions is in the context of auctioning a digital good. For this problem, the random sampling optimal price auction works by selecting a bipartition of the bidders uniformly at random and offering the optimal sale price for each part to the other part.
We give a simple analysis of the competitive ratio of the random sampling auction. The random sampling auction was prreviously known to be worst-case competitive with a bound of 7600; our analysis improves the bound to 15. It is believed that the auction is in fact 4-competitive, and we show that on the equal revenue input, where any sale price gives the same revenue, random sampling is exactly a factor of four from optimal.
This is joint work with Uri Feige, Jason Hartline and Bobby Kleinberg.
TITLE: How to solve a hypergraph Turan problem exactly?
SPEAKER: Oleg Pikhurko
WHEN: Thursday, September 15, 4:00-5:30 pm
WHERE: 300 PPB (Physical Plant Building)
ABSTRACT:For a k-graph F, the Turan function ex(n,F) is the maximum size of an F-free k-graph on n vertices. In general, it is notoriously hard to determine. Even if we know ex(n,F) asymptotically, the exact computation might turn out to be a difficult task. I will discuss the stability approach for proving exact Turan results that was suggested by Simonovits in the 1960s and used recently by Furedi, Keevash, Mubayi, Sudakov and others.
Some of the presented results are joint work with Dhruv Mubayi.
tmj @ andrew . cmu . edu