Research group
Combinatorics
Tue, 20 Nov 2012
14:30
SR1

"Interpolation, box splines, and lattice points in zonotopes"

Matthias Lenz
(Merton College)
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)

Tue, 13 Nov 2012

14:30 - 15:30
SR1

Counting and packing Hamilton cycles in dense graphs and oriented graphs

Asaf Ferber
(Tel Aviv)
Abstract

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 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 even degree of a spanning regular subgraph of $G$. This proves an approximate version of a conjecture made by Osthus and K\"uhn.  Joint work with Michael Krivelevich and Benny Sudakov.

Tue, 30 Oct 2012

14:30 - 15:30
SR1

Local limit theorems for giant components

Oliver Riordan
(Oxford)
Abstract

In an Erdő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 Łuczak.

The proof is based on a `smoothing' technique, deducing the local

limit result from the (much easier) `global' central limit theorem.

Tue, 23 Oct 2012

16:30 - 17:30
SR2

Realising evolutionary trees with local information

Charles Semple
(University of Canterbury)
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.

Tue, 23 Oct 2012

14:30 - 15:30
SR1

Law of the determinant

Van Vu
(Yale)
Abstract
Consider random matrices with independent entries (in both hermitian and non-hermtian setting). An old and basic question is:

What is the law of the determinant ?

I am going to give a survey about this problem, focusing on recent developments and new techniques, along with several open questions.

(partially based on joint works with H. Nguyen and T. Tao).
Tue, 09 Oct 2012

14:30 - 15:30
L3

Tiling Euclidean space with a polytope, by translations

Sinai Robins
(Nanyang Technological University)
Abstract

We study the problem of covering R^d by overlapping translates of a convex polytope, such that almost every point of R^d is covered exactly k times. Such a covering of Euclidean space by a discrete set of translations is called a k-tiling. The investigation of simple tilings by translations (which we call 1-tilings in this context) began with the work of Fedorov and Minkowski, and was later extended by Venkov and McMullen to give a complete characterization of all convex objects that 1-tile R^d. By contrast, for k ≥ 2, the collection of polytopes that k-tile is much wider than the collection of polytopes that 1-tile, and there is currently no known analogous characterization for the polytopes that k-tile. Here we first give the necessary conditions for polytopes P that k-tile, by proving that if P k-tiles R^d by translations, then it is centrally symmetric, and its facets are also centrally symmetric. These are the analogues of Minkowski’s conditions for 1-tiling polytopes, but it turns out that very new methods are necessary for the development of the theory. In the case that P has rational vertices, we also prove that the converse is true; that is, if P is a rational, centrally symmetric polytope, and if P has centrally symmetric facets, then P must k-tile R^d for some positive integer k.

Tue, 22 May 2012

14:30 - 15:30
L3

Strong Ramsey saturation for cycles

Jozef Skokan
(LSE)
Abstract

We call a graph $H$ \emph{Ramsey-unsaturated} if there is an edge in the

complement of $H$ such that the Ramsey number $r(H)$ of $H$ does not

change upon adding it to $H$. This notion was introduced by Balister,

Lehel and Schelp who also showed that cycles (except for $C_4$) are

Ramsey-unsaturated, and conjectured that, moreover, one may add {\em

any} chord without changing the Ramsey number of the cycle $C_n$, unless

$n$ is even and adding the chord creates an odd cycle.

We prove this conjecture for large cycles by showing a stronger

statement: If a graph $H$ is obtained by adding a linear number of

chords to a cycle $C_n$, then $r(H)=r(C_n)$, as long as the maximum

degree of $H$ is bounded, $H$ is either bipartite (for even $n$) or

almost bipartite (for odd $n$), and $n$ is large.

This motivates us to call cycles \emph{strongly} Ramsey-unsaturated.

Our proof uses the regularity method.

Tue, 08 May 2012

14:30 - 15:30
L3

Extremal Problems in Eulerian Digraphs

Hao Huang
(UCLA)
Abstract

Graphs and digraphs behave quite differently, and many classical results for graphs are often trivially false when extended to general digraphs. Therefore it is usually necessary to restrict to a smaller family of digraphs to obtain meaningful results. One such very natural family is Eulerian digraphs, in which the in-degree equals out-degree at every vertex.

In this talk, we discuss several natural parameters for Eulerian digraphs and study their connections. In particular, we show that for any Eulerian digraph G with n vertices and m arcs, the minimum feedback arc set (the smallest set of arcs whose removal makes G acyclic) has size at least $m^2/2n^2+m/2n$, and this bound is tight. Using this result, we show how to find subgraphs of high minimum degrees, and also long cycles in Eulerian digraphs. These results were motivated by a conjecture of Bollob\'as and Scott.

Joint work with Ma, Shapira, Sudakov and Yuster

Tue, 24 Apr 2012

14:30 - 15:30
L3

Large and judicious bisections of graphs

Choongbum Lee
(UCLA)
Abstract

It is very well known that every graph on $n$ vertices and $m$ edges admits a bipartition of size at least $m/2$. This bound can be improved to $m/2 + (n-1)/4$ for connected graphs, and $m/2 + n/6$ for graphs without isolated vertices, as proved by Edwards, and Erd\"os, Gy\'arf\'as, and Kohayakawa, respectively. A bisection of a graph is a bipartition in which the size of the two parts differ by at most 1. We prove that graphs with maximum degree $o(n)$ in fact admit a bisection which asymptotically achieves the above bounds.These results follow from a more general theorem, which can also be used to answer several questions and conjectures of Bollob\'as and Scott on judicious bisections of graphs.
Joint work with Po-Shen Loh and Benny Sudakov

Tue, 28 Feb 2012

14:30 - 15:30
L3

On packing and covering in hypergraphs

Penny Haxell (Waterloo)
Abstract

We discuss some recent developments on the following long-standing problem known as Ryser's

conjecture. Let $H$ be an $r$-partite $r$-uniform hypergraph. A matching in $H$ is a set of disjoint

edges, and we denote by $\nu(H)$ the maximum size of a matching in $H$. A cover of $H$ is a set of

vertices that intersects every edge of $H$. It is clear that there exists a cover of $H$ of size at

most $r\nu(H)$, but it is conjectured that there is always a cover of size at most $(r-1)\nu(H)$.

Subscribe to Combinatorial Theory Seminar