|
Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Research Groups
About the Department |
Algorithms, Combinatorics and Optimization Seminars
Schedule for Fall 2009
THURSDAY, September 10, 2009 Eyal Lubetzky, Microsoft Research Title: Anatomy of a young giant component in the random graph ABSTRACT: We provide a complete description of the giant component of the Erdős-Rényi random graph G(n,p) as soon as it emerges from the scaling window, i.e., for p = (1+ε)/n where ε3n → ∞ and ε=o(1)$. Our description is particularly simple for ε = o(n-1/4), where the giant component C1 is contiguous with the following model (i.e., every graph property that holds with high probability for this model also holds w.h.p. for C1). Let Z be normal with mean (2/3)ε3n and variance ε3n, and let K be a random 3-regular (multi)graph on 2⌊Z⌋ vertices. Replace each edge of K by a path, where the path lengths are i.i.d. geometric with mean 1/ε. Finally, attach an independent Poisson(1-ε)-Galton-Watson tree to each vertex. A similar picture is obtained for larger ε=o(1), in which case the random 3-regular graph is replaced by a random (multi)graph with Nk vertices of degree k for k≥3$, where Nk has mean and variance of order εkn. This description enables us to determine fundamental characteristics of the supercritical random graph. Namely, we can infer the asymptotics of the diameter of the giant component for any rate of decay of ε, as well as the mixing time of the random walk on C1. Joint work with Jian Ding and Yuval Peres. Time: 4:30 P.M. - 5:30 P.M. THURSDAY, September 17, 2009Pal Melsted Title: Space Utilization of Cuckoo Hashtables ABSTRACT: We study the space requirements for Cuckoo Hashing. This can be reduced to the following question in Random Graphs. We are given two disjoint sets L,R with |L|=n=alpha*m and |R|=m. We construct a random graph G by allowing each x in L to choose d random neighbours in R. The problem is to find m(G), the size of the largest matching in G. From the point of view of Cuckoo Hashing, a key question is to locate the threshold for when m(G)=n with high probability, since if m(G) < n it is impossible to store all items. We answer this question exactly for d greater than 5. Time: 4:30 P.M. - 5:30 P.M. THURSDAY, September 24, 2009Adam Smith Title: Lower Bounds on Error in Private Data Analysis and Connections to the Spectra of Random Matrices ABSTRACT: Contingency tables are the method of choice of government agencies for releasing statistical summaries of categorical data. In this paper, we consider lower bounds on how much distortion (noise) is necessary in these tables to provide privacy guarantees when the data being summarized is sensitive. We extend a line of recent work on lower bounds on noise for private data analysis (DInur & Nissim, PODS 03; Dwork, McSherry & Talwar, STOC 07; Dwork and Yekhanin, Crypto 08) to a natural and important class of functionalities. Our investigation also leads to new results on the spectra of random matrices with correlated rows. Joint work with Shiva Kasiviswanathan (Los Alamos) and Mark Rudelson (Michigan). Time: 4:30 P.M. - 5:30 P.M.
THURSDAY, October 22, 2009Michal Karonski Title: On the 1-2-3 conjecture ABSTRACT: A weighting of the edges of a graph with integer weights gives rise to a weighting of the vertices, the weight of a vertex being the sum of the weights of its incident edges. Such a weighting induces a vertex coloring, i.e., by assigning the same color to vertices with the same weight. It is natural to consider edge weighting where we require that adjacent vertices have different weights --- that is, the vertex weighting induce a proper coloring of the graph. In 2001 Luczak, Thomason and myself formulated the following conjecture: (in which a `non-trivial graph' refers to a connected graph with at least three vertices.) Conjecture (Karonski, Luczak and Thomason, 2001): The edges of every graph that does not contain a component isomorphic to $K_2$ can be weighted with the integers {1,2,3} such that the resultant vertex weighting is a proper coloring. In my talk I will discuss some recent developments regarding the above conjecture. and a related {1,2}-conjecture. In particular, I will present a joint result, with Maciej Kalkowski and Florian Pfender, showing that {1,2, ... , 5}-edge-weighting suffices to properly color vertices of a graph. Time: 4:30 P.M. - 5:30 P.M. THURSDAY, October 29, 2009Pawel Pralat, West Virginia University Title: Chasing robbers on random graphs ABSTRACT: We study the vertex pursuit game of Cops and Robbers where cops try to capture a robber on the vertices of the graph. The minimum number of cops required to win on a given graph G is the cop number of G. We present asymptotic results for the game of Cops and Robber played on a random graph G(n,p) for a wide range of p=p(n). It has been shown that the cop number as a function of an average degree forms an intriguing zigzag shape. Time: 4:30 P.M. - 5:30 P.M. THURSDAY, November 12, 2009Zed Yilma, Department of Mathematical Sciences, Carnegie Mellon University Title: Set systems without a strong simplex ABSTRACT: A d-simplex is a collection of d+1 sets such that every d of them have non-empty intersection and the intersection of all of them is empty. A strong d-simplex is a collection of d+2 sets A,A_1, ... ,A_{d+1} such that {A_1, ... ,A_{d+1}} is a d-simplex, while A contains an element of each d-wise intersection. For n large and k \geq d+2, we prove that a k-uniform hypergraph F that contains no strong d-simplex has size at most {n-1 \choose k-1} with equality only when F is a star. Joint work with Tao Jiang and Oleg Pikhurko. Time: 4:30 P.M. - 5:30 P.M. THURSDAY, November 19, 2009Gabor Kun, DIMACS and Institute for Advanced Study Title: Proof of the Bollobas-Catlin-Eldridge conjecture ABSTRACT: We say that the graphs G and H with n vertices pack if G and H can be embedded to the same vertex set with no overlapping edges. Bollobas, Eldridge and independently Catlin conjectured that if that if (M(G)+1)(M(H)+1) < n+2 holds for the maximal degress then G and H pack. Aigner and Brandt and independently Alon and Fischer proved this in the case M(G),M(H)<3. Csaba, Shokoufandeh and Szemeredi proved it if M(G),M(H)<4. Bollobas, Kostochka and Nakprasit settled the case when one of the graphs is degenerate. Kaul, Kostochka and Yu showed that if M(G)M(H)<3/5n and the maximal degrees are large enough then G and H pack. We prove the conjecture for graphs with at least 108 vertices. Time: 4:30 P.M. - 5:30 P.M.
|
