Combinatorial Theory Seminar
|
Tue, 21/05 14:30 |
Paul Seymour (Princeton) |
Combinatorial Theory Seminar  |
L3 |
| The “k-commodity flow problem” is: we are given k pairs of vertices of a graph, and we ask whether there are k flows in the graph, where the ith flow is between the ith pair of vertices, and has total value one, and for each edge, the sum of the absolute values of the flows along it is at most one. We may also require the flows to be 1/2-integral, or indeed 1/p-integral for some fixed p. If the problem is feasible (that is, the desired flows exist) then it is still feasible after contracting any edge, so let us say a flow problem is “critical” if it is infeasible, but becomes feasible when we contract any edge. In many special cases, all critical instances have only two vertices, but if we ask for integral flows (that is, p = 1, essentially the edge-disjoint paths problem), then there arbitrarily large critical instances, even with k = 2. But it turns out that p = 1 is the only bad case; if p>1 then all critical instances have bounded size (depending on k, but independent of p), and the same is true if there is no integrality requirement at all. The proof gives rise to a very simple algorithm for the k edge-disjoint paths problem in 4-edge-connected graphs. | |||
|
Tue, 28/05 14:30 |
Christina Goldschmidt (University of Oxford) |
Combinatorial Theory Seminar |
L3 |
Consider the complete graph on n vertices with independent and identically distributed edge-weights having some absolutely continuous distribution. The minimum spanning tree (MST) is simply the spanning subtree of smallest weight. It is straightforward to construct the MST using one of several natural algorithms. Kruskal's algorithm builds the tree edge by edge starting from the globally lowest-weight edge and then adding other edges one by one in increasing order of weight, as long as they do not create any cycles. At each step of this process, the algorithm has generated a forest, which becomes connected on the final step. In this talk, I will explain how it is possible to exploit a connection between the forest generated by Kruskal's algorithm and the Erdös-Rényi random graph in order to prove that  , the MST of the complete graph, possesses a scaling limit as  tends to infinity. In particular, if we think of as a metric space (using the graph distance), rescale edge-lengths by  , and endow the vertices with the uniform measure, then converges in distribution in the sense of the Gromov-Hausdorff-Prokhorov distance to a certain random measured real tree.
This is joint work with Louigi Addario-Berry (McGill), Nicolas Broutin (INRIA Paris-Rocquencourt) and Grégory Miermont (ENS Lyon). |
|||
|
Tue, 28/05 16:30 |
Po-Shen Loh (CMU) |
Combinatorial Theory Seminar |
SR2 |
| The first application of Szemeredi's regularity method was the following celebrated Ramsey-Turan result proved by Szemeredi in 1972: any K_4-free graph on N vertices with independence number o(N) has at most (1/8 + o(1))N^2 edges. Four years later, Bollobas and Erdos gave a surprising geometric construction, utilizing the isodiametric inequality for the high dimensional sphere, of a K_4-free graph on N vertices with independence number o(N) and (1/8 - o(1)) N^2 edges. Starting with Bollobas and Erdos in 1976, several problems have been asked on estimating the minimum possible independence number in the critical window, when the number of edges is about N^2 / 8. These problems have received considerable attention and remained one of the main open problems in this area. More generally, it remains an important problem to determine if, for certain applications of the regularity method, alternative proofs exist which avoid using the regularity lemma and give better quantitative estimates. In this work, we develop new regularity-free methods which give nearly best-possible bounds, solving the various open problems concerning this critical window. Joint work with Jacob Fox and Yufei Zhao. | |||
|
Wed, 05/06 11:00 |
Combinatorial Theory Seminar |
L1 | |
