If you

The next speaker will be **Colin Cooper** on
Thursday, April 28th 4:30-5:30 PM in WEH 6423 .

TITLE: ** The diameter of randomly perturbed digraphs and some applications**

SPEAKER: Abie Flaxman

WHEN: Tuesday, ** October 12**, 12:30-1:30 PM

WHERE: OSC 200 (Old Student Center)

PAPERS: The diameter of randomly perturbed digraphs and some applications

ABSTRACT: The central observation of this talk is that if \epsilon n
random edges are added to any n node connected graph or digraph then the
resulting graph has diameter O(log n) with high probability. We apply this
to smoothed analysis of algorithms and property testing.

Smoothed Analysis: Recognizing strongly connected digraphs is a basic
computational task in graph theory. Even for graphs with bounded
out-degree, it is NL-complete. By XORing an arbitrary bounded out-degree
digraph with a sparse random digraph R = G(n,\epsilon n) we obtain a
``smoothed'' instance. We show that, with high probability, a log-space
algorithm will correctly determine if a smoothed instance is strongly
connected. The algorithm consists of, for every pair (s,t), checking if a
series of random walks starting at s ever reaches t (and can be
derandomized by carefully exploring vertices within a certain distance).
We also show that if NL is not contained in L then no heuristic can
recognize similarly perturbed instances of (s,t)-connectivity.

Property Testing: A digraph is called k-linked if for every choice of 2k
distinct vertices s_1, ... ,s_k,t_1,... ,t_k, the graph contains k vertex
disjoint paths joining s_r to t_r for r=1,... ,k. Recognizing k-linked>
digraphs is NP-complete for k >= 2. We describe a polynomial time
algorithm for bounded degree digraphs which accepts k-linked graphs with
high probability, and rejects all graphs which are at least \epsilon n
edges away from being k-linked. The algorithm consists of perturbing the
graph by adding \epsilon n/2 random edges, and then for every choice of
terminal pairs, checking if a series of vertex disjoint random walks
starting from s_1, ... ,s_k ever reach t_1,....,t_k.

This is joint work with Alan Frieze.

TITLE:

SPEAKER: Barbara Anthony

WHEN: Tuesday,

WHERE: OSC 200 (Old Student Center)

ABSTRACT: Consider a directed network with edge capacities and per-unit-time holding costs at each node. We seek flows over time that drain all supplies to the sink, obey capacity constraints and minimize the total holding cost incurred. This problem is motivated by job-shop scheduling problems, whose relaxations can be viewed as continuous multicommodity flow problems with holding costs. We give new results about the structure of optimal solutions, in particular for acyclic graphs which capture the case of flexible flow shops. For acyclic graphs, we prove an O(mn) bound on the number of times flow changes can occur, and give a class of examples requiring \Omega(mn) flow changes, proving the bound is tight.

This is joint work with Lisa Fleischer, to be presented at INFORMS 2004.

TITLE:

SPEAKER: Kelley Burgin

WHEN: Tuesday,

WHERE: OSC 200 (Old Student Center)

ABSTRACT: For a graph K, a random n-lift G of K has vertex set V(K)x[n] where for each vertex v\in V(K), {v}x[n] is called the pillar above v and will be denoted by p_v. The edge set of G is obtained by placing a random perfect matching between pillars p_u and p_w for each edge (u,w)\in E(K). We show that there exists a constant h_0 such that if h>h_0 then a random lift of the complete graph K_h is hamiltonian whp.

This is joint work with Prasad Chebolu, Colin Cooper, Alan Frieze.

TITLE:

SPEAKER: Juan Vera

WHEN: Tuesday,

WHERE: OSC 200 (Old Student Center)

ABSTRACT: We study a random graph $G_n$ that combines certain aspects of geometric random graphs and preferential attachment graphs. Vertices are chosen uniformly at random from the surface of the unit sphere. After generating a vertex, we randomly connect it to $m$ previously generated vertices from those which are within distance r. Neighbors are chosen with probability proportional to their current degree.

We show that if m and r are sufficiently large (will be made precise in the talk) this graph presents the following properties:

- Power law degree sequence.

- Small separators.

- O(m/r) diameter.

This is joint work with Abie Flaxman, Alan Frieze.

TITLE:

SPEAKER: Mohit Singh

WHEN: Tuesday,

WHERE: OSC 200 (Old Student Center)

ABSTRACT: In this talk we will discuss the randomized rounding method for constrained and bicriterion spanning tree problems. We will present how a result by Alon on Network Reliability can be adapted to obtain good approximation algorithms for spanning tree problems. We will obtain approximation guarantees for (at least)two different problems using the same technique.

Talk based on Noga Alon " A note on Network Reliability", Discrete Probability and Algorithms, vol 72,1995,11-14.

This is joint work with Kedar Dhamdhere and R. Ravi.

TITLE:

SPEAKER: Paul Gartside

WHEN: Tuesday,

WHERE: OSC 200 (Old Student Center)

ABSTRACT: The Borromean Rings are a configuration of three rings which are linked together in such a way that no two rings are linked when the third ring is removed. A Brunnian $n$-link is the generalization to $n$ linked rings with the property that if any one ring is deleted then the remaining rings are completely unlinked. In this talk we will see how to classify and count Brunnian links (joint work with Sina Greenwood).

This is joint work with Sina Greenwood.

TITLE:

SPEAKER: Jerzy Wojciechowski

WHEN: Thursday,

WHERE: WEH 6423 (Wean Hall)

ABSTRACT: Let K

The problem of finding a good lower bound for the value of
S(K_{n}^{d}) has a long history. It was first met by Kautz (1958
) in the case of n = 2 ( known in the literature as the snake-in-the-box
problem) in constructng a type of error-checking code for a certain analog-to-
digital conversion systems. He showed that S(K_{2}^{d}) ≥
λ√2^{d}, for some positive constant λ. Several
authors improved the lower bound for S(K_{2}^{d}) until
Evdokimov (1969) obtained a lower bound that is linear in 2^{d}, that
is, he showed that S(K_{2}^{d}) ≥ λ2^{d},
where λ is a positive constant.

The general case of the problem, with an arbitrary value of n, was introduced by Abbott and Dierker (1977), and the bound S(K_{n}^{d})
≥ λ_{n}n^{d} was proved by Abbott and Katchalski
(1991) in the case of even n and by Wojciechowski(1994) in the case of odd n.
The constant λ_{n} obtained in these results is dependent on n
and approaches 0 as n → ∞. Actually, a linear lower bound with the coefficient independent from both n and d is not possible since Abbott and
Katchalski (1988) proved that S(K_{n}^{d}) ≤ (1 + 1/(d-1))n
^{d-1}.

In this talk we will show that the answer to that question is positive.

TITLE:

SPEAKER: A. Ganesh

WHEN: Thursday,

WHERE: WEH 6423 (Wean Hall)

ABSTRACT: We study the SIS epidemic model (or contact process) on graphs, and identify topological properties of the graph that determine the persistence of epidemics. We show that if the ratio of cure to infection rates is larger than the spectral radius of the graph, then the mean epidemic lifetime is of order log n, where n is the number of nodes. Conversely, if this ratio is smaller than a generalization of the isoperimetric constant of the graph, then the mean epidemic lifetime is of order e

TITLE:

SPEAKER: Cliff Smyth

WHEN: Thursday,

WHERE: WEH 6423 (Wean Hall)

ABSTRACT: A family of functions from an ableian group to itself is a permutation sum set if each function is a bijection and the pointwise sum of each pair of functions is a bijection. We study the maximum size of such sets for various abelian and non-abelian groups and draw a connection to certain families of Latin squares.

This is joint work with Don Coppersmith and Abie Flaxman.

TITLE:

SPEAKER: Yiannis Koutis

WHEN: Thursday,

WHERE: WEH 6423 (Wean Hall)

ABSTRACT: We study component-wise sums of vectors over Z

TITLE:

SPEAKER: Dan Spielman

WHEN: Thursday,

WHERE: WEH 4623 (Wean Hall)

ABSTRACT: A low-stretch spanning tree T of a graph G is a spanning tree subgraph in which most edges of G can be routed with small dilation. In particular, the stretch of an edge of G in T is the length of the path in T connecting the endpoints of that edge. The average stretch is the average over edges in G of their stretch. In an analysis of an algorithm for the k-server problem, Alon, Karp, Peleg and West showed that there exist spanning trees of average stretch 2

This is joint work with Michael Elkin, Yuval Emek and Shang-Hua Teng.

TITLE:

SPEAKER: Christopher Hanusa

WHEN: Thursday,

WHERE: WEH 6423 (Wean Hall)

ABSTRACT: In the 1980's, Gessel and Viennot presented a determinantal method for counting non-intersecting lattice paths. We present an extension of this method to counting non-intersecting cycle systems in a particular type of graph we call a hamburger. This ``Hamburger Theorem'' gives a purely combinatorial proof of a determinantal formula for the number of domino tilings of an Aztec diamond, as first introduced by Brualdi and Kirkland in 2003. We present this argument and expand upon the Hamburger Theorem's applications to domino tilings of other regions of interest.

TITLE:

SPEAKER: Anupam Gupta

WHEN: Thursday,

WHERE: WEH 6423 (Wean Hall)

ABSTRACT: We will talk about two problems: (a) that of finding good embeddings of finite metric spaces into L

As a corollary of our results, we show the following basic fact about metric spaces: any n-point subset of L

The talk is partly based on results with Shuchi Chawla and Harald Raecke, and will be self contained.

TITLE:

SPEAKER: David Kravitz

WHEN: Thursday,

WHERE: WEH 6423 (Wean Hall)

ABSTRACT: Here we introduce a new model for random 2-SAT. It is well-known that on 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 thing.

TITLE:

SPEAKER: Abie Flaxman

WHEN: Thursday,

WHERE: WEH 6423 (Wean Hall)

ABSTRACT: In combinatorial optimization, a popular approach to NP-hard problems is the design of approximation algorithms. These algorithms typically run in polynomial time and are guaranteed to produce a solution which is within a known multiplicative factor of optimal. Unfortunately, the known factor is often known to be large in pathological instances. Conventional wisdom holds that, in practice, approximation algorithms will produce solutions closer to optimal than their proven guarantees.

We analyze the performance of three related approximation algorithms for the uncapacitated facility location problem (from [Jain, Mahdian, Markakis, Saberi, Vazirani, 2003] and [Mahdian, Ye, Zhang, 2002]) when each is applied to an instances created by placing n points uniformly at random in the unit square. We find that, with high probability, these three algorithms do not find asymptotically optimal solutions, and, also with high probability, a simple plane partitioning heuristic does find an asymptotically optimal solution.

TITLE:

SPEAKER: Colin Cooper

WHEN: Thursday,

WHERE: WEH 6423 (Wean Hall)

ABSTRACT: We discuss several results related to the time taken for a random walk to visit all vertices of a graph, the cover time. We first discuss this in relation to two classical models of random graphs viz. $G_{n,p}$ and random $r$-regular graphs. We then consider the preferential attachment graph. We give high probability, asymptotically precise estimates for the cover time in all cases.

PostScript Ghostview or GSview, Adobe Acrobat Reader, Sun StarOffice Impress or Microsoft PowerPoint Viewer.

pchebolu @ andrew . cmu . edu