Past Seminars › Seminar Series

Combinatorial Theory Seminar (past)

Tue, 08/03/2011
14:30 		Dominic Welsh (Oxford) Combinatorial Theory Seminar Add to calendar L3
"Random matroids"
I shall describe some recent results about the asymptotic behaviour of matroids. Specifically almost all matroids are simple and have probability at least 1/2 of being connected. Also, various quantitative results about rank, number of bases and number and size of circuits of almost all matroids are given. There are many open problems and I shall not assume any previous knowledge of matroids. This is joint work, see below. 1 D. Mayhew, M. Newman, D. Welsh and G. Whittle, On the asymptotic properties of connected matroids, European J. Combin. to appear 2 J. Oxley, C. Semple, L. Wasrshauer and D. Welsh, On properties of almost all matroids, (2011) submitted
Tue, 08/02/2011
16:30 		Lutz Warnke Combinatorial Theory Seminar Add to calendar SR2
"The C_ell -free process".
The $ C_\ell $-free process starts with the empty graph on $ n $ vertices and adds edges chosen uniformly at random, one at a time, subject to the condition that no copy of $ C_\ell $ is created. For every $ \ell \geq 4 $ we show that, with high probability as $ n \to \infty $, the maximum degree is $ O((n \log n)^{1/(\ell-1)}) $, which confirms a conjecture of Bohman and Keevash and improves on bounds of Osthus and Taraz. Combined with previous results this implies that the $ C_\ell $-free process typically terminates with $ \Theta(n^{\ell/(\ell-1)}(\log n)^{1/(\ell-1)}) $ edges, which answers a question of Erd\H{o}s, Suen and Winkler. This is the first result that determines the final number of edges of the more general $ H $-free process for a non-trivial class of graphs $ H $. We also verify a conjecture of Osthus and Taraz concerning the average degree, and obtain a new lower bound on the independence number. Our proof combines the differential equation method with a tool that might be of independent interest: we establish a rigorous way to `transfer' certain decreasing properties from the binomial random graph to the $ H $-free process.
Tue, 18/01/2011
14:30 		Christopher Dowden Combinatorial Theory Seminar Add to calendar L3
"Extremal planar graphs"
Tue, 16/11/2010
14:30 		John Talbot (UCL) Combinatorial Theory Seminar Add to calendar L3
Triangles in tripartite graphs
How many triangles must a graph of density d contain? This old question due to Erdos was recently answered by Razborov, after many decades of progress by numerous authors. We will consider the analogous question for tripartite graphs. Given a tripartite graph with prescribed edges densities between each pair of classes how many triangles must it contain?
Tue, 09/11/2010
14:30 		David Ellis (Cambridge) Combinatorial Theory Seminar Add to calendar L3
Intersecting families of graphs
A family of graphs F on a fixed set of n vertices is said to be triangle-intersecting if for any two graphs G,H in F, the intersection of G and H contains a triangle. Simonovits and Sos conjectured that such a family has size at most (1/8)2^{\binom{n}{2}}, and that equality holds only if Fconsists of all graphs containing some fixed triangle. Recently, the author, Yuval Filmus and Ehud Friedgut proved a strengthening of this conjecture, namely that if F is an odd-cycle-intersecting family of graphs, then |F| \leq (1/8) 2^{\binom{n}{2}}. Equality holds only if F consists of all graphs containing some fixed triangle. A stability result also holds: an odd-cycle-intersecting family with size close to the maximum must be close to a family of the above form. We will outline proofs of these results, which use Fourier analysis, together with an analysis of the properties of random cuts in graphs, and some results in the theory of Boolean functions. We will then discuss some related open questions. All will be based on joint work with Yuval Filmus (University of Toronto) and Ehud Friedgut (Hebrew University of Jerusalem).
Tue, 26/10/2010
14:30 		Raphael Clifford (Bristol) Combinatorial Theory Seminar Add to calendar L3
When not knowing can slow you down
Combinatorial pattern matching is a subject which has given us fast and elegant algorithms for a number of practical real world problems as well as being of great theoretical interest. However, when single character wildcards or so-called "don't know" symbols are introduced into the input, classic methods break down and it becomes much more challenging to find provably fast solutions. This talk will give a brief overview of recent results in the area of pattern matching with don't knows and show how techniques from fields as disperse FFTs, group testing and algebraic coding theory have been required to make any progress. We will, if time permits, also discuss the main open problems in the area.
Tue, 19/10/2010
14:30 		Jean Cardinal (Universite Libre de Bruxelles) Combinatorial Theory Seminar Add to calendar L3
Sorting under Partial Information and Partial Order Entropy
We revisit the problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (STOC 1992) showed that there exists a polynomial-time sorting algorithm achieving this bound up to a constant factor. They established a crucial link between the entropy of the input partial order and the information-theoretic lower bound. However, their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it unpractical. We develop efficient algorithms for sorting under partial information, derived from approximation and exact algorithms for computing the partial order entropy. This is joint work with S. Fiorini, G. Joret, R. Jungers, and I. Munro.
Tue, 12/10/2010
14:30 		Mary Cryan (Edinburgh) Combinatorial Theory Seminar Add to calendar L3
A couple of easy cases for counting Euler tours
The problem of checking existence for an Euler tour of a graph is trivial (are all vertex degrees even?). The problem of counting (or even approximate counting) Euler tours seems to be very difficult. I will describe two simple classes of graphs where the problem can be solved exactly in polynomial time. And also talk about the many many classes of graphs where no positive results are known.
Tue, 08/06/2010
14:30 		Bill Jackson (QMUL) Combinatorial Theory Seminar Add to calendar L3
Rigidity of direction-length frameworks
Consider a configuration of points in $ d $-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.
Fri, 04/06/2010
17:00 		Tristan Denley (Austin Peay) Combinatorial Theory Seminar Add to calendar L3
Sudoku... More than just a game
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, 01/06/2010
14:30 		Tom Sanders (Cambridge) Combinatorial Theory Seminar Add to calendar L3
Subspaces in sumsets: a problem of Bourgain and Green
Suppose that $ A \subset \mathbb F_2^n $ has density $ \Omega(1) $. How large a subspace is $ A+A:=\{a+a’:a,a’ \in A\} $ guaranteed to contain? We discuss this problem and how the the result changes as the density approaches $ 1/2 $.
Tue, 25/05/2010
14:30 		Anusch Taraz (Munich) Combinatorial Theory Seminar Add to calendar L3
Embedding spanning graphs into dense and sparse graphs
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 $ (1-1/r+\epsilon)n $ 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, 18/05/2010
16:30 		Alan Hammond (University of Oxford) Combinatorial Theory Seminar Add to calendar SR2
Phase boundary fluctuation and growth models
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, 18/05/2010
14:30 		Dan Archdeacon (University of Vermont) Combinatorial Theory Seminar Add to calendar L3
Trading 'tween crossings, crosscaps, and handles

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, 04/05/2010
16:30 		Balázs Ráth (Budapest) Combinatorial Theory Seminar Add to calendar SR2
Multigraph limits and aging of the edge reconnecting model
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, 04/05/2010
14:30 		Leslie Goldberg (University of Liverpool) Combinatorial Theory Seminar Add to calendar L3
Independent sets in bipartite graphs and approximating the partition function of the ferromagnetic Potts model
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, 09/03/2010
14:30 		Gregory Z. Gutin (Royal Holloway) Combinatorial Theory Seminar Add to calendar L3
Establishing Complexity of Problems Parameterized Above Average
In the Max Acyclic Subdigraph problem we are given a digraph $ D $ and ask whether $ D $ contains an acyclic subdigraph with at least $ k $ arcs. The problem is NP-complete and it is easy to see that the problem is fixed-parameter tractable, i.e., there is an algorithm of running time $ f(k)n $ for solving the problem, where $ f $ is a computable function of $ k $ only and $ n=|V(D)| $. The last result follows from the fact that the average number of arcs in an acyclic subdigraph of $ D $ is $ m/2 $, where $ m $ is the number of arcs in $ D $. Thus, it is natural to ask another question: does $ D $ have an acyclic subdigraph with at least $ m/2 +k $ arcs? Mahajan, Raman and Sikdar (2006, 2009), and by Benny Chor (prior to 2006) asked whether this and other problems parameterized above the average are fixed-parameter tractable (the problems include Max $ r $-SAT, Betweenness, and Max Lin). Most of there problems have been recently shown to be fixed-parameter tractable. Methods involved in proving these results include probabilistic inequalities, harmonic analysis of real-valued functions with boolean domain, linear algebra, and algorithmic-combinatorial arguments. Some new results obtained in this research are of potential interest for several areas of discrete mathematics and computer science. The examples include a new variant of the hypercontractive inequality and an association of Fourier expansions of real-valued functions with boolean domain with weighted systems of linear equations over $ F^n_2 $. I’ll mention results obtained together with N. Alon, R. Crowston, M. Jones, E.J. Kim, M. Mnich, I.Z. Ruzsa, S. Szeider, and A. Yeo.

For any corrections/updates to these listings, please contact seminars [-at-] maths [dot] ox [dot] ac [dot] uk.

Syndicate content