Best Response Dynamics on Random Graphs
We consider an evolving system of agents whose underlying topology of interactions is determined by a binomial random graph G(n,p). In each round, each agent will choose a binary strategy which will then be executed against each of its neighbours in a symmetric 2-players game. We consider the best response dynamics on this system: each agent synchronously updates their strategy by selecting that which maximises their total payoff, given their neighboursâ current choices. We outline two results that bound the time needed for all agents to reach a consensus.
Based on joint work with Calina Durbac and Nikolaos Fountoulakis. âââââââââââââââââââââââââââââ Meeting ID: 949 1136 5006 Passcode: 342983
- Part of Combinatorics and Probability seminar
- Speaker: Jordan Chellig (University of Birmingham)
- Thursday 01 October 2020, 16:00-17:00
- https://bham-ac-uk.zoom.us/j/94911365006?pwd=RGNmWlYvY2NPUmFpKzFoRUpvY1lEUT09.
On Hamilton cycles in highly symmetric graphs
The question whether a graph has a Hamilton cycle or not is one of the oldest and most fundamental graph-theoretic problems, and one of the prototypical NP-complete problems. In this talk I will survey some recent results on Hamilton cycles in different families of highly symmetric graphs. The starting point is our proof of the middle levels conjecture, and various other long-standing problems that we settled subsequently, including the Hamiltonicity of bipartite Kneser, of sparse Kneser graphs, and cycles through any range of consecutive levels of the hypercube. I will highlight how these constructions and problems link several well-known concepts in combinatorics and algorithms. _
Meeting ID: 872 9816 4024 Passcode: 604350
- Part of Combinatorics and Probability seminar
- Speaker: Torsten MĂŒtze (University of Warwick)
- Thursday 08 October 2020, 16:00-17:00
- https://bham-ac-uk.zoom.us/j/87298164024?pwd=WWJBM3pKWWdGU1lucEJZZk8rbjBXQT09.
Ryser's conjecture and more
A Latin square of order $n$ is an $n \times n$ array filled with $n$ symbols such that each symbol appears only once in every row or column and a transversal is a collection of cells which do not share the same row, column or symbol. The study of Latin squares goes back more than 200 years to the work of Euler. One of the most famous open problems in this area is a conjecture of Ryser, Brualdi and Stein from 60s which says that every Latin square of order $n\times n$ contains a transversal of order $n-1$. A closely related problem is 40 year old conjecture of Brouwer that every Steiner triple system of order $n$ contains a matching of size $(n-4)/3$. The third problem weâd like to mention asks how many distinct symbols in Latin arrays suffice to guarantee a full transversal? In this talk we discuss a novel approach to attack these problems. Joint work with Peter Keevash, Alexey Pokrovskiy and Benny Sudakov.
Meeting ID: 830 2268 5017 Passcode: 101833
- Part of Combinatorics and Probability seminar
- Speaker: Liana Yepremyan (University of Illinois at Chicago)
- Thursday 15 October 2020, 16:00-17:00
- https://bham-ac-uk.zoom.us/j/83022685017?pwd=L1RQclI2dmIvL2RXeUNCblpuanlBUT09.
Roots of random polynomials near the unit circle
It is a well-known (but perhaps surprising) fact that a polynomial with independent random coefficients has most of its roots very close to the unit circle. Using a probabilistic and combinatorial perspective, we understand the behavior of roots of random polynomials exceptionally close to the unit circle and prove several limit theorems; these results resolve several conjectures of Shepp and Vanderbei. We will also discuss how our techniques provide a heuristic, combinatorial explanation for why random polynomials tend to have most roots near the unit circle. Based on joint work with Julian Sahasrabudhe.
_
https://bham-ac-uk.zoom.us/j/83022685017?pwd=L1RQclI2dmIvL2RXeUNCblpuanlBUT09
Meeting ID: 830 2268 5017 Passcode: 101833
- Part of Combinatorics and Probability seminar
- Speaker: Marcus Michelen (University of Illinois at Chicago)
- Thursday 22 October 2020, 16:00-17:00
- https://bham-ac-uk.zoom.us/j/83022685017?pwd=L1RQclI2dmIvL2RXeUNCblpuanlBUT09.
Algorithmic Aspects of The LovĂĄsz Local Lemma
The Lovåsz Local Lemma (LLL) is a powerful probabilistic tool for establishing the existence of objects that satisfy certain properties. The breakthrough of Moser and Tardos that made the LLL algorithmic (for which they received the Gödel Prize this year), along with follow-up works revealed that the LLL has intimate connections with a rich class of stochastic local search algorithms. In this talk, I will survey this line of work through the perspective of recent unifying results. __
https://bham-ac-uk.zoom.us/j/83022685017?pwd=L1RQclI2dmIvL2RXeUNCblpuanlBUT09
Meeting ID: 830 2268 5017 Passcode: 101833
- Part of Combinatorics and Probability seminar
- Speaker: Fotis Iliopoulos (Institute for Advanced Study)
- Thursday 29 October 2020, 16:00-17:00
- https://bham-ac-uk.zoom.us/j/83022685017?pwd=L1RQclI2dmIvL2RXeUNCblpuanlBUT09.
Combinatorial discrepancy and harmonic analysis
Given a collection of finite subsets A_1,..., A_n of {1,... ,n }, a basic problem in combinatorial discrepancy theory is to find a colouring f of {1,...,n} with {+1,-1} so that the largest sum of f over x in A_i is as small as possible. I will discuss how the sort of combinatorial reasoning used to think about problems in combinatorial discrepancy can help us solve an old problem in the field of harmonic analysis. This talk is based on joint work with Balister, BollobĂĄs, Morris and Tiba.
__
https://bham-ac-uk.zoom.us/j/83022685017?pwd=L1RQclI2dmIvL2RXeUNCblpuanlBUT09
Meeting ID: 830 2268 5017 Passcode: 101833
- Part of Combinatorics and Probability seminar
- Speaker: Julian Sahasrabudhe (University of Cambridge)
- Thursday 05 November 2020, 16:00-17:00
- https://bham-ac-uk.zoom.us/j/83022685017?pwd=L1RQclI2dmIvL2RXeUNCblpuanlBUT09.
The threshold for the square of a Hamilton cycle
We will talk about a recent result of Jeff Kahn, Bhargav Narayanan, and myself stating that the threshold for the random graph G(n,p) to contain the square of a Hamilton cycle is 1/sqrt n, resolving a conjecture of KĂŒhn and Osthus from 2012. The proof idea is motivated by the recent work of Frankston and the three aforementioned authors on a conjecture of Talagrandââa fractional version of Kahn-Kalai expectation threshold conjecture.â
__
Meeting ID: 830 2268 5017 Passcode: 101833
- Part of Combinatorics and Probability seminar
- Speaker: Jinyoung Park (Institute for Advanced Study)
- Thursday 12 November 2020, 16:00-17:00
- https://bham-ac-uk.zoom.us/j/83022685017?pwd=L1RQclI2dmIvL2RXeUNCblpuanlBUT09.
Extremal stationary values for random digraphs
In this talk, we will discuss the minimum positive value of the stationary distribution of a random walk on a directed random graph with given degrees. While for undirected graphs the stationary distribution is simply determined by the degrees, the graph geometry plays a major role in the directed case. Understanding typical stationary values is key to determining the mixing time of the walk, as shown by Bordenave, Caputo, and Salez. However, typical results provide no information on the minimum value, which is important for many applications. Recently, Caputo and Quattropani showed that the stationary distribution exhibits logarithmic fluctuations provided that the minimum degree is at least 2. In this talk, we show that dropping the minimum degree condition may yield polynomially smaller stationary values of the form n^{-(1+C+o(1))}, for a constant C determined by the degree distribution. In particular, C is the combination of two factors: (1) the contribution of atypically thin in-neighborhoods, controlled by subcritical branching processes; and (2) the contribution of atypically âlightâ trajectories, controlled by large deviation rate functions. As a by-product of our proof, we also determine the hitting and cover time in random digraphs. This is joint work with Xing Shi Cai. __
Meeting ID: 830 2268 5017 Passcode: 101833
- Part of Combinatorics and Probability seminar
- Speaker: Guillem Perarnau (Polytechnic University of Catalonia)
- Thursday 19 November 2020, 16:00-17:00
- https://bham-ac-uk.zoom.us/j/83022685017?pwd=L1RQclI2dmIvL2RXeUNCblpuanlBUT09.
Large monochromatic tight cycles in 2-edge-coloured complete 4-uniform hypergraphs
A 4 -uniform tight cycle is a 4-uniform hypergraph with a cyclic ordering of its vertices such that its edges are precisely the sets of 4 consecutive vertices in the ordering. Given a 2-edge-coloured complete 4-uniform hypergraph, we consider the following two questions. 1) What is the length of the longest monochromatic tight cycle? In other words, what is the Ramsey number for tight cycles? 2) How many tight cycles are needed to partition the vertex set? This is a generalisation of Lehelâs conjecture for graphs. In this talk, I will highlight a common approach, which yields some asymptotic results for these two questions. The approach is based on Ćuczakâs connected matching method together with a novel auxiliary graph, which I call the blueprint. This is joint work with Allan Lo.
- Part of Combinatorics and Probability seminar
- Speaker: Vincent Pfenninger (University of Birmingham)
- Thursday 26 November 2020, 16:00-17:00
- https://bham-ac-uk.zoom.us/j/83022685017?pwd=L1RQclI2dmIvL2RXeUNCblpuanlBUT09.
Counting solutions in the random k-SAT model
We give the first efficient algorithm to approximately count the number of solutions in the random k-SAT model when the density of the formula scales exponentially with k. The best previous counting algorithm was due to Montanari and Shah and was based on the correlation decay method, which works up to densities (1+o_k(1))2logk/k, the Gibbs uniqueness threshold for the model. Instead, our algorithm harnesses a recent technique by Moitra to work for random formulas. The main challenge in our setting is to account for the presence of high-degree variables whose marginal distributions are hard to control and which cause significant correlations within the formula.
This is joint work with Leslie Ann Goldberg, Heng Guo, and Kuan Yang.
- Part of Combinatorics and Probability seminar
- Speaker: Andreas Galanis (University of Oxford)
- Thursday 03 December 2020, 16:00-17:00
- Venue to be confirmed.
Even-hole-free graphs with bounded degree have bounded treewidth
The class of even-hole-free graphs (i.e. graphs that do not contain a chordless cycle on an even number of vertices) has been studied since the 1990âs, initially motivated by their structural similarity to perfect graphs. It is known for example that they can be decomposed by star cutsets and 2-joins into graphs that are line graphs of a tree plus at most two vertices, which has led to, for example, their polynomial time recognition. Nevertheless, the complexity of a number of classical computational problems remain open for this class, such as the coloring and stable set problems.
In this talk we show that even-hole-free graphs with bounded degree have bounded treewidth, resolving a conjecture of Aboulker, Adler, Kim, Sintiari and Trotignon. This implies that many algorithmic problems can be solved in polynomial time for this class. Furthermore, it shows that even-hole-freeness is testable in the bounded degree graph model of property testing.
Treewidth is a parameter that emerged out of the study of minor closed classes of graphs (i.e. classes closed under vertex and edge deletion, and edge contraction). It in some sense describes the global structure of a graph. Roughly, a graph has treewidth k if it can be decomposed by a sequence of noncrossing cutsets of size at most k into pieces of size at most k+1. The study of hereditary graph classes (i.e. those closed under vertex deletion only) reveals a different picture, where cutsets that are not necessarily bounded in size (such as star cutsets, 2-joins and their generalization) are required to decompose the graph into simpler pieces that are structured but not necessarily bounded in size. A number of such decomposition theorems are known for complex hereditary graph classes, including for even-hole-free graphs, perfect graphs and others. They do not describe the global structure in the sense that a tree decomposition does, since the cutsets guaranteed by these decomposition theorems are far from being noncrossing. In the case of even-hole-free graphs of bounded degree we show how these cutsets can be partitioned into a bounded number of well-behaved collections, which allows us to bound the treewidth of such graphs.
This is joint work with Tara Abrishami and Maria Chudnovsky.
- Part of Combinatorics and Probability seminar
- Speaker: Kristina VuĆĄkoviÄ (Leeds)
- Thursday 04 February 2021, 16:00-17:00
- https://bham-ac-uk.zoom.us/j/86238837160.
Finding Homeomorphs
Nati Linial asked the following basic problem in 2006: Given a k-dimensional simplicial complex S, how many facets can a k-complex on n vertices have if it contains no topological copy of S? This is a beautiful and natural question, but results in low dimensions apart (k <= 2), very little was previously known. In this talk, Iâll provide an answer in all dimensions and take the scenic route to the answer, surveying many natural problems about simplicial complexes along the way.
- Part of Combinatorics and Probability seminar
- Speaker: Bhargav Narayanan (Rutgers)
- Thursday 11 February 2021, 16:00-17:00
- https://bham-ac-uk.zoom.us/j/86238837160.
Title to be confirmed
Abstract not available
- Part of Combinatorics and Probability seminar
- Speaker: Dong Yeap Kang (Birmingham)
- Thursday 18 February 2021, 16:00-17:00
- https://bham-ac-uk.zoom.us/j/86238837160.
Trees in Tournaments
Given an n-vertex oriented tree T, what is the smallest size a tournament G must be, in order to guarantee G contains a copy of T? A strengthening of Sumnerâs conjecture poses that it is enough for G to have (n+k-1) vertices, where k is the number of leaves of T. Recently, Dross and Havet used a method of median orders to prove that this is true for arborescencesâi.e. trees with edges oriented outwards from a specified root vertex. We show that median orders can make further progress towards (n+k-1), by proving that there exists a constant C such that |G|=(n+Ck) is enough, as well as confirming a separate conjecture that |G|=(n+k-2) is enough, provided we allow n to grow large with k fixed. In this talk we shall discuss these results and further progress that could be made.
Joint work with Richard Montgomery
- Part of Combinatorics and Probability seminar
- Speaker: Alistair Benford (Birmingham)
- Thursday 25 February 2021, 16:00-17:00
- https://bham-ac-uk.zoom.us/j/86238837160.
Hypergraphs with many extremal configurations (cancelled)
For every positive integer $t$ we construct a finite family of triple systems $M_t$, determine its Tur\â{a}n number, and show that there are $t$ extremal $M_t$-free configurations that are far from each other in edit-distance.
We also prove a strong stability theorem: every $M_t$-free triple system whose size is close to the maximum size is a subgraph of one of these $t$ extremal configurations after removing a small proportion of vertices.
This is joint work with Xizhi Liu and Dhruv Mubayi.
- Part of Combinatorics and Probability seminar
- Speaker: Christian Reiher (Hamburg)
- Thursday 04 March 2021, 16:00-17:00
- https://bham-ac-uk.zoom.us/j/86238837160.
Counting integer partitions with the method of maximum entropy
We give an asymptotic formula for the number of partitions of an integer n where the sums of the kth powers of the parts are also fixed, for some collection of values k. To obtain this result, we reframe the counting problem as an optimization problem, and find the probability distribution on the set of all integer partitions with maximum entropy among those that satisfy our restrictions in expectation (in essence, this is an application of Jaynesâ principle of maximum entropy). This approach leads to an approximate version of our formula as the solution to a relatively straightforward optimization problem over real-valued functions. To establish more precise asymptotics, we prove a local central limit theorem using an equidistribution result of Green and Tao.
A large portion of the talk will be devoted to outlining how our method can be used to re-derive a classical result of Hardy and Ramanujan, with an emphasis on the intuitions behind the method, and limited technical detail. This is joint work with Marcus Michelen and Will Perkins.
- Part of Combinatorics and Probability seminar
- Speaker: Gwen McKinley (UCSD)
- Thursday 11 March 2021, 16:00-17:00
- https://bham-ac-uk.zoom.us/j/86238837160.
A proof of the ErdoÌsâFaberâLovaÌsz conjecture
The ErdoÌsâFaberâLovaÌsz conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. In this talk, I will sketch a proof of this conjecture for every large n.
Joint work with Dongyeap Kang, Tom Kelly, Daniela Kuhn and Deryk Osthus.
- Part of Combinatorics and Probability seminar
- Speaker: Abhishek Methuku (Birmingham)
- Thursday 18 March 2021, 16:00-17:00
- https://bham-ac-uk.zoom.us/j/86238837160.
Hypergraphs with many extremal configurations
For every positive integer $t$ we construct a finite family of triple systems $M_t$, determine its Tur\â{a}n number, and show that there are $t$ extremal $M_t$-free configurations that are far from each other in edit-distance.
We also prove a strong stability theorem: every $M_t$-free triple system whose size is close to the maximum size is a subgraph of one of these $t$ extremal configurations after removing a small proportion of vertices.
This is joint work with Xizhi Liu and Dhruv Mubayi.
- Part of Combinatorics and Probability seminar
- Speaker: Christian Reiher (Hamburg)
- Thursday 22 April 2021, 16:00-17:00
- https://bham-ac-uk.zoom.us/j/86238837160.
On embedding graphs in surfaces
I will start explaining the two main problems concerning embeddings of graphs in surfaces. Then I will explain Whitneyâs characterisation of planarity in terms of abstract dual graphs from the 1930s. Can abstract duals also be used to construct embeddings in surfaces beyond the plane?
- Part of Combinatorics and Probability seminar
- Speaker: Johannes Carmesin (Birmingham)
- Thursday 29 April 2021, 16:00-17:00
- https://bham-ac-uk.zoom.us/j/86238837160.
Counting complexity and quantum information theory
In computational counting problems, the goal of a computation is to determine the number of solutions to some problem specified by a number of constraint functions. More generally, each constraint function may be weighted, and the goal is to determine the total weight of all solutions. The holant framework formalises a broad family of such counting problems in order to analyse their computational complexity. In this talk, I show how some of the mathematical properties of constraint functions that determine the complexity of a holant problem are equivalent to properties of quantum states that are of independent interest in quantum information theory. I then use results from quantum theory to classify the (classical, i.e. non-quantum) complexity of several families of holant problems.
- Part of Combinatorics and Probability seminar
- Speaker: Miriam Backens (Birmingham)
- Thursday 06 May 2021, 16:00-17:00
- https://bham-ac-uk.zoom.us/j/86238837160.
Previous seminars: Autumn 2006, Spring 2007, Autumn 2007, Spring 2008, Autumn 2008, Spring 2009, Autumn 2009, Spring 2010, 2010-2016, 2016/17, 2017/18, 2018/19, 2019/20, 2020/21, 2021/22, 2022/23