Combinatorial Theory Seminar
|
Tue, 04/05/2010 14:30 |
Leslie Goldberg (University of Liverpool) |
Combinatorial Theory Seminar  |
L3 |
| This talk considers the problem of sampling an independent set uniformly at random from a bipartite graph (equivalently, the problem of approximately counting independent sets in a bipartite graph). I will start by discussing some natural Markov chain approaches to this problem, and show why these lead to slow convergence. It turns out that the problem is interesting in terms of computational complexity – in fact, it turns out to be equivalent to a large number of other problems, for example, approximating the partition function of the “ferromagnetic Ising model’’ (a 2-state particle model from statistical physics) in the presence of external fields (which are essentially vertex weights). These problems are all complete with respect to approximation-preserving reductions for a logically-defined complexity class, which means that if they can be approximated efficiently, so can the entire class. In recent work, we show some connections between this class of problems and the problem of approximating the partition function of the “ferromagnetic Potts model’’ which is a generalisation of the Ising model—our result holds for q>2 spins. (This corresponds to the approximation problem for the Tutte polynomial in the upper quadrant above the hyperbola q=2.) That result was presented in detail at a recent talk given by Mark Jerrum at Oxford’s one-day meeting in combinatorics. So I will just give a brief description (telling you what the Potts model is and what the result is) and then conclude with some more recently discovered connections to counting graph homomorphisms and approximating the cycle index polynomial. | |||
|
Tue, 04/05/2010 16:30 |
Balázs Ráth (Budapest) |
Combinatorial Theory Seminar |
SR2 |
| We define the edge reconnecting model, a random multigraph evolving in time. At each time step we change one endpoint of a uniformly chosen edge: the new endpoint is chosen by linear preferential attachment. We consider a sequence of edge reconnecting models where the sequence of initial multigraphs is convergent in a sense which is a natural generalization of the Lovász-Szegedy notion of convergence of dense graph sequences. We investigate how the limit objects evolve under the edge reconnecting dynamics if we rescale time properly: we give the complete characterization of the time evolution of the limiting object from its initial state up to the stationary state using the theory of exchangeable arrays, the Pólya urn model, queuing and diffusion processes. The number of parallel edges and the degrees evolve on different timescales and because of this the model exhibits “aging”. | |||
|
Tue, 18/05/2010 14:30 |
Dan Archdeacon (University of Vermont) |
Combinatorial Theory Seminar |
L3 |
|
Given a graph we want to draw it in the plane; well we *want* to draw it in the plane, but sometimes we just can't. So we resort to various compromises. Sometimes we add crossings and try to minimize the crossings. Sometimes we add handles and try to minimize the number of handles. Sometimes we add crosscaps and try to minimize the number of crosscaps. Sometimes we mix these parameters: add a given number of handles (or crosscaps) and try to minimize the number of crossings on that surface. What if we are willing to trade: say adding a handle to reduce the number of crossings? What can be said about the relative value of such a trade? Can we then add a second handle to get an even greater reduction in crossings? If so, why didn't we trade the second handle in the first place? What about a third handle? The crossing sequence cr_1, cr_2, ... , cr_i, ... has terms the minimum number of crossings over all drawings of G on a sphere with i handles attached. The non-orientable crossing sequence is defined similarly. In this talk we discuss these crossing sequences. By Dan Archdeacon, Paul Bonnington, Jozef Siran, and citing works of others. |
|||
|
Tue, 18/05/2010 16:30 |
Alan Hammond (University of Oxford) |
Combinatorial Theory Seminar |
SR2 |
| The Wulff droplet arises by conditioning a spin system in a dominant phase to have an excess of signs of opposite type. These gather together to form a droplet, with a macroscopic Wulff profile, a solution to an isoperimetric problem. I will discuss recent work proving that the phase boundary that delimits the signs of opposite type has a characteristic scale, both at the level of exponents and their logarithmic corrections. This behaviour is expected to be shared by a broad class of stochastic interface models in the Kardar-Parisi-Zhang class. Universal distributions such as Tracy-Widom arise in this class, for example, as the maximum behaviour of repulsive particle systems. time permitting, I will explain how probabilistic resampling ideas employed in spin systems may help to develop a qualitative understanding of the random mechanisms at work in the KPZ class. | |||
|
Tue, 25/05/2010 14:30 |
Anusch Taraz (Munich) |
Combinatorial Theory Seminar |
L3 |
In this talk we will first survey results which guarantee the existence of
spanning subgraphs in dense graphs. This will lead us to the proof of the
bandwidth-conjecture by Bollobas and Komlos, which states that any graph
with minimum degree at least  contains every r-chromatic graph
with bounded maximum degree and sublinear bandwidth as a spanning subgraph.
We will then move on to discuss the analogous question for a host graph that
is obtained by starting from a sparse random graph G(n,p) and deleting a
certain portion of the edges incident at every vertex.
This is joint work with J. Boettcher, Y. Kohayakawa and M. Schacht. |
|||
|
Tue, 01/06/2010 14:30 |
Tom Sanders (Cambridge) |
Combinatorial Theory Seminar |
L3 |
Suppose that  has density  . How
large a subspace is  guaranteed to contain? We
discuss this problem and how the the result changes as the density
approaches  . |
|||
|
Fri, 04/06/2010 17:00 |
Tristan Denley (Austin Peay) |
Combinatorial Theory Seminar |
L3 |
| Whether as the sudoku puzzles of popular culture or as restricted coloring problems on graphs or hypergraphs, completing partial Latin squares and cubes present a framework for a variety of intriguing problems. In this talk we will present several recent results on completing partial Latin squares and cubes. | |||
|
Tue, 08/06/2010 14:30 |
Bill Jackson (QMUL) |
Combinatorial Theory Seminar |
L3 |
Consider a configuration of points in  -dimensional Euclidean space
together with a set of constraints
which fix the direction or the distance between some pairs of points.
Basic questions are whether the constraints imply that the configuration
is unique or locally unique up to congruence, and whether it is bounded. I
will describe some solutions
and partial solutions to these questions. |
|||
