Past Combinatorial Theory Seminar

10 March 2015
14:30
Julia Böttcher
Abstract

Dellamonica, Kohayakawa, Rödl and Ruciński showed that for $p=C(\log n/n)^{1/d}$ the random graph $G(n,p)$ contains asymptotically almost surely all spanning graphs $H$ with maximum degree $d$ as subgraphs. In this talk I will discuss a resilience version of this result, which shows that for the same edge density, even if a $(1/k-\epsilon)$-fraction of the edges at every vertex is deleted adversarially from $G(n,p)$, the resulting graph continues to contain asymptotically almost surely all spanning $H$ with maximum degree $d$, with sublinear bandwidth and with at least $C \max\{p^{-2},p^{-1}\log n\}$ vertices not in triangles. Neither the restriction on the bandwidth, nor the condition that not all vertices are allowed to be in triangles can be removed. The proof uses a sparse version of the Blow-Up Lemma. Joint work with Peter Allen, Julia Ehrenmüller, Anusch Taraz.

  • Combinatorial Theory Seminar
3 March 2015
14:30
Vytautas Gruslys
Abstract

Suppose that we have a tile $T$ in say $\mathbb{Z}^2$, meaning a finite subset of $\mathbb{Z}^2$. It may or may not be the case that $T$ tiles $\mathbb{Z}^2$, in the sense that $\mathbb{Z}^2$ can be partitioned into copies of $T$. But is there always some higher dimension $\mathbb{Z}^d$ that can be tiled with copies of $T$? We prove that this is the case: for any tile in $\mathbb{Z}^2$ (or in $\mathbb{Z}^n$, any $n$) there is a $d$ such that $\mathbb{Z}^d$ can be tiled with copies of it. This proves a conjecture of Chalcraft.

  • Combinatorial Theory Seminar
24 February 2015
14:30
Mark Walters
Abstract

Suppose we have a finite graph. We can view this as a resistor network where each edge has unit resistance. We can then calculate the resistance between any two vertices and ask questions like `which graph with $n$ vertices and $m$ edges minimises the average resistance between pairs of vertices?' There is a `obvious' solution; we show that this answer is not correct.

This problem was motivated by some questions about the design of statistical experiments (and has some surprising applications in chemistry) but this talk will not assume any statistical knowledge.

This is joint work with Robert Johnson.

  • Combinatorial Theory Seminar
17 February 2015
14:30
Shoham Letzter
Abstract
In 2011, Schelp introduced the idea of considering Ramsey-Turán type problems for graphs with large minimum degree. Inspired by his questions, Balogh, Barat, Gerbner, Gyárfás, and Sárközy suggested the following conjecture. Let $G$ be a graph on $n$ vertices with minimum degree at least $3n/4$. Then for every red and blue colouring of the edges of $G$, the vertices of $G$ may be partitioned into two vertex-disjoint cycles, one red and the other blue. They proved an approximate version of the conjecture, and recently DeBiasio and Nelsen obtained stronger approximate results. We prove the conjecture exactly (for large $n$). I will give an overview of the history of this problem and describe some of the tools that are used for the proof. I will finish with a discussion of possible future work for which the methods we use may be applicable.
  • Combinatorial Theory Seminar
10 February 2015
14:30
Luka Milicevic
Abstract

Erdős asked the following question: given a positive integer $n$, what is the largest integer $k$ such that any set of $n$ points in a plane, with no $4$ on a line, contains $k$ points no $3$ of which are collinear? Füredi proved that $k = o(n)$. Cardinal, Toth and Wood extended this result to $\mathbb{R}^3$, finding sets of $n$ points with no $5$ on a plane whose subsets with no $4$ points on a plane have size $o(n)$, and asked the question for the higher dimensions. For given $n$, let $k$ be largest integer such that any set of $n$ points in $\mathbb{R}^d$ with no more than $d + 1$ cohyperplanar points, has $k$ points with no $d + 1$ on a hyperplane. Is $k = o(n)$? We prove that $k = o(n)$ for any fixed $d \geq 3$.

  • Combinatorial Theory Seminar
3 February 2015
14:30
Jonathan Lee
Abstract

The Number Field Sieve is the current practical and theoretical state of the art algorithm for factoring. Unfortunately, there has been no rigorous analysis of this type of algorithm. We randomise key aspects of the number theory, and prove that in this variant congruences of squares are formed in expected time $L(1/3, 2.88)$. These results are tightly coupled to recent progress on the distribution of smooth numbers, and we provide additional tools to turn progress on these problems into improved bounds.

  • Combinatorial Theory Seminar
27 January 2015
14:30
Bhargav Narayanan
Abstract

Given two probability distributions $P_R$ and $P_B$ on the positive reals with finite means, colour the real line alternately with red and blue intervals so that the lengths of the red intervals have distribution $P_R$, the lengths of the blue intervals have distribution $P_B$, and distinct intervals have independent lengths. Now iteratively update this colouring of the line by coalescing intervals: change the colour of any interval that is surrounded by longer intervals so that these three consecutive intervals subsequently form a single monochromatic interval. Say that a colour (either red or blue) `wins' if every point of the line is eventually of that colour. I will attempt to answer the following question: under what natural conditions on the distributions is one of the colours almost surely guaranteed to win?

  • Combinatorial Theory Seminar
2 December 2014
14:30
Michal Przykucki
Abstract
We prove that there exist natural generalizations of the classical bootstrap percolation model on $\mathbb{Z}^2$ that have non-trivial critical probabilities, and moreover we characterize all homogeneous, local, monotone models with this property. Joint work with Paul Balister, Béla Bollobás and Paul Smith.
  • Combinatorial Theory Seminar
11 November 2014
14:30
Jorge Ramirez-Alfonsin
Abstract
Let $P(M)$ be the matroid base polytope of a matroid $M$. A decomposition of $P(M)$ is a subdivision of the form $P(M)=\cup_{i=1}^t P(M_i)$ where each $P(M_i)$ is also a matroid base polytope for some matroid $M_i$, and for each $1\le i\neq j\le t$ the intersection $P(M_i)\cap P(M_j)$ is a face of both $P(M_i)$ and $P(M_j)$. In this talk, we shall discuss some results on hyperplane splits, that is, polytope decomposition when $t=2$. We present sufficient conditions for $M$ so $P(M)$ has a hyperplane split and a characterization when $P(M_i\oplus M_j)$ has a hyperplane split, where $M_i\oplus M_j$ denotes the direct sum of $M_i$ and $M_j$. We also show that $P(M)$ has not a hyperplane split if $M$ is binary. Finally, we present some recent results concerning the existence of decompositions with $t\ge 3$.
  • Combinatorial Theory Seminar

Pages