# Past 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
23 October 2012
14:30
Van Vu
Abstract
Consider random matrices with independent entries (in both hermitian and non-hermtian setting). An old and basic question is:<br /><span></span><br /> What is the law of the determinant ?</span><br /><span></span><br /> I am going to give a survey about this problem, focusing on recent developments and new techniques, along with several open questions.</span><br /><span></span><br /><span>(partially based on joint works with H. Nguyen and T. Tao).</span>
• Combinatorial Theory Seminar
9 October 2012
14:30
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.
• Combinatorial Theory Seminar
22 May 2012
14:30
Jozef Skokan
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.
• Combinatorial Theory Seminar
8 May 2012
14:30
Hao Huang
Abstract
<p>Graphs and digraphs behave quite diff erently, 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.</p> <p>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 fi nd subgraphs of high minimum degrees, and also long cycles in Eulerian digraphs. These results were motivated by a conjecture of Bollob\'as and Scott.</p> <p>Joint work with Ma, Shapira, Sudakov and Yuster</p>
• Combinatorial Theory Seminar
24 April 2012
14:30
Choongbum Lee
Abstract
<p>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&nbsp;of a graph is a bipartition in which the size of the two parts&nbsp;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,&nbsp;which can also be used to answer several questions and conjectures of Bollob\'as and Scott on&nbsp;judicious bisections of graphs.<br />Joint work with Po-Shen Loh and Benny Sudakov</p>
• Combinatorial Theory Seminar