MSI Weekly Bulletin - Week starting Monday 6 August, 2007

A $t-(v,k,\lambda_{t})$ design D, for $t\geq 0$, is an ordered pair $(V,B)$, where $V$ is a set of $v$ elements, called points, $B$ is a collection (multiset) of $k$-subsets of $V$, called blocks, such that each $t$-subset of $V$ belongs to exactly $\lambda_{t}$ blocks. A defining set of a $t-(v,k,\lambda_{t}$) design is a set of blocks which is a subset of a unique t-design with the given parameters. A minimal defining set is a defining set, none of whose proper subsets is a defining set. A smallest defining set is one with smallest cardinality. This talk will summaries the ideas of earlier algorithms and proposes a new and more efficient algorithm that finds all non-isomorphic minimal defining sets of a given $t$-design. The complete list of minimal defining sets of the full $2-(7,3,5)$ design, $2-(15,3,1)$ designs, $2-(25,5,1)$ design and $2-(31,6,1)$ design were found. Some new theoretical technics will also be given for finding the minimal defining sets of $t-(v,k,\lambda_{t})$ designs. BIO: http://home.ku.edu.tr/~eyazici/

Gibbs sampling also known as Glauber dynamics is a popular technique for sampling high dimensional distributions defined on graphs. Of special interest is the behavior of Gibbs sampling on the Erdos-Renyi random graph G(n, d/n) which is sparse on average but has some nodes of degree order log n/ log log n. Most rigorous bounds for mixing times critically depend on the maximum degree of the graph, we are able to show polynomial mixing times for uniform colourings on random graphs with sufficiently many colours. Our results also hold for a broad range of models including the Ising model at high temperatures and the hardcore model at low activities. Joint work with Elchanan Mossel.

To use the "probabilistic method", one typically constructs a probability space P in order to prove something about a given structure S. Normally P is built by considering some random variables defined in terms of S. I will give some examples of this, and then describe a new kind of probabilistic method. It works in an unlikely-sounding way: we can find typical properties of random structures in a large set C, and then show separately that the properties "transfer" to all structures in C. Of course, this is only applicable under special circumstances. Present applications involve regular graphs of large girth. (The girth is the length of the shortest cycle.) Results obtained include lower bounds on the largest independent set (set of vertices no two of which are adjacent). These bounds significantly improve Shearer's bounds, which have stood since 1991. Another application gives new upper bounds on the minimum size of dominating sets in graphs with given maximum degree and large girth.