[Lowerbounds, Upperbounds]

Title: The Typical Structure of Graphs without Given Excluded Subgraphs
Speaker: Jozsi Balogh, University of Illinois at Urbana-Champaign
When: October 11, 16:30-17:30
Where: Wean Hall 5302

Abstract:

Let L be a finite family of graphs. We describe the typical structure of L-free graphs, improving our earlier results on the Erdos-Frankl-Rodl theorem, by proving our conjecture from our earlier paper. Let p=p(L)=min{F\in L:\chi(F)-1}. We shall prove that the structure of almost all L-free graphs are very similar to the Turan graph T_{n,p}, where “similarity” is measured in terms of graph theoretical parameters of L. Some more recent developements will be discussed as well. Joint work with B. Bollobas and M. Simonovits.

Who: Anupam Gupta
Where: NSH 1507
When: Noon, 2007-10-10

Stochastic Analysis of Online Steiner Tree

In the online Steiner tree problem, vertices come one-by-one and have to be connected to the root. The greedy algorithm is an O(log n) competitive algorithm, and this is the best possible. We will obtain better guarantees when the input sequence is not chosen by an adversary, but are just draws from some distribution over the vertices of the graph.