Past Combinatorial Theory Seminar

19 February 2013
14:30
Karen Johannson
Abstract
While usual percolation concerns the study of the connected components of random subgraphs of an infinite graph, bootstrap percolation is a type of cellular automaton, acting on the vertices of a graph which are in one of two states: `healthy' or `infected'. For any positive integer $r$, the $r$-neighbour bootstrap process is the following update rule for the states of vertices: infected vertices remain infected forever and each healthy vertex with at least $r$ infected neighbours becomes itself infected. These updates occur simultaneously and are repeated at discrete time intervals. Percolation is said to occur if all vertices are eventually infected. As it is often difficult to determine precisely which configurations of initially infected vertices percolate, one often considers a random case, with each vertex infected independently with a fixed probability $p$. For an infinite graph, of interest are the values of $p$ for which the probability of percolation is positive. I will give some of the history of this problem for regular trees and present some new results for bootstrap percolation on certain classes of randomly generated trees: Galton--Watson trees.
  • Combinatorial Theory Seminar
12 February 2013
14:30
Veselin Jungic
Abstract
I will describe how a search for the answer to an old question about the existence of monotone arithmetic progressions in permutations of positive integers led to the study of infinite words with bounded additive complexity. The additive complexity of a word on a finite subset of integers is defined as the function that, for a positive integer $n$, counts the maximum number of factors of length $n$, no two of which have the same sum.
  • Combinatorial Theory Seminar
5 February 2013
14:30
David Ellis
Abstract
Results of Bourgain and Kindler-Safra state that if $f$ is a Boolean function on $\{0,1\}^n$, and the Fourier transform of $f$ is highly concentrated on low frequencies, then $f$ must be close to a ‘junta’ (a function depending upon a small number of coordinates). This phenomenon is known as ‘Fourier stability’, and has several interesting consequences in combinatorics, theoretical computer science and social choice theory. We will describe some of these, before turning to the analogous question for Boolean functions on the symmetric group. Here, genuine stability does not occur; it is replaced by a weaker phenomenon, which we call ‘quasi-stability’. We use our 'quasi-stability' result to prove an isoperimetric inequality for $S_n$ which is sharp for sets of size $(n-t)!$, when $n$ is large. Several open questions remain. Joint work with Yuval Filmus (University of Toronto) and Ehud Friedgut (Weizmann Institute).
  • Combinatorial Theory Seminar
29 January 2013
14:30
Mireille Bousquet-Melou
Abstract
<p>A self-avoiding walk on a lattice is a walk that never visits the same vertex twice.&nbsp; Self-avoiding walks (SAW) have attracted interest for decades, first in statistical physics, where they are considered as polymer models, and then in combinatorics and in probability theory (the first mathematical contributions are probably due to John Hammersley, from Oxford, in the early sixties). However, their properties remain poorly understood in low dimension, despite the existence of remarkable conjectures. <br /><br />About two years ago, Duminil-Copin and Smirnov proved an "old" and remarkable conjecture of Nienhuis (1982), according to which the number of SAWs of length n on the honeycomb (hexagonal) lattice grows like mu^n, with mu=sqrt(2 +sqrt(2)). <br /><br />This beautiful result has woken up the hope to prove other simple looking conjectures involving these objects. I will thus present the proof of a younger conjecture (1995) by Batchelor and Yung, which deals with SAWs confined to a half-plane and interacting with its boundary.<br /><br />(joint work with N. Beaton, J. de Gier, H. Duminil-Copin and A. Guttmann)<br /><br /></p>
  • Combinatorial Theory Seminar
22 January 2013
14:30
Eoin Long
Abstract
Let $Q_n$ denote the graph of the $n$-dimensional cube with vertex set $\{0, 1\}^n$ in which two vertices are adjacent if they differ in exactly one coordinate. Suppose $G$ is a subgraph of $Q_n$ with average degree at least $d$. How long a path can we guarantee to find in $G$? My aim in this talk is to show that $G$ must contain an exponentially long path. In fact, if $G$ has minimum degree at least $d$ then $G$ must contain a path of length $2^d − 1$. Note that this bound is tight, as shown by a $d$-dimensional subcube of $Q^n$. I hope to give an overview of the proof of this result and to discuss some generalisations.
  • Combinatorial Theory Seminar
27 November 2012
14:30
Annika Heckel
Abstract

Rainbow connectivity is a new concept for measuring the connectivity of a graph which was introduced in 2008 by Chartrand, Johns, McKeon and Zhang. In a graph G with a given edge colouring, a rainbow path is a path all of whose edges have distinct colours. The minimum number of colours required to colour the edges of G so that every pair of vertices is joined by at least one rainbow path is called the rainbow connection number rc(G) of the graph G.

For any graph G, rc(G) >= diam(G). We will discuss rainbow connectivity in the random graph setting and present the result that for random graphs, rainbow connectivity 2 happens essentially at the same time as diameter 2. In fact, in the random graph process, with high probability the hitting times of diameter 2 and of rainbow connection number 2 coincide

  • Combinatorial Theory Seminar
20 November 2012
14:30
Matthias Lenz
Abstract

Given a finite list of vectors X in $\R^d$, one can define the box spline $B_X$. Box splines are piecewise polynomial functions that are used in approximation theory. They are also interesting from a combinatorial point of view and many of their properties solely depend on the structure of the matroid defined by the list X. The support of the box spline is a certain polytope called zonotope Z(X). We will show that if the list X is totally unimodular, any real-valued function defined on the set of lattice points in the interior of Z(X) can be extended to a function on Z(X) of the form $p(D)B_X$ in a unique way, where p(D) is a differential operator that is contained in the so-called internal P-space. This was conjectured by Olga Holtz and Amos Ron. The talk will focus on combinatorial aspects and all objects mentioned above will be defined. (arXiv:1211.1187)

  • Combinatorial Theory Seminar
13 November 2012
14:30
Asaf Ferber
Abstract
<p>In this talk we present a general method using permanent estimates in order to obtain results about counting and packing Hamilton cycles in dense graphs and oriented graphs. As a warm up we prove that every Dirac graph $G$ contains at least $(reg(G)/e)^n$ many distinct Hamilton cycles, where $reg(G)$ is the maximal degree of a spanning regular subgraph of $G$. We continue with strengthening a result of Cuckler by proving&nbsp;that the number of oriented Hamilton cycles in an almost $cn$-regular oriented graph is $(cn/e)^n(1+o(1))^n$, provided that $c$ is greater than $3/8$. Last, we prove that every graph $G$ of minimum degree at least $n/2+\epsilon n$ contains at least $reg_{even}(G)-\epsilon n$ edge-disjoint Hamilton cycles, where $reg_{even}(G)$ is the maximal&nbsp;even&nbsp;degree of a spanning regular subgraph of $G$. This proves an approximate version of a conjecture made by Osthus and K\"uhn.&nbsp; Joint work with Michael Krivelevich and Benny Sudakov.</p>
  • Combinatorial Theory Seminar
30 October 2012
14:30
Oliver Riordan
Abstract
In an Erd&#337;s--R\'enyi random graph above the phase transition, i.e., where there is a giant component, the size of (number of vertices in) this giant component is asymptotically normally distributed, in that its centred and scaled size converges to a normal distribution. This statement does not tell us much about the probability of the giant component having exactly a certain size. In joint work with B\'ela Bollob\'as we prove a `local limit theorem' answering this question for hypergraphs; the graph case was settled by Luczak and &#321;uczak. The proof is based on a `smoothing' technique, deducing the local limit result from the (much easier) `global' central limit theorem.
  • Combinatorial Theory Seminar
23 October 2012
16:30
Charles Semple
Abstract
Results that say local information is enough to guarantee global information provide the theoretical underpinnings of many reconstruction algorithms in evolutionary biology. Such results include Buneman's Splits-Equivalence Theorem and the Tree-Metric Theorem. The first result says that, for a collection $\mathcal C$ of binary characters, pairwise compatibility is enough to guarantee compatibility for $\mathcal C$, that is, there is a phylogenetic (evolutionary) tree that realises $\mathcal C$. The second result says that, for a distance matrix $D$, if every $4\times 4$ distance submatrix of $D$ is realisable by an edge-weighted phylogenetic tree, then $D$ itself is realisable by such a tree. In this talk, we investigate these and other results of this type. Furthermore, we explore the closely-related task of determining how much information is enough to reconstruct the correct phylogenetic tree.
  • Combinatorial Theory Seminar

Pages