Combinatorial Theory Seminar
|
Tue, 29/04/2008 14:30 |
Mihyun Kang (Humboldt University) |
Combinatorial Theory Seminar  |
L3 |
| The phase transition is a phenomenon that appears in natural sciences in various contexts. In the random graph theory, the phase transition refers to a dramatic change in the number of vertices in the largest components by addition of a few edges around a critical value, which was first discussed on the standard random graphs in the seminal paper by Erdos and Renyi. Since then, the phase transition has been a central theme of the random graph theory. In this talk we discuss the phase transition in random graphs with a given degree sequence and random graph processes with degree constraints. | |||
|
Tue, 06/05/2008 14:30 |
Mike Paterson (Warwick) |
Combinatorial Theory Seminar |
L3 |
| How far can a stack of n identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be of order log n. Recently, we (Paterson and Zwick) constructed n-block stacks with overhangs of order n^{1/3}, exponentially better than previously thought possible. The latest news is that we (Paterson, Peres, Thorup, Winkler and Zwick) can show that order n^{1/3} is best possible, resolving the long-standing overhang problem up to a constant factor. I shall review the construction and describe the upper bound proof, which illustrates how methods founded in algorithmic complexity can be applied to a discrete optimization problem that has puzzled some mathematicians and physicists for more than 150 years. | |||
|
Tue, 13/05/2008 14:30 |
Louigi Addario-Berry (Oxford) |
Combinatorial Theory Seminar |
L3 |
| Joint work with Nicolas Broutin. The problem is related to searching in trees. Suppose we are given a complete binary tree (a rooted tree in which the root has degree 2 and every other vertex has degree 3) with independent, identically distributed random edge weights (say copies of some random variable X, which need not be non-negative). The depth d(v) of a vertex v is the number of edges on the path from v to the root. We give each vertex v the label S_v which is the sum of the edge weights on the path from v to the root. For positive integers n, we let M_n be the maximum label of any vertex at depth n, and let M^* = max {M_n: n =0,1,...}. It is of course possible that M^* is infinity. Under suitable moment assumptions on X, it is known that there is a constant A such that M_n/n –> A almost surely and in expectation. We call the cases A>0, A=0, and A< 0 supercritical, critical, and subcritical, respectively. When A <= 0 it makes sense to try to find the vertex of maximum weight M* in the whole tree. One possible strategy is to only explore the subtree T_0 containing the root consisting only of vertices of non-negative weight. With probability bounded away from zero this strategy finds the vertex of maximum weight. We derive precise information about the expected running time for this strategy. Equivalently, we derive precise information about the random variable |T_0|. In the process, we also derive rather precise information about M*. This answers a question of David Aldous. | |||
|
Tue, 20/05/2008 14:30 |
Ed Marchant (Cambridge) |
Combinatorial Theory Seminar |
L3 |
| Let G be the union of a red graph R and a blue graph B where every edge of G is in R or B (or both R and B). We call such a graph 2-painted. Given 2-painted graphs G and H, we say that G contains a copy of H if we can find a subgraph of G which is isomorphic to H. Let 0 | |||
|
Tue, 27/05/2008 14:30 |
David Ellis (Cambridge) |
Combinatorial Theory Seminar |
L3 |
| We call a family of permutations A in Sn 'intersecting' if any two permutations in A agree in at least one position. Deza and Frankl observed that an intersecting family of permutations has size at most (n-1)!; Cameron and Ku proved that equality is attained only by families of the form {σ in Sn: σ(i)=j} for i, j in [n]. We will sketch a proof of the following `stability' result: an intersecting family of permutations which has size at least (1-1/e + o(1))(n-1)! must be contained in {σ in Sn: σ(i)=j} for some i,j in [n]. This proves a conjecture of Cameron and Ku. In order to tackle this we first use some representation theory and an eigenvalue argument to prove a conjecture of Leader concerning cross-intersecting families of permutations: if n >= 4 and A,B is a pair of cross-intersecting families in Sn, then |A||B| <= [(n-1)!]2, with equality iff A=B= {σ in Sn: σ(i)=j} for some i,j in [n]. A by-product of this is a relatively clean proof of equality in the Deza-Frankl Theorem. | |||
|
Tue, 03/06/2008 14:30 |
F.M. Dong (Singapore) |
Combinatorial Theory Seminar |
L3 |
| For any simple graph G and any positive integer lambda, let P(G,lambda) denote the number of mappings f from V(G) to {1,2,..,lambda} such that f(u) not= f(v) for every two adjacent vertices u and v in G. It can be shown that P(G,lambda) = \sum_{A \subseteq E} (-1)^{|A|} lambda^{c(A)} where E is the edge set of G and c(A) is the number of components of the spanning subgraph of G with edge set A. Hence P(G,lambda) is really a polynomial of lambda. Many results on the chromatic polynomial of a graph have been discovered since it was introduced by Birkhoff in 1912. However, there are still many unsolved problems and this talk will introduce the progress of some problems and also some new problems proposed recently. | |||
|
Tue, 10/06/2008 14:30 |
Julius Borcea (Stockholm) |
Combinatorial Theory Seminar |
L3 |
| Linear operators preserving non-vanishing properties are an important tool in e.g. combinatorics, the Lee-Yang program on phase transitions, complex analysis, matrix theory. We characterize all linear operators on spaces of multivariate polynomials preserving the property of being non-vanishing when the variables are in prescribed open circular domains, which solves the higher dimensional counterpart of a long-standing classification problem going back to Pólya-Schur. This also leads to a self-contained theory of multivariate stable polynomials and a natural framework for dealing with Lee-Yang and Heilmann-Lieb type problems in a uniform manner. The talk is based on joint work with Petter Brändén. | |||
