Forthcoming Seminars › Seminar Series

Combinatorial Theory Seminar

Tue, 19/01/2010
14:30 		Peter Keevash (QMUL) Combinatorial Theory Seminar Add to calendar L3
Shadows and intersections: stability and new proofs
We give a short new proof of a version of the Kruskal-Katona theorem due to Lovász. Our method can be extended to a stability result, describing the approximate structure of configurations that are close to being extremal, which answers a question of Mubayi. This in turn leads to another combinatorial proof of a stability theorem for intersecting families, which was originally obtained by Friedgut using spectral techniques and then sharpened by Keevash and Mubayi by means of a purely combinatorial result of Frankl. We also give an algebraic perspective on these problems, giving yet another proof of intersection stability that relies on expansion of a certain Cayley graph of the symmetric group, and an algebraic generalisation of Lovász’s theorem that answers a question of Frankl and Tokushige.
Tue, 26/01/2010
14:30 		Jan Hladky (University of Warwick) Combinatorial Theory Seminar Add to calendar L3
Tree packing conjectures; Graceful tree labelling conjecture
A family of graphs $ H_1,...,H_k $ packs into a graph $ G $ if there exist pairwise edge-disjoint copies of $ H_1,...,H_k $ in $ G $. Gyarfas and Lehel conjectured that any family $ T_1, ..., T_n $ of trees of respective orders $ 1, ..., n $ packs into $ K_n $. A similar conjecture of Ringel asserts that $ 2n $ copies of any trees $ T $ on $ n+1 $ vertices pack into $ K_{2n+1} $. In a joint work with Boettcher, Piguet, Taraz we proved a theorem about packing trees. The theorem implies asymptotic versions of the above conjectures for families of trees of bounded maximum degree. Tree-indexed random walks controlled by the nibbling method are used in the proof. In a joint work with Adamaszek, Adamaszek, Allen and Grosu, we used the nibbling method to prove the approximate version of the related Graceful Tree Labelling conjecture for trees of bounded degree. In the talk we shall give proofs of both results. We shall discuss possible extensions thereof to trees of unbounded degree.
Tue, 09/02/2010
14:30 		David Conlon (Cambridge) Combinatorial Theory Seminar Add to calendar L3
Combinatorial theorems in random sets
The famous theorem of Szemerédi says that for any natural number $ k $ and any $ a>0 $ there exists $ n $ such that if $ N\ge n $ then any subset $ A $ of the set $ [N] =\{1, 2,\ldots , N\} $ of size $ |A| \ge a N $ contains an arithmetic progression of length $ k $. We consider the question of when such a theorem holds in a random set. More precisely, we say that a set $ X $ is $ (a, k) $-Szemerédi if every subset $ Y $ of $ X $ that contains at least $ a|X| $ elements contains an arithmetic progression of length $ k $. Let $ [N]_p $ be the random set formed by taking each element of $ [N] $ independently with probability $ p $. We prove that there is a threshold at about $ p = N^{-1/(k-1)} $ where the probability that $ [N]_p $ is $ (a, k) $-Szemerédi changes from being almost surely 0 to almost surely 1. There are many other similar problems within combinatorics. For example, Turán’s theorem and Ramsey’s theorem may be relativised, but until now the precise probability thresholds were not known. Our method seems to apply to all such questions, in each case giving the correct threshold. This is joint work with Tim Gowers.
Tue, 16/02/2010
14:30 		Vadim Lozin (Warwick) Combinatorial Theory Seminar Add to calendar L3
Boundary properties of graphs
The notion of a boundary graph property is a relaxation of that of a minimal property. Several fundamental results in graph theory have been obtained in terms of identifying minimal properties. For instance, Robertson and Seymour showed that there is a unique minimal minor-closed property with unbounded tree-width (the planar graphs), while Balogh, Bollobás and Weinreich identified nine minimal hereditary properties of labeled graphs with the factorial speed of growth. However, there are situations where the notion of minimal property is not applicable. A typical example of this type is given by graphs of large girth. It is known that for each particular value of k, the graphs of girth at least k are of unbounded tree-width and their speed of growth is superfactorial, while the limit property of this sequence (i.e., the acyclic graphs) has bounded tree-width and its speed of growth is factorial. To overcome this difficulty, the notion of boundary properties of graphs has been recently introduced. In the present talk, we use this notion in order to identify some classes of graphs which are well-quasi-ordered with respect to the induced subgraph relation.
Tue, 23/02/2010
14:30 		Lowell Beineke (Purdue) Combinatorial Theory Seminar Add to calendar L3
Line Graphs and Beyond
The line graph operation, in which the edges of one graph are taken as the vertices of a new graph with adjacency preserved, is arguably the most interesting of graph transformations.  In this survey, we will begin looking at characterisations of line graphs, focusing first on results related to our set of nine forbidden subgraphs. This will be followed by a discussion of some generalisations of line graphs, including our investigations into the Krausz dimension of a graph G, defined as the minimum, over all partitions of the edge-set of G into complete subgraphs, of the maximum number of subgraphs containing any vertex (the maximum in Krausz's characterisation of line graphs being 2).
Tue, 23/02/2010
14:30 		Lowell Beineke (Purdue) Combinatorial Theory Seminar Add to calendar L3
Line Graphs and Beyond
The line graph operation, in which the edges of one graph are taken as the vertices of a new graph with adjacency preserved, is arguably the most interesting of graph transformations. In this survey, we will begin looking at characterisations of line graphs, focusing first on results related to our set of nine forbidden subgraphs. This will be followed by a discussion of some generalisations of line graphs, including our investigations into the Krausz dimension of a graph G, defined as the minimum, over all partitions of the edge-set of G into complete subgraphs, of the maximum number of subgraphs containing any vertex (the maximum in Krausz's characterisation of line graphs being 2).
Tue, 02/03/2010
14:30 		Nicolas Trotignon (Paris) Combinatorial Theory Seminar Add to calendar L3
Decomposition of graphs and $ \chi $-boundedness
A graph is $ \chi $-bounded with a function $ f $ is for all induced subgraph H of G, we have $ \chi(H) \le f(\omega(H)) $.  Here, $ \chi(H) $ denotes the chromatic number of $ H $, and $ \omega(H) $ the size of a largest clique in $ H $. We will survey several results saying that excluding various kinds of induced subgraphs implies $ \chi $-boundedness. More precisely, let $ L $ be a set of graphs. If a $ C $ is the class of all graphs that do not any induced subgraph isomorphic to a member of $ L $, is it true that there is a function $ f $ that $ \chi $-bounds all graphs from $ C $? For some lists $ L $, the answer is yes, for others, it is no.   A decomposition theorems is a theorem saying that all graphs from a given class are either "basic" (very simple), or can be partitioned into parts with interesting relationship. We will discuss whether proving decomposition theorems is an efficient method to prove $ \chi $-boundedness. 
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