Past Combinatorial Theory Seminar

E.g., 2019-12-06
E.g., 2019-12-06
E.g., 2019-12-06
3 December 2019
14:00
Yanitsa Pehova

Further Information: 

We say that a sequence $\{\Pi_i\}$ of permutations is quasirandom if, for each $k\geq 2$ and each $\sigma\in S_k$, the probability that a uniformly chosen $k$-set of entries of $\Pi_i$ induces $\sigma$ tends to $1/k!$ as $i$ tends to infinity. It is known that a much weaker condition already forces $\{\Pi_i\}$ to be quasirandom; namely, if the above property holds for all $\sigma\in S_4$. We further weaken this condition by exhibiting sets $S\subseteq S_4$, such that if a randomly chosen $k$-set of entries of $\Pi_i$ induces an element of $S$ with probability tending to $|S|/24$, then $\{\Pi_i\}$ is quasirandom. Moreover, we are able to completely characterise the sets $S$ with this property. In particular, there are exactly ten such sets, the smallest of which has cardinality eight. 
This is joint work with Timothy Chan, Daniel Kráľ, Jon Noel, Maryam Sharifzadeh and Jan Volec.

  • Combinatorial Theory Seminar
26 November 2019
14:00
Jason Long

Further Information: 

Latin squares arise from the multiplication tables of groups, but the converse is not true in general. Given a Latin square A, we can define a group operation giving A as its multiplication table only when A satisfies a suitable associativity constraint. This observation leads to a natural question concerning the '1%' version: if A is only partially associative, can we still obtain something resembling a group structure? I will talk about some joint work with Tim Gowers on this question.

  • Combinatorial Theory Seminar
19 November 2019
14:00
Endre Csóka

Further Information: 

We analyze the asymptotic relative size of the largest independent set of a random d-regular graph on n → ∞ vertices. This problem is very different depending on d because of a surprising phase transition. This is somewhat similar to finding the density of ``water'' above and below its freezing point. These phase transitions are related to algorithmic thresholds, mixing properties, counting, graph reconstruction, graph limits and other questions. We are still far from a complete understanding of all these questions. Our tools are partially coming from statistical physics. 

  • Combinatorial Theory Seminar
12 November 2019
14:00
Julia Boettcher

Further Information: 

The r-​colour size-​Ramsey number of a graph G is the minimum number of edges of a graph H such that any r-​colouring of the edges of H has a monochromatic G-​copy. Random graphs play an important role in the study of size-​Ramsey numbers. Using random graphs, we establish a new bound on the size-​Ramsey number of D-​degenerate graphs with bounded maximum degree.

In the talk I will summarise what is known about size-​Ramsey numbers, explain the connection to random graphs and their so-​called partition universality, and outline which methods we use in our proof.

Based on joint work with Peter Allen.  
 

  • Combinatorial Theory Seminar
5 November 2019
14:00
Julian Sahasrabudhe

Further Information: 

Given a collection of subsets of a set X, the basic problem in combinatorial discrepancy theory is to find an assignment of 1,-1 to the elements of X so that the sums over each of the given sets is as small as possible. I will discuss how the sort of combinatorial reasoning used to think about problems in combinatorial discrepancy can be used to solve an old conjecture of J.E. Littlewood on the existence of ``flat Littlewood polynomials''.

This talk is based on joint work with Paul Balister, Bela Bollobas, Rob Morris and Marius Tiba.
 

  • Combinatorial Theory Seminar
29 October 2019
14:00
Daniel Korandi

Further Information: 

How many monochromatic paths, cycles or general trees does one need to cover all vertices of a given r-edge-colored graph G? Such questions go back to the 1960's and have been studied intensively in the past 50 years. In this talk, I will discuss what we know when G is the random graph G(n,p). The problem turns out to be related to the following question of Erdős, Hajnal and Tuza: What is the largest possible cover number of an r-uniform hypergraph where any k edges have a cover of size l.

The results I mention give new bounds for these problems, and answer some questions by Bal and DeBiasio, and others. The talk is based on collaborations with Bucić, Mousset, Nenadov, Škorić and Sudakov.

  • Combinatorial Theory Seminar
22 October 2019
14:00
Matthew Jenssen

Further Information: 

We present a detailed probabilistic and structural analysis of the set of weighted homomorphisms from the discrete torus Z_m^n, where m is even, to any fixed graph. Our main result establishes the "phase coexistence" phenomenon in a strong form: it shows that the corresponding probability distribution on such homomorphisms is close to a distribution defined constructively as a certain random perturbation of some "dominant phase". This has several consequences, including solutions (in a strong form) to conjectures of Engbers and Galvin and a conjecture of Kahn and Park. Special cases include sharp asymptotics for the number of independent sets and the number of proper q-colourings of Z_m^n (so in particular, the discrete hypercube). For the proof we develop a `Cluster Expansion Method', which we expect to have further applications, by combining machinery from statistical physics, entropy and graph containers. This is joint work with Peter Keevash.
 

 
  • Combinatorial Theory Seminar
15 October 2019
14:00
Kitty Meeks
Abstract

Decision problems – those in which the goal is to return an answer of “YES" or “NO" – are at the heart of the theory of computational complexity, and remain the most studied problems in the theoretical algorithms community. However, in many real-world applications it is not enough just to decide whether the problem under consideration admits a solution: we often want to find all solutions, or at least count (either exactly or approximately) their  total number. It is clear that finding or counting all solutions is at least as computationally difficult as deciding whether there exists a single solution, and  indeed in many cases it is strictly harder (assuming P is not equal NP) even to count approximately the number of solutions than it is to decide whether there exists at least one.


In this talk I will discuss a restricted family of problems, in which we are interested in solutions of a given size: for example, solutions could be copies of a specific k-vertex graph H in a large host graph G, or more generally k-vertex subgraphs of G that have some specified property (e.g. k-vertex subgraphs that are connected). In this setting, although exact counting is strictly harder than decision (assuming standard assumptions in parameterised complexity), the methods typically used to separate approximate counting from decision break down. Indeed, I will demonstrate a method that, subject to certain additional assumptions, allows us to transform an efficient decision algorithm for a problem of this form into an approximate counting algorithm with essentially the same running time.

This is joint work with John Lapinskas (Bristol) and Holger Dell (ITU Copenhagen).

  • Combinatorial Theory Seminar
18 June 2019
14:30
Anita Liebenau

Further Information: 

How many d-regular graphs are there on n vertices? What is the probability that G(n,p) has a specific given degree sequence? 

Asymptotic formulae for the first question are known when d=o(\sqrt(n)) and when d= \Omega(n). More generally, asymptotic formulae are known for 
the number of graphs with a given degree sequence, for a range of degree sequences that is wide enough to deduce asymptotic formulae for the second 
question for p =o(1/o(\sqrt(n))) and p = Theta(1).  

McKay and Wormald showed that the formulae for the sparse case and the 
dense case can be cast into a common form, and then conjectured in 1990 and 1997 that the same formulae should hold for the gap range. A particular consequence of both conjectures is that the degree sequence of the random graph G(n,p) can be approximated by a sequence of n independent 
binomial variables Bin(n − 1, p'). 

In 2017, Nick Wormald and I proved both conjectures. In this talk I will describe the problem and survey some of the earlier methods to showcase the differences to our new methods. I shall also report on enumeration results of other discrete structures, such as bipartite graphs and hypergraphs, that are obtained by adjusting our methods to those settings. 

  • Combinatorial Theory Seminar
4 June 2019
14:30
Annika Heckel

Further Information: 

A classic result of Shamir and Spencer states that for any function $p=p(n)$, the chromatic number of $G(n,p)$ is whp concentrated on a sequence of intervals of length about $\sqrt{n}$. For $p<n^{-\frac{1}{2} -\epsilon}$, much more is known: here, the chromatic number is concentrated on two consecutive values.

Until now, there have been no non-trivial cases where $\chi(G(n,p))$ is known not to be extremely narrowly concentrated. In 2004, Bollob\'as asked for any such examples, particularly in the case $p=\frac{1}{2}$, in a paper in the problem section of CPC. 

In this talk, we show that the chromatic number of $G(n, 1/2)$ is not whp concentrated on $n^{\frac{1}{4}-\epsilon}$ values

  • Combinatorial Theory Seminar

Pages