Seminars

Past Events and Seminars

2023

14/12: Rainbow Turán problems

Speaker: Andrzej Grzesik

Abstract: A typical Turán problem asks for the maximum number of edges in graphs that do not contain a given forbidden graph. In the rainbow variant of this problem, we consider many graphs on a common vertex set, thinking of each graph as edges in a separate color, and want to determine the smallest number of edges in each color that guarantees the existence of a rainbow copy of a given graph. In the talk we will survey known results on this topic, in particular present the asymptotically optimal solution for short paths, directed triangles and small directed stars for any number of colors. This is based on joint works with Sebastian Babiński, Dániel Gerbner, Cory Palmer and Magdalena Prorok.

7/12: Robust sublinear expanders

Speaker: Matija Bucic

Abstract: Expander graphs are perhaps one of the most widely useful classes of graphs ever considered. In this talk, we will focus on a fairly weak notion of expanders called sublinear expanders, first introduced by Komlós and Szemerédi around 30 years ago. They have found many remarkable applications ever since. In particular, we will focus on certain robustness conditions one may impose on sublinear expanders and some applications of this idea, which include: 

- recent progress on the classical Erdős-Gallai cycle decomposition conjecture,

- essentially tight answer to the classical Erdős unit distance problem for "most" real normed spaces and

- rainbow Turan problem for cycles, raised by Keevash, Mubayi, Sudakov and Verstraete, including an application of this result to additive number theory.

30/11: Connectivity threshold for the Square Graph

Speaker: Altar Ciceksiz, Umeå universitet

Abstract: Given a random graph G chosen from the Erdős-Rényi random graph on n vertices with edge probabilities p, we consider the percolation properties of the associated square graph S(G). The square graph is the graph with the vertices V(S(G)):={S=xyzt: xyzt is a 4 cycle in G}, and edges E(S(G)):={ST: the induced 4 cycles S and T share a diagonal}. In 2021, Falgas-Ravry, Behrstock, Hagen and Susse determined the critical probability for the threshold of a giant component emerging in the square graph, and in 2021 Susse conjectured that the threshold for the square graph S(G) being connected. We settle the conjecture of Susse. We will also briefly talk about the geometric group theory context and what it means to associate a group to a random graph. 

23/11: Sparsity, pebble games and posets

Speaker: Joannes Vermant, Umeå universitet

Abstract: There are various sparsity conditions which define matroids on graphs, hypergraphs or incidence geometries. Such conditions have applications in combinatorial geometry, as well as some classical interpretations in terms of disjoint spanning trees in graphs. An algorithm that recognises 2,3 sparsity, called the pebble game, was developed by Jackson and Hendrickson (1997). Later this was generalised to the k-plane matroid by Berg and Jordan (2003), to other parameters by Lee and Streinu (2008), to hypergraphs by Theran and Streinu (2009) and to general count matroids by Frank (2011). In ongoing work together with Signe Lundqvist, Tovohery Randrianarisoa and Klara Stokes, we consider pebble games on posets.

16/11: The Mubayi—Terry problem for locally sparse multigraphs

Speaker: Victor Falgas Ravry, Umeå universitet

Abstract: A multigraph is (s,q)-sparse if every s-set of vertices in G supports at most q edges, counting multiplicities. How large can the product of the edge multiplicities be in an (s,q)-sparse multigraph on n vertices?

This question was posed by Mubayi and Terry in 2016, with motivation coming from hypergraph container theory. It can also be seen as a natural attempt to generalise classical results from extremal graph theory to the setting of multigraphs with bounded edge multiplicities.  That one seeks to maximise a product rather than a sum results in some unusual features, such as extremal constructions with parts containing an asymptotically transcendental proportion of the vertices.

Despite some recent progress, the answer to Mubayi and Terry's question is still poorly understood for general (s,q). In this talk, I will give some background and motivation for the study of (s,q)-sparse multigraphs, before going over the (few) know results and (many) open problems in the area.

9/11: Geometries with trialities but no dualities

Speaker: Klara Stokes, Umeå universitet

Abstract: The notion of triality is more elusive than projective duality. It is a phenomenon appearing in a certain 6-dimensional hyperbolic quadric in 7-dimensional projective space, first discovered in the 19th century by Study when he investigated the parametrizations of the rigid motions of 3-dimensional Euclidean space. Nowadays the same triality phenomenon is best known as "an outer automorphism of groups of type D_4, coming from a graph automorphism of the diagram". Actually,  this diagram has the symmetric group on 3 elements as automorphism group, so the geometry not only has a triality, but a total of 2 trialities and 3 dualities. In this talk I will show how to get new incidence geometries from embeddings of graphs on surfaces with trialities but no dualities. I will also show how to use Suzuki groups to get an infinite family of flag-transitive incidence geometries with trialities but no dualities. The talk will be adapted to a general audience. 

2/11: On Linear Complexity of Finite Sequences: Coding Theory and Applications to Cryptography

Speaker: Tovohery Randrianarisoa, Umeå universitet

Abstract: We define two metrics on vector spaces over a finite field using the linear complexity of finite sequences. We then develop coding theory notions for these metrics and study their properties. We give a Singleton-like bound as well as constructions of subspaces achieving this bound. We also provide an asymptotic Gilbert-Varshamov-like bound for random subspaces. We show how to reduce the problem of finding codewords with a given Hamming weight into a problem of finding a vector of a given linear complexity. As a consequence, an application to a post-quantum digital signature scheme is presented.

Joint work with E. Persichetti.

27/10: Multi-colour competition with reinforcement

Speaker: Daniel Ahlberg, Stockholm University

Abstract: We study a system of interacting urns where balls of different colour/type compete for their survival and annihilate upon contact. We shall consider the finite setting, i.e. when the underlying graph is finite and connected. In this case it is known that coexistence is not possible between two types. However, for competition between three or more types, the possibility of coexistence depends on the underlying graph. We prove a conjecture stating that when the underlying graph is a cycle, then the competition between three or more types has a single survivor almost surely. As part of the proof, we give a detailed description of an auto-annihilative process on the cycle, which can be perceived as an expression of the geometry of a Möbius strip in a discrete setting. (Joint work with Carolina Fransson.)

19/10: A resolution of the Kohayakawa Kreuter conjecture for almost all pairs of graphs

Speaker: Robert Hancock, University of Oxford

Abstract: We study asymmetric Ramsey properties of the random graph G(n,p). For r ≥ 2 and a graph H, Rödl and Rucinski (1993-5) provided the asymptotic threshold for G(n,p) to have the following property: whenever we r-colour the edges of G(n,p) there exists a monochromatic copy of H as a subgraph. In 1997, Kohayakawa and Kreuter conjectured an asymmetric version of this result, where one replaces H with a set of graphs H_1,...,H_r and we seek the threshold for when every r-colouring contains a monochromatic copy of H_i in colour i for some i ∈ {1,...,r}.

The 1-statement of this conjecture was confirmed by Mousset, Nenadov and Samotij in 2020. We extend upon the many partial results for the 0-statement, by resolving it for almost all cases. We reduce the remaining cases to a deterministic colouring problem.

Our methods also extend to the hypergraph setting.

Joint work with Candida Bowtell (University of Warwick) and Joseph Hyde (University of Victoria).

12/10: Positive discrepancy, MaxCut and eigenvalues of graphs

Speaker: Eero Räty, Umeå university

Abstract:The positive discrepancy of a graph G of edge density p is defined as the maximum of e(U) - p|U|(|U|-1)/2, where the maximum is taken over subsets of vertices in G. In 1993 Alon proved that if G is d-regular graph on n vertices and d = O(n^(1/9)), then the positive discrepancy of G is at least c*d^(1/2)n for some constant c.

We extend this result by proving lower bounds for the positive discrepancy with average degree d when d < (1/2 - \epsilon)*n. We prove that, up to a logarithmic factor, the same lower bound remains true when d < n^(2/3), while in the ranges n^(2/3) < d < n^(4/5) and n^(4/5) < d < (1/2 - \epsilon)*n we prove that the positive discrepancy is at least n^2/d and d^(1/4)n respectively.

Our proofs are based on semidefinite programming and linear algebraic techniques. Our results are tight when d < n^(3/4), thus demonstrating a change in the behaviour around d = n^(2/3) when a random graph no longer minimises the positive discrepancy. As a by-product, we also present lower bounds for the second largest eigenvalue of a d-regular graph when d < (1/2 - c)n, thus extending the celebrated Alon-Boppana theorem.

This is joint work with Benjamin Sudakov and István Tomon

5/10: Perfect tilings in hypergraphs

Speaker: Richard Lang, University of Hamburg

Abstract: A classic result of Dirac provides optimal minimum degree conditions for the existence of a perfect matching. Over the past decades, a comprehensive literature has evolved around generalisations of Dirac's theorem, yet many questions remain widely open.

In this talk, I will introduce the topic and then discuss a general framework to approach this type of problems.

14/9: Hypergraphs with arbitrarily small codegree Turán density

Speaker: Simón Piga, University of Birmingham

Abstract:Let $k\geq 3$. Given a $k$-uniform hypergraph $H$, the minimum codegree $\delta(H)$ is the largest $d\in\mathbb N$ such that every $(k-1)$-set of $V(H)$ is contained in at least $d$ edges. Given a $k$-uniform hypergraph $F$, the codegree Turán density $\gamma(F)$ of $F$ is the smallest $\gamma \in [0,1]$ such that every $k$-uniform hypergraph on $n$ vertices with $\delta(H)\geq (\gamma + o(1))n$ contains a copy of $F$. As in other variants of the hypergraph Turán problem, determining the codegree Turán density of a hypergraph is in general notoriously difficult and only few results are known.

We show that for every~$\eps>0$, there is a $k$-uniform hypergraph $F$ with $0<\gamma(F)<\eps$. This is in contrast to the classical Turán density, which cannot take any value in the interval $(0,k!/k^k)$ due to a fundamental result by Erd\H os.

24/8: Coordinating shipments from multiple suppliers

Speaker: Marcel Turkensteen, University of Aarhus

Abstract: Companies often order products from multiple suppliers. Combining these orders from different suppliers into joint shipments can have environmental and economic benefits.

Based on a case company, we formulate the problem of determining in which periods orders for multiple products should be placed to minimize the sum of the order and inventory costs. However, we limit the number of periods in which shipment, and vary the number of periods to measure its impact.

We call this problem the Bi-Objective Lot Sizing Problem with Shipment Minimization (BLSPSM). This problem combines an overarching problem, namely the determination of shipment periods, with subproblems for each product, namely the determination of order periods and order quantities.

We introduce dynamic programming heuristics for the BLSPSM, which utilize the bi-level nature of the problem, and which we call bi-level dynamic programming. We show that these heuristics outperform existing methods for a special case of our problem (the Coordinated Uncapacitated Lot Sizing Problem) and finds efficient frontiers very close to the best ones for all instances in our test.

8/6: Interesting rank 2 geometries coming from a classical construction by Tits

Speaker: Philippe Tranchida, Université Llibre de Bruxelles

Abstract: We introduce the notion of moving absolute geometry of a geometry with triality and show that certain cases the moving absolute geometry of the classical 7-dimensional quadric also gives interesting flag-transitive geometries. We also classify the classical absolute geometries for geometries with trialities but no dualities coming from maps (graphs embeddings on surfaces) of Class III with automorphism group L_2(q_3), where q is a power of a prime. This is joint work with Dimitri Leemans and Klara Stokes. 

7/6: Modelling the Motions of Realisations of Incidence Geometries

Speaker: Joannes Vermant, Umeå universitet

Abstract: In structural rigidity, one studies frameworks of bars and joints in Euclidean space. Such a framework is an articulated structure consisting of rigid bars, joined together at joints around which the bars may rotate. I will present a model of articulated motions of realisations of incidence geometries that uses the terminology of graph of groups, and describe the motions of such a framework using group theory. Our approach allows to model a variety of situations, such as parallel redrawings, scenes, polytopes, realisations of graphs on surfaces, and even unique colourability of graphs. We also provide a lower bound on the dimension of the infinitesimal motions of such a framework in the special case when the underlying group is a Lie group. This is joint work with Klara Stokes. 

25/5: Presentation about a PostDoc research

Speaker: Denys Shcherbak, Umeå universitet

Abstract: We would like to invite to a short presentation about the progress of a PostDoc research, which is belong to Optimal Search Problem.

There are several classical algorithms in that area, such as simplex method, ellipsoid method, interior point method etc. All of them have their own advantages  and disadvantages. At the same time, they have one thing in common, namely, to start the search they require an initial feasible point. There is no special  recommendations on how to find this point, and usually, these methods yhemselves are used to find the point. In other words, first, an optimum method is used to find an initial feasible point, and then optimum method searches for optimal value.

We want to demonstrate a method which works in reverse order, namely, it searches a feasible point and also can find an optimum solution. The method is based on geometrical properties of n-dimensional space and can be used on any type of linear constrains (>, =, ≥). Moreover it can be used when the feasible region is non-full-dimensional.

11/5: Extremal independent set reconfiguration

Speaker: Nicolas Bousquet, CNRS Lyon

Abstract: Two independent sets A,B of size k of a graph G are said to be adjacent if their symmetric difference is reduced to two vertices (i.e. |A \ B|=|B \ A|=1).  Consider the graph R_k(G) whose vertices are k-independent sets and where two sets A,B are adjacent with the notion of adjacency defined above. One can then wonder: given two k-independent sets, are they in the same connected component of R_k(G) ? How many steps are needed to find a transformation? Can we efficiently find a transformation? All these problems, called reconfiguration problems, have attracted a lot of attention recently.

In the first part of the talk, we will briefly survey some important results and open problems on the topic. In the second part we will focus on "extremal reconfiguration" which consists in studying the following problem: what is the largest possible diameter of a connected component of R_k(G) for a given k and a given graph size n ? We provide some general upper and lower bounds.
In the particular case of k=3, we prove that this diameter can be almost quadratic (in n) but cannot be quadratic. To do so, we exhibit some relations between this problem and the so-called (6, 3)-theorem of Ruzsa-Szemerédi.

4/5: The Minimum Degree Removal Lemma Thresholds

Speaker: Zhihan Jin, ETH Zürich

Abstract: The graph removal lemma is a fundamental result in extremal graph theory which says that for every fixed graph H and ε>0, if an n-vertex graph G contains εn^2 edge-disjoint copies of H then G contains δn^{v(H)} copies of H for some δ=δ(ε,H)>0. The current proofs of the removal lemma give only very weak bounds on δ(ε,H), and it is also known that δ(ε,H) is not polynomial in ε unless H is bipartite. Recently, Fox and Wigderson initiated the study of minimum degree conditions guaranteeing that δ(ε,H) depends polynomially or linearly on ε. In this talk, we answer several questions of Fox and Wigderson on this topic. In particular, we provide the polynomial removal lemma threshold for odd cycles and give the full characterization of the linear removal lemma threshold for 3-chromatic graphs.

27/4: Turán problems for graphs from geometric shapes

Speaker: Hong Liu, Institute for Basic Science, Daejeon, South Korea

Abstract: While Turán type problems are the most studied topic in extremal combinatorics, some of the most basic bipartite degenerate Turán problems remain elusive. In this talk, I will discuss some recent progress on this topic and new results on bipartite graphs arising from geometric shapes and periodic tilings commonly found in nature, including even prisms, planar hexagonal tilings and quadrangulations of the plane, the cylinder and the torus.

This is joint work with Jun Gao, Oliver Janzer, and Zixiang Xu.

20/4: Unavoidable structures in infinite tournaments

Speaker: Alistair Benford, University of Birmingham

Abstract: Suppose T is a countably infinite tree. By Ramsey's theorem, every 2-edge-colouring of a complete graph on the natural numbers contains a monochromatic copy of T. In fact, recent work of Corsten, DeBiasio, and McKenney shows something even stronger: you can always guarantee a monochromatic copy of T with upper density at least 1/2. This can be viewed as a infinite analogue of a conjecture of Burr and Erdős, which asserts that if T is an n-vertex tree, then every 2-colouring of K_{2n-2} contains a monochromatic copy of T.

If T is an n-vertex oriented tree, then Sumner's conjecture asserts that every (2n-2)-vertex tournament contains a copy of T. It is then natural to wonder whether a similar infinite analogue exists in the oriented setting. Unfortunately, it is no longer true that every countably infinite oriented tree has a copy in every infinite tournament; however, for those that do, something far stronger can be established: such trees have a spanning copy in every infinite tournament.

In this talk we discuss this result, as well as further generalisations of Sumner's conjecture to infinite tournaments. This is joint work with Louis DeBiasio and Paul Larson.

6/4: A general approach to transversal versions of Dirac-type theorems

Speaker: Alp Müyesser, University College London

Abstract: Given a disjoint union of hypergraphs H_1,...,H_m on the same vertex set, an m-edge hypergraph F is a transversal if each of its edges comes from a distinct hypergraph H_i. How large does the minimum degree of each H_i need to be so that we can always find a F-transversal?

Each H_i in the collection could be identical, hence the minimum degree of each H_i needs to be large enough to be able to find a copy of F in H_i. Since its general introduction by Joos and Kim, a growing body of work has shown that in many cases, this lower bound is tight.

In this paper, we give a unified approach to this problem by providing a widely applicable sufficient condition for this lower bound to be asymptotically tight. This is general enough to recover many previous results in the area and obtain novel transversal variants of several classical Dirac-type results for (powers of) Hamilton cycles.

30/3: Maker-Breaker games on random boards

Speaker: Miloš Stojaković, University of Novi Sad

Abstract: In Maker-Breaker games played on edge sets of graphs, two players, Maker and Breaker, alternately claim unclaimed edges of a given graph until all of its edges are claimed. Maker wins the game if he claims all edges of one representative of a prescribed graph-theoretic structure (e.g. a Hamiltonian cycle, or a fixed graph H). Breaker wins otherwise.

We take a closer look at various Maker-Breaker games played on the edge sets of random graphs

23/3: Positive co-degree density of r-graphs

Speaker: Anastasia Halfpap, University of Montana

Abstract: In an r-uniform hypergraph H (which we will often call an r-graph for short), the co-degree of a set S of r-1 vertices is simply the number of hyperedges of H which contain S. The minimum co-degree of H is the minimum co-degree over all (r-1)-sets S, while the minimum positive co-degree of H is the largest integer k such that if an (r-1)-set S is contained in some hyperedge of H, then S is contained in at least k hyperedges of H.

Co-degree in r-graphs can be seen as a natural generalization of degree in 2-graphs, and several measures of extremality using co-degree have been considered. The best known of these is the co-degree Turán number coex(n,F), the largest possible minimum co-degree in an n-vertex, F-free r-graph. In this talk, inspired by the study of minimum co-degree problems, we shall introduce the positive co-degree Turán number, the largest possible minimum positive co-degree in an n-vertex, F-free r-graph. Our primary goals will be to motivate consideration of minimum positive co-degree problems and to give some general results on the (sometimes surprising) behavior of positive co-degree Turán numbers. We also highlight a number of open directions in this area.

This talk represents joint work with Cory Palmer and Nathan Lemons.

16/3: On the q-analogue of codes, matroids, simplicial complexes and their relations

Speaker: Tovohery Randrianarisoa, Umeå universitet

Abstract: For a code with the Hamming metric one can associate a matroid using its parity check matrix. The independent elements of this matroid form a simplicial complex. Simplicial complexes associated to a q-matroid were shown to be shellable and this property helps to relate some properties of the simplicial complex to the codes. Indeed it was shown that there is a relation between Betti Numbers associated to the simplicial complex and the generalized weights of the linear code.

In the first part of this talk, we will give a brief review of the relations between these objects. A very interesting question is to find whether similar relations exist when we replace the Hamming metric with the rank metric. As a partial answer to this question, a q-analogue of some of the previous results are presented in the second part of the talk.

2/3: Random perfect matchings in regular graphs

Speaker: Felix Joos, Universität Heidelberg

Abstract: The number of derangements (fixpoint-free permutations) is a topic studied for centuries. Observe that this number is equal to the number of perfect matchings in a complete balanced bipartite graph minus a perfect matching. I present several extensions of this result, thereby also answering two questions of Sprio and Surya.

23/2: Turán densities of tight cycles

Speaker: Shoham Letzter, University College London

Abstract: The Turán density of an r-uniform hypergraph H is the limit of the maximum density of an n-vertex r-uniform hypergraph not containing a copy of H, as n tends to infinity.        

Denote by Ct the 3-uniform tight cycle on t vertices. Mubayi and Rödl (2002) gave an `iterated blow-up' construction showing that the Turán density of C5 is at least 2\sqrt{3}-3, and this bound is conjectured to be tight. Their construction also does not contain any Ct for larger t not divisible by 3, which suggests that it might be an extremal construction for these hypergraphs as well. We show that, for large t not divisible by 3, the Turán density of Ct is, indeed, 2\sqrt{3}-3.

This is joint work with Nina Kamčev and Alexey Pokrovskiy.

16/2: Expander graphs are globally synchronising

Speaker: Victor Souza, University of Cambridge

Abstract: The Kuramoto model is a prototypical model used for rigorous mathematical analysis in the field of synchronisation and nonlinear dynamics.  A realisation of this model consists of a collection of identical oscillators with interactions given by a network, which we identify respectively with vertices and edges of a graph.

We show that a graph with sufficient expansion must be globally synchronising, meaning that the Kuramoto model on such a graph will converge to the fully synchronised state with all the oscillators with same phase, for every initial state up to a set of measure zero.

In particular, we show that for p ≥ (1 + epsilon)(log n)/n, the Kuramoto model on the Erdős--Rényi graph G(n,p) is globally synchronising with high probability, settling a conjecture of Ling, Xu and Bandeira. We also show the global synchrony of any d-regular Ramanujan graph with d ≥ 600.

Joint work with P. Abdalla, A. Bandeira, M. Kassabov, S. Strogatz and A. Townsend.

9/2: Turán numbers and tournament switching

Speaker: Karen Gunderson, University of Manitoba

Abstract: The Turán number for a fixed r-uniform hypergraph H is the maximum number of hyperedges in any r-uniform hypergraph on n vertices containing no copy of H.  I will discuss some exact Turán numbers that are obtained from a `switching operation' on tournaments.  Two tournaments on the same vertex set are switching equivalent if one can be obtained from the other by interchanging all edges between two disjoint sets that partition the vertices.  In some cases, infinite classes of extremal hypergraphs can be constructed by taking as hyperedges all sub-tournaments in a fixed switching equivalence class.  The target equivalence class can either be defined using some special classes of tournaments with connections to design theory or by computer search.  I will discuss some uniqueness results for the extremal results arising from algebraically-defined tournaments, and some possible avenues for further research directions. 

Based on joint work with Jason Semeraro.

2/2: Twin-width IV and V: ordered structures, modular counting and matrix multiplication

Speaker: Ugo Giocanti, ENS Lyon

Abstract: Twin-width is a graph parameter recently discovered by Bonnet, Kim, Thomassé and Watrigant that aims at generalizing and unifying many previous notions from parameterized complexity. The original article introducing twin-width was the starting point of a series of papers setting the basis of the theory of twin-width.

In this presentation, I will first give you a brief introduction to twin-width, and state the main results and questions. Then I will focus on ordered graphs, (i.e. graphs with a total order on their vertices) and show you that in this case there are many different ways to characterize twin-width boundedness, going from enumerative combinatorics to logics. In particular, from these characterizations we will see that there exists an FPT-algorithm to approximate the twin-width of ordered graphs, which is still not known to exist in the general case. In the remaining time, as an example of application I will explain you how to derive an efficient algorithm to compute in time Oq,t(n2 log(n)) the product of two matrices of twin-width t over the finite field Fq.     

Joint work with Edouard Bonnet, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé and Szymon Toruńczyk.

26/1: Odd distances in colourings of the plane

Speaker: James Davies, Cambridge

Abstract: We prove that every finite colouring of the plane contains a monochromatic pair of points at an odd integral distance from each other.

2022

19/12 Is it easier to count communities than find them?

Speaker: Fiona Skerman, Uppsala Universitet

Abstract: Random graph models with community structure have been extensively studied. For both the problems of detecting and recovering community structure, an interesting landscape of statistical and computational phase transitions has emerged. A natural unanswered question is: might it be possible to infer properties of the community structure (for instance, the number and sizes of communities) even in situations where actually finding those communities is believed to be computationally hard?

We show the answer is no. In particular, we consider certain hypothesis testing problems between models with different community structures, and we show in the low-degree polynomial framework that testing between two options is as hard as finding the communities. Our methods give the first computational lower bounds for testing between two different ”planted” distributions, whereas previous results have considered testing between a planted distribution and an i.i.d. ”null” distribution.

Joint work with Cynthia Rush, Alex Wein and Dana Yang.

8/12: Additive query games

Speaker: Anders Martinsson, ETH Zürich

Abstract: Combinatorial guessing games is a class of well-known problems studied for their information-theoretic, algorithmic as well as recreational aspects. In 1960, Shapiro and Fine asked how many weightings on an exact scale are needed to find all counterfeits out of n coins, assuming real and fake coins have distinct weights. In the following decade, multiple strategies were discovered to solve this problem optimally up to constant factors. Generalized Mastermind was proposed by Chvátal in 1983 as an extension of this problem. The problem of determining the optimal strategy for this game remained open until recently in joint work with Pascal Su. In this talk I will present new research on a framework to approach general information theoretic games over the integers. This allows us to derive simple self-sufficient proofs of optimal strategies to coin-weighing, Mastermind, and related query problems.

1/12: Approaches to Agrawal’s conjecture for triple arrays

Speaker: Tomas Nilson, Mittuniversitet

Abstract: A triple array is an array in which two 2-designs are merged together such that any row and column contain the same number of common symbols. We say that the array is adjusted orthogonal. Agrawal’s conjecture from 1966 says that (in the canonical case), there is a triple array if and only there is a symmetric 2-design. Given a triple array we can construct a symmetric 2-design, but in this talk we look at what is known about the desirable and still open direction.

We will give background and define objects used. The exposition will be elementary and special knowledge of the area will not be assumed.

25/11: Conflict-Free Colouring of Subsets

Speaker: Yelena Yudistky, Université Libre de Bruxelles

Abstract: A conflict-free colourings of t-subsets in hypergraphs is a colouring where one assigns colours to all subsets of vertices of cardinality t such that in any hyperedge of cardinality at least t there is a uniquely coloured t-subset. In the talk, I will present the following results. 

(i) For any fixed t, the t-subsets in any set P of n points in the plane can be coloured with O(t2  log2 n) colours so that any axis-parallel rectangle that contains at least t points of P also contains a uniquely coloured t-subset.

(ii) For a wide class of `well behaved' geometrically defined hypergraphs, there is a nearly tight upper bound on their t-subset conflict-free chromatic number.

This is a joint work with Bruno Jartoux, Chaya Keller and Shakhar Smorodinsky.  

17/11: An apology of computer constructions

Speaker: Vedran Krčadinac, University of Zagreb

Abstract: The computer has become an indispensable tool of mathematical discovery. While this claim hardly needs defending, results obtained by computer calculations are often considered less worthy than discoveries made by more traditional means. In this talk I will present some families of finite incidence geometries and theorems about these structures that were originally discovered by constructing small examples on a computer. I will also present a software package for the construction of combinatorial objects with prescribed automorphism groups that we are developing for the computer algebra system GAP.

11/11: Entropic counting of combinatorial 3-spheres

Speaker: Joel Danielsson, Lund university

27/10 Hypergraph Matchings Avoiding Forbidden Submatchings

Speaker: Michelle Delcourt, Toronto Metropolitan

Abstract: In 1973, Erdős conjectured the existence of high girth (n,3,2)-Steiner systems. Recently, Glock, Kühn, Lo, and Osthus and independently Bohman and Warnke proved the approximate version of Erdős' conjecture. Just this year, Kwan, Sah, Sawhney, and Simkin proved Erdős' conjecture. As for Steiner systems with more general parameters, Glock, Kühn, Lo, and Osthus conjectured the existence of high girth (n,q,r)-Steiner systems. We prove the approximate version of their conjecture.  This result follows from our general main results which concern finding perfect or almost perfect matchings in a hypergraph G avoiding a given set of submatchings (which we view as a hypergraph H where V(H)=E(G)). Our first main result is a common generalization of the classical theorems of Pippenger (for finding an almost perfect matching) and Ajtai, Komlós, Pintz, Spencer, and Szemerédi (for finding an independent set in girth five hypergraphs). More generally, we prove this for coloring and even list coloring, and also generalize this further to when H is a hypergraph with small codegrees (for which high girth designs is a specific instance). A number of applications in various areas follow from our main results including: Latin squares, high dimensional permutations, and rainbow matchings. 

This is joint work with Luke Postle.

20/10: On the number of points in general position in the plane, after Balogh and Solymosi

Speaker: Joannes Vermant, Umeå university

Abstract: In this seminar I will go through the proof of a theorem from a paper of Balogh and Solymosi, in which some progress on the following question is made. Suppose we are given a set S of n points such that no four points are collinear. How small can the largest subset S’ of S which is in general position be? Balogh and Solymosi proved the upper bound of n^(5/6 + o(1)). The proof is based on the hypergraph container method.

20/10 Geometric Dominating Sets, after Aichholzer, Eppstein and  Hainzl

Speaker: Signe Lundqvist, Umeå University

Abstract: A geometric dominating set in an n by n grid is a set of points such that every grid point lies on a line defined by two points in the set. The geometric dominating set problem asks for the smallest geometric dominating set in an n by n-grid. We can also consider the same problem with the additional requirement that no three of the points in the set lie on a line. A geometric dominating set such that no three points lie on a line is said to be in general position.

This talk will follow a paper by Aichholzer, Eppstein and  Hainzl, where the authors show both lower and upper bounds on the size of minimal geometric dominating sets in an n by n grid. Furthermore, the authors provide optimal geometric dominating sets in general position for grids of size up to 12 by 12. They also consider the same problem on the discrete torus, where they prove upper bounds on the size of geometric dominating sets.

13/10: Percolation in High-Dimensional Product Graphs

Speaker: Joshua Erde, TU Graz, Austria

Abstract: A classic result of Erdős and Rényi describes the phase transition that the component structure of the binomial random graph G(n,p) undergoes when p is around 1/n. Below this point, the graph typically contains only small components, of logarithmic order, whereas above this point many of these component coalesce to a unique `giant' component of linear order, and all other components are of logarithmic order. It has been observed that quantitatively similar phase transitions occur in many other percolation models, and, in particular, work of Ajtai, Komlós and Szemerédi and of Bollobás, Kohayakawa and Łuczak shows that such a phenomena occurs in the percolated hypercube. We consider this phase transition in percolation on graphs arising from the cartesian product of many graphs and show that, under some mild conditions on the factor graphs, this phenomena is universal.

Joint work with Sahar Diskin, Mihyun Kang and Michael Krivelevich

6/10: Asymptotic results on Betti numbers of edge ideals of graphs via critical graphs

Speaker: Milo Orlich, Aalto

Abstract: To any graph G one can associate its edge ideal. One of the most famous results in combinatorial commutative algebra, Hochster's formula, describes the Betti numbers of the edge ideal in terms of combinatorial information on the graph G. More explicitly, each specific Betti number is given in terms of the presence of certain induced subgraphs in G. The machinery of critical graphs, relatively recently introduced by Balogh and Butterfield, deals with characterizing asymptotically the structure of graphs based on their induced subgraphs. In a joint work with Alexander Engström, we apply these techniques to Betti numbers and regularity of edge ideals. We introduce parabolic Betti numbers, which constitute a non-trivial portion of the Betti table. Usually, the vanishing of a Betti number has little impact on the rest of the Betti table. I this talk I will describe our main results, which show that on the other hand the vanishing of a parabolic Betti number determines asymptotically the structure and regularity of the graphs with that Betti number equal to zero. 

15/9: Minimal hyperplane covers of finite spaces and applications

Speaker: István Tomon, Umeå university

Abstract: At least how many hyperplanes are needed to cover the finite space $\mathbb{F}_p^{n}$ if we require that the normal vectors of the hyperplanes span the whole space, and none of the hyperplanes is redundant? This question is related to a number of long-standing conjectures in linear algebra and group theory, such as the Alon-Jaeger-Tarsi conjecture on non-vanishing linear maps, the Additive Basis conjecture, and a conjecture of Pyber about irredundant coset covers. I will talk about some progress on this question, which in particular leads to a solution of the first conjecture in a strong form, makes substantial progress on the second conjecture, and fully resolves the third conjecture. This is based on a joint work with Janos Nagy and Peter Pal Pach.

2/6: Inequalities on Projected Volumes

Speaker: Eero Räty

Abstract: Given 2^n-1 real numbers x_A indexed by the non-empty subsets A \subset {1,..,n}, is it possible to construct a body T \subset R^n such that x_A=|T_A| where |T_A| is the |A|-dimensional volume of the projection of T onto the subspace spanned by the axes in A? As it is more convenient to take logarithms we denote by \psi_n the set of all vectors x for which there is a body T such that x_A=\log |T_A| for all A. Bollobás and Thomason showed that \psi_n is contained in the polyhedral cone defined by the class of `uniform cover inequalities'. Tan and Zeng conjectured that the convex hull of \psi_{n} is equal to the cone given by the uniform cover inequalities. 

We prove that this conjecture is nearly right: the closure of the convex hull of \psi_n is equal to the cone given by the uniform cover inequalities.

Joint work with Imre Leader and Zarko Randelovic. 

19/5: Skew Dyck paths

Speaker: Helmut Prodinger, Stellenbosch University and NITheCS, South Africa

Abstract: Bijective issues around Dyck paths, ordered trees, binary trees are reviewed, as non-specialists are probably not familiar with them. Then structures enumerated by the sequence 1,1,3,10,36,137, 543, 2219, … are discussed, among them skew Dyck paths, marked ordered trees, unary-binary trees, Hex-trees, 3-Motzkin trees. It is demonstrated how to derive relevant generating functions. Bijective issues are also discussed.

12/5: Rigidity, Combinatorics and Topology

Speaker: James (Jim) Cruickshank, NUI Galway, Ireland 

Abstract: In 1776 Leonard Euler made the following startling and somewhat provocative claim: “A closed spacial figure allows not changes, as long as it is not ripped apart.”

This statement has inspired much investigation in the intervening centuries with many connections to various mathematical, scientific and engineering disciplines. I will survey some of the highlights in this story, focusing on the case of polyhedra and related structures, and on topics of current interest to the geometric rigidity community. I will also report on recent joint work with Shinichi Tanigawa and Bill Jackson which resolves a conjecture of Bob Connelly and also extends the well known lower bound theorem for simplicial complexes.

5/5: Lattice models and special polynomials in algebraic combinatorics

Speaker: Henrik Gustafsson, Umeå University

Abstract: With this talk I would like to introduce myself and my research to the group in Discrete Mathematics which I have recently joined. In particular, I will give an introductory overview of my research on solvable lattice models. My original motivation for this research was to construct lattice models whose partition functions compute special functions in representation theory. However, as a by-product they also produce special functions (polynomials) of interest in algebraic combinatorics such as Schur polynomials, Hall-Littlewood polynomials and Macdonald polynomials, and this angle will be the starting-point of the talk.

The lattice models can then be used to give (alternative) proofs of a multitude of interesting combinatorial properties, including branching rules, Pieri- and Cauchy-type identities, and functional equations which I will explain diagrammatically.

Based on joint work with Ben Brubaker, Valentin Buciumas and Daniel Bump.

28/4: The density Turan problem for hypergraphs

Speaker: John Talbot, University College London

Abstract: Bondy et al. showed that any tripartite graph in which the density of edges between each pair of vertex classes is at least 0.618.. (the golden ratio) must contain a triangle, moreover this is sharp. The density Turán problem for a graph or hypergraph H asks for the corresponding quantity guaranteeing a copy of H in a subgraph of a  blow-up of H. Previous results due to Csikvári and Nagy gave bounds for graphs related to the largest root of the matching polynomial; while the only exact result for hypergraphs is for the complete r-graph of order r+1, due to Markström and Thomassen.

In joint work with Adam Sanitt we use an entropy compression argument to provide upper bounds for any hypergraph.

14/4: A transversal of simplicial polytopes

Speaker: Joseph Briggs, Auburn University

Abstract: Suppose you have a subset S of the vertices of a polytope which contains at least one vertex from every face. How large must S be? We believe, in the worst case, about half of the number of vertices of the polytope. But we don't really know why. We have found some situational evidence, but also some situational counter-evidence. This is based on joint work with Michael Dobbins and Seunghun Lee.

7/4: Minimal Ramsey graphs for cliques

Speaker: John Bamberg, University of Western Australia

Abstract: Burr, Erdős, and Lovász, in 1976, introduced the study of the smallest minimum degree s(r,k) of a graph G such that any r-colouring of the edges of G contains a monochromatic clique of size k, whereas no proper subgraph of G has this property. Burr, Erdős, and Lovász were able to show the rather surprising exact result, that if r=2, then s(2,k) = (k-1)^2. The behaviour of this function is still not so well understood for more than 2 colours. In 2016, Fox, Grinshpun, Liebenau, Person, and Szabó showed that for r>2, s(r,k) is at most 8(k-1)^6 r^3. The speaker, together with Anurag Bishnoi and Thomas Lesgourgues, have recently used finite geometry to improve this bound.

31/3: Chromatic structure of bipartite graphs

Speaker: Ross Kang, Radboud University

Abstract: Despite it being a seemingly redundant topic, the task of colouring bipartite graphs has a surprisingly rich tradition, connecting to different parts of combinatorics. I am referring here of course to stronger forms of graph colouring, especially those related to list colouring. I will give a quick overview of some highlights in this vein starting with the seminal Erdős-Rubin-Taylor paper, and spanning links to, inter alia, Property B, hypergraph Turán numbers, the coupon collector problem, the local lemma, and the permanent in random matrices. Central to these investigations is the stubborn Alon-Krivelevich conjecture, and a view towards chromatic structure in triangle-free graphs.

This talk touches on recent joint works with, variously, Alon, Cambie, Cames van Batenburg, and Davies.

24/3: The geometry of extremal Cayley graphs

Speaker: Valentina Pepe, La Sapienza, University of Rome

Abstract: The geometric aspect of extremal Cayley graphs is highlighted, providing a different proof of known results and giving a new perspective on how to tackle such problems. Some new results about extremal pseudorandom triangle free graphs are also presented.

17/3: Almost every matroid has a rank-3 wheel or rank-3 whirl as minor

Speaker: Jorn van der Pol, University of Waterloo

Abstract: Many conjectures – but few results – exist for the statistical properties of large "random" matroids. For example, the question of which matroids appear as a minor of almost every matroid has been settled for only a few matroids. I will present recent progress in this direction: almost every matroid has at least one of two particular matroids, the rank-3 wheel M(K_4) or the rank-3 whirl W^3, as a minor.

At the heart of the argument lies a counting version of the Ruzsa–Szemerédi (6,3)-theorem on 3-uniform hypergraphs, which is then generalised in several ways to obtain the main result.

This talk focuses on the hypergraph side of things; in particular, no prior knowledge about matroids is assumed.

4/3: Colourings of symmetric configurations of triples

Speaker: Grahame Erskine, Open University, UK

Abstract: A symmetric configuration $v_3$ is an incidence structure consisting of $v$ points and $v$ blocks; each block contains three points, each point is in three blocks and no pair of points appears in more than one block. There are two natural colouring problems associated with these objects: a weak colouring is a colouring of the points such that no block is monochromatic, and a strong colouring is a colouring such that no colour appears more than once in a block. In this talk I will explore the history of the weak colouring problem and the related idea of blocking sets in a configuration. I will describe the relationship between the weak and strong chromatic numbers, and mention a number of open problems.

This is joint work with Terry Griggs and Jozef Širáň.

17/2: Enumerating matroids, linear spaces and clique-decompositions

Speaker: Matthew Kwan, IST, Austria

Abstract: We show that the number of linear spaces on a set of n points and the number of rank-3 matroids on a ground set of size n are both of the form (cn+o(n))n^2/6, for an explicit constant c ≈ 0.162. This is the final piece of the puzzle for enumerating fixed-rank matroids at this level of accuracy: the numbers of rank-1 and rank-2 matroids on a ground set of size n have exact representations in terms of well-known combinatorial functions, and it was recently proved by van der Hofstad, Pendavingh and van der Pol that for constant r ≥ 4 there are (e1−rn+o(n))n^{r−1}/r! rank-r matroids on a ground set of size n. The proof comes down to counting clique-decompositions of the complete graph; to this end we introduce some new counting techniques, using quasirandomness instead of the so-called entropy method that is common in this area.

10/2: Random graphs and applications to Coxeter groups

Speaker: Jason Behrstock, CUNY

Abstract: Erdős and Rényi introduced a model for studying random graphs of a given density and proved that there is a sharp threshold at which lower density random graphs are disconnected and higher density ones are connected.  Motivated by ideas in geometric group theory we will explain some new threshold theorems for random graphs and applications of these results to the geometry of Coxeter groups.  This talk will include joint work with Falgas-Ravry, Hagen, Sisto, and Susse (in various combinations).

3/2: When is a planar rod configuration infinitesimally rigid? 

Speaker: Signe Lundqvist

Abstract: A rod configuration is a realisation of an incidence geometry as points and lines in the Euclidean plane. In this talk, we will introduce notions of rigidity for rod configurations and discuss approaches for determining whether a given rod configuration is infinitesimally rigid. We will generalise a result due to Whiteley.

Rod configurations generalise frameworks of graphs. Rigidity of graphs is well-studied. There is a combinatorial characterisation of the minimally rigid graphs, due to Pollaczek-Geiringer (1927) and later Laman (1970).

27/1: MacWilliams Identities for q-Polymatroids and Applications

Speaker: Eimear Byrn, University College Dublin (UCD)

Abstract: A q-polymatroid consists of a lattice of subspaces of a vector space endowed with a rank function that is both increasing and submodular. They were introduced independently by Gorla et al (2020) and Shiromoto (2019) as q-analogues of polymatroids and in reference to matrix codes. A number of invariants of codes are in fact matroid invariants, including the MacWilliams duality theorem. MacWilliams identities for classical matroids have been studied by a number of authors (e.g. Brylawski, Oxley, Britz, Shiromoto).  In this talk we will consider duality of q-polymatroids and will give a version of a MacWilliams theorem for q-polymatroids, using the characteristic polynomial. As as application of this result, we will state an Assmus-Mattson-like theorem that establishes criteria for the existence of weighted subspace designs arising from a q-polymatroid. This talk is based on joint work with Michela Ceria, Relinde Jurrius, and Sorina Ionica.

20/1: Uniform Turán density

Speaker: Samuel Mohr, Masaryk University

Abstract: In the early 1980s, Erdos and Sos initiated the study of the classical Turán problem with a uniformity condition: the uniform Turán density of a hypergraph $H$ is the infimum over all $d$ for which any sufficiently large hypergraph with the property that all its linear-size subhyperghraphs have density at least $d$ contains $H$.

In particular, they raise the questions of determining the uniform Turán densities of $K_4^{(3)-}$ and $K_4^{(3)}$. The former question was solved only recently in [Israel J. Math. 211 (2016), 349--366] and [J. Eur. Math. Soc. 97 (2018), 77--97], while the latter still remains open for almost 40 years. In addition to $K_4^{(3)-}$, the only $3$-uniform hypergraphs whose uniform Turán density is known are those with zero uniform Turán density classified by Reiher, Rodl and Schacht [J. London Math. Soc. 97 (2018), 77--97] and a specific family with uniform Turán density equal to $1/27$.

In this talk, we give an introduction to the concept of uniform Turán densities, present a way to obtain lower bounds using color schemes, and give a glimpse of the proof for determining the uniform Turán density of the tight $3$-uniform cycle $C_\ell^{(3)}$, $\ell\ge 5$.

13/1: Common and locally common graphs

Speaker: Daniel Kráľ, Masaryk University

Abstract: A graph is common if the number of its monochromatic copies in a 2-edge-coloring of a large complete graph is minimized by the random 2-edge-coloring. This notion goes back to the work of Erdős in the 1960s, who conjectured that every complete graph is common. The conjecture was disproved by Thomason in the 1980s, however, the classification of common graphs remains one of the most intriguing problems in extremal combinatorics.

Sidorenko's Conjecture (if true) would imply that every bipartite graph is common.  However, until Hatami et al. showed that a 5-wheel is common about a decade ago, common graphs with chromatic number two or three only were known. In this talk, we present a construction of connected common k-chromatic graphs for every k; this answers a problem posed by Conlon, Fox and Sudakov [LMS Lecture Notes Ser. 424 (2015), 49–118].

We also consider an extension of the notion to m-edge-colorings and present present a construction of connected m-common non-bipartite graphs, which resolves a problem raised by Jagger, Šťovíček and and Thomason [Combinatorica 16 (1996), 123-141], and discuss the notion in the local setting, where we give a complete characterization based on the 12 initial terms in the Taylor series determining the number of monochromatic copies in perturbations of the random 2-edge-coloring.

The talk is based on results obtained jointly with Robert Hancock, Matjaž Krnc, Jonathan A. Noel, Sergey Norin, Jan Volec and Fan Wei.

2021

16/12: "Finite Semifields and their Invariants"

Speaker: John Sheekey

Abstract: Finite Semifields are  division algebras in which multiplication is not assumed to be associative. They have been studied in many contexts over the years; as algebraic objects, as the coordinatisation of projective planes with certain symmetries, and more recently as rank-metric codes. Determining the equivalence of two semifields is difficult, and so various equivalence invariants have been proposed and studied.

In this talk we will discuss some of these invariants, with particular emphasis on recent work with Michel Lavrauw on the tensor rank. The tensor rank is an invariant naturally arising from multilinear algebra, and can be viewed as a measure of multiplicative complexity. We present the first known examples of finite semifields of lower tensor rank than the finite field of the same size.

9/12: Colloquium "Polyhedra, polytopes and finite simple groups"

Speaker: Dimitri Leemans (KAW Guest Professor at Umeå University 2022)

Abstract: The classification of finite simple groups, achieved in the eighties, is one of the most spectacular achievements in mathematics, combining the efforts of hundreds of researchers. Its proof amounts to roughly 15,000 pages. Current revisions of this result aim to bring back to less than 10,000 pages the proof of this amazing result. Simple groups play in group theory the role of prime numbers in number theory. They are the building blocks of groups as the primes are the building blocks of numbers.

The classification gives 18 infinite families and 26 groups that are called sporadics, the largest one being the Monster or Friendly Giant, a group of order 808,017,424,794,512,875,886,459,904,961,710,757,005,754,368,000,000,000, roughly 8x 10^{53}.

Geometric interpretations of the finite simple groups have been discovered over decades and Jacques Tits' theory of buildings is so far the most unified geometric way of seeing these groups. Only the alternating and the sporadic groups are not covered by Tits' theory.

In this talk, we will focus on polyhedra and polytopes. These very natural geometric objects have been studied for millennia. The most famous ones are probably the five platonic solids, competing with the truncated icosahedron, also known as the buckminsterfullerene.

We will introduce polytopes in an abstract way. We will then focus on two classes of polytopes. Those that have maximum level of symmetry (the regular ones) and those that have all rotational symmetries but no mirror symmetries (the chiral ones).

We will then make the link between these objects and special sets of generators of groups. A regular polytope has an automorphism group generated by involutions. This group is a smooth quotient of a Coxeter group. Similary a chiral polytope has a group generated by elements (not necessarilyinvolutions) and therefore these geometric objects can be classified using their automorphism group.

The finite simple groups that can appear as automorphism groups of regular polytopes have been classified. We will talk briefly about that classification. In the chiral case, this classification is not complete yet. We will explain where we stand nowadays.

The talk will be accessible to a large audience. We do not intend to enter into technical details. 

2/12: "Hermitian self-orthogonal codes"

Speaker: Simeon Ball, Universitat Politécnica Catalunya, Barcelona, Spain

Abstract: Let C be a [n,k]_{q^2} linear code, i.e. a k-dimensional subspace of the n-dimensional vector space over the finite field with q^2 elements F_{q^2}. The code C is linearly equivalent to a Hermitian self-orthogonal code if and only if there are non-zero a_i in the finite field with q elements F_{q} such that a_1 u_1 (v_1)^q+…+a_n u_n (v_n)^q=0 for all u and v in C. For any linear code C of length n over the finite field with q^2 elements, Rains defined the puncture code P(C) to be

P(C)={a=(a_1,…,a_n) in (F_q)^n : a_1 u_1 (v_1)^q+…+a_n u_n (v_n)^q=0 for all u and v in C }.

There is a truncation of a linear code C over F_{q^2} of length n to a linear over F_{q^2} of length r <= n which is linearly equivalent to a Hermitian self-orthogonal code if and only if there is an element of P(C) of weight r. Rains was motivated to look for Hermitian self-orthogonal codes, since there is a simple way to construct a [[ n,n-2k]]_q quantum code, given a Hermitian self-orthogonal code. This construction is due to Ketkar et al, generalising the F_4-construction of Calderbank et al.

In this talk, I will detail an effective way to calculate the puncture code. I will outline how to prove various results about when a linear code has a truncation which is linearly equivalent to a Hermitian self-orthogonal linear code and how to extend it to one that does in the case that it has no such truncation. In the case that the code is a Reed-Solomon code, it turns out that the existence of such a truncation of length r is equivalent to the existence of a polynomial g(X) in F_{q^2}[X] of degree at most (q-k)q-1 with the property that g(X)+g(X)^q has q^2-r distinct zeros in F_{q^2}.

(Joint work with Ricard Vilar)

25/11: "Graphical" introduction to parapolar spaces

Speaker: Anneleen De Schepper, Ghent University, Belgium

Abstract: In this talk I want to give a gentle introduction to parapolar spaces. These are are axiomatically defined point-line geometries,  introduced by Cooperstein in the 70ies to capture the behaviour of the Grassmannians of spherical buildings. Actually, all interesting known examples arise from buildings (not necessarily spherical). I will talk about some results on how to recognise a parapolar space given local information, starting from some graph related examples, and ending with an application in the Freudenthal-Tits magic square.

18/11: "Maker-Breaker Percolation Game on the Square Lattice"

Speaker: Vojtěch Dvorak (University of Cambridge)

Abstract: The (m,b) Maker-Breaker Percolation Game played on the edges of Z^2 has simple rules. Initially, all the edges of Z^2 are marked as unsafe. Maker and Breaker take turns. In each turn of hers, Maker marks m unsafe edges as safe. While in each of his turns, Breaker erases b unsafe edges from the graph. If the connected component of the origin ever becomes finite, Breaker wins, and else Maker wins.

Day and Falgas-Ravry proved that whenever b/m \geq 2, Breaker wins, and whenever b/m \leq \frac{1}{2}, Maker wins. In this talk, I will discuss an improvement for the side of Breaker. 

(Joint work with Adva Mond and Victor Souza.)

18/11: "Counting Hamiltonian cycles in Dirac hypergraphs"

Speaker: Adva Mond (University of Cambridge) 

Abstract: For 0 ≤ \ell < k, a Hamiltonian \ell-cycle in a k-uniform hypergraph H is a cyclic ordering of the vertices of H in which the edges are segments of length k and every two consecutive edges overlap in exactly \ell vertices.

We show that for all 0 ≤ r < k-1, every Dirac k-graph, that is, a k-graph with minimum co-degree pn for some p>1/2, has (up to a subexponential factor) at least as many Hamiltonian \ell-cycles as a typical random k-graph with edge-probability p.

This improves a recent result of Glock, Gould, Joos, Osthus and Kühn, and verifies a conjecture of Ferber, Krivelevich and Sudakov for all values 0 ≤ r < k-1.

(Joint work with Asaf Ferber and Liam Hardiman.)

11/11: "The dimension of the divisibility order" given by Victor Souza

Speaker: Victor Souza, University of Cambridge

Abstract: The Dushnik-Miller dimension of a partially-ordered set P is the smallest d such that one can embed P into a product of d linear orders.

We prove that the dimension of the divisibility order on the interval {1,.. n} is equal to (log n)2 (log log n)-Θ(1) as n goes to infinity. We will also see similar results when for variant notions of dimension and when the divisibility order taken over various other sets of integers.

Based on joint work with David Lewis and also with Leo Versteegen.

4/11: "The n-queens problem"

Speaker: Candida Bowtell, University of Oxford

Abstract: The n-queens problem asks how many ways there are to place n queens on an n x n chessboard so that no two queens can attack one another, and the toroidal n-queens problem asks the same question where the board is considered on the surface of a torus. Let Q(n) denote the number of n-queens configurations on the classical board and T(n) the number of toroidal n-queens configurations. The toroidal problem was first studied in 1918 by Pólya who showed that T(n)>0 if and only if n is not divisible by 2 or 3. Much more recently Luria showed that T(n) is at most ((1+o(1))ne^{-3})^n and conjectured equality when n is not divisible by 2 or 3. We prove this conjecture, prior to which no non-trivial lower bounds were known to hold for all (sufficiently large) n not divisible by 2 or 3. We also show that Q(n) is at least ((1+o(1))ne^{-3})^n for all natural numbers n which was independently proved by Luria and Simkin and, combined with our toroidal result, completely settles a conjecture of Rivin, Vardi and Zimmerman regarding both Q(n) and T(n). 

In this talk we'll discuss our methods used to prove these results. A crucial element of this is translating the problem to one of counting matchings in a 4-partite 4-uniform hypergraph. Our strategy combines a random greedy algorithm to count `almost' configurations with a complex absorbing strategy that uses ideas from the methods of randomised algebraic construction and iterative absorption.

This is joint work with Peter Keevash.

28/10: "Counting H-free orientations of graphs"

Speaker: Oliver Janzer, ETH Zürich

Abstract: In 1974, Erdős posed the following problem. Given an oriented graph H, determine or estimate the maximum possible number of H-free orientations of an n-vertex graph. When H is a tournament, the answer was determined precisely for sufficiently large n by Alon and Yuster. In general, when the underlying undirected graph of H contains a cycle, one can obtain accurate bounds by combining an observation of Kozma and Moran with celebrated results on the number of F-free graphs. We resolve all remaining cases in an asymptotic sense, thereby giving a rather complete answer to Erdős's question. Moreover, we determine the answer exactly when H is an odd cycle and n is sufficiently large, answering a question of Araújo, Botler and Mota.

Joint work with Matija Bucic and Benny Sudakov.

21/10: "Maker-Breaker domination game"

Speaker: Valentin Gledel

Abstract: The Maker-Breaker domination game is a two player game played on a graph. The two players, Dominator and Staller, alternatively select vertices of the graph. If at some point, the vertices selected by Dominator form a dominating set, he wins the game. If however Staller can keep Dominator from ever dominating the graph, she wins the game.

As in every two player game with perfect information, one of the two players is bound to have a winning strategy. The goal of this talk will be to study two problems: the first one is to determine which player has a winning strategy and the other one is to know the number of moves Dominator needs to play to win the game, assuming he has a winning strategy. We give complexity results for both of these problems.

14/10: "Nested cycles with no geometric crossings"

Speaker: Irene Gil Fernández, University of Warwick

Abstract: In this talk, we answer the following question posed by Erdős in 1975: what is the smallest function $f(n)$ for which all graphs with $n$ vertices and $f(n)$ edges contain two edge-disjoint cycles $C_1$ and $C_2$, such that the vertex set of $C_2$ is a subset of the vertex set of $C_1$ and their cyclic orderings of the vertices respect each other? We prove the optimal linear bound $f(n)=O(n)$ using sublinear expanders. This is joint work with Jaehoon Kim, Younjin Kim and Hong Liu.

7/10: "Towards the 0-statement of the Kohayakawa-Kreuter conjecture"

Speaker: Joseph Hyde, University of Warwick

Abstract: Let $r \in \mathbb{N}$ and $H_1, \ldots, H_r$ be graphs. We write $G_{n,p} \to (H_1, \ldots, H_r)$ to denote the property that whenever we colour the edges of $G_{n,p}$ with colours from the set $[r] := \{1, \ldots, r\}$ there exists $i \in [r]$ and a copy of $H_i$ in $G_{n,p}$ monochromatic in colour $i$. 

There has been much interest in determining the asymptotic threshold function for this property. R\"{o}dl and Ruci\'{n}ski (1995) determined the threshold function for the general symmetric case; that is, when $H_1 = \cdots = H_r$. A conjecture of Kohayakawa and Kreuter (1997), if true, would fully resolve the asymmetric problem. Recently, the 1-statement of this conjecture was confirmed by Mousset, Nenadov and Samotij (2021^{+}). The 0-statement however has only been proved for pairs of cycles, pairs of cliques and pairs of a clique and a cycle.    

In this talk we introduce a reduction of the 0-statement of Kohayakawa and Kreuter's conjecture to a certain deterministic, natural subproblem. To demonstrate the potential of this approach, we show this subproblem can be resolved for almost all pairs of regular graphs.'

30/9: "The Erd\H{o}s-Rothschild problem"

Speaker: Katherine Staden, University of Oxford

Abstract: Consider an $n$-vertex graph $G$ whose edges are coloured with $s$ colours so that there is no monochromatic clique of size $k$, and call such a colouring of $G$ valid. The Erd\H{o}s-Rothschild problem from 1974 is to determine the maximum number of valid colourings over all $n$-vertex graphs $G$. This problem is in general wide open and an exact (or even asymptotic) answer is only known for a few pairs $(k,s)$. In this talk I will discuss a method for obtaining new exact results. Joint work with Oleg Pikhurko.

23/9: "Maximum Number of Almost Similar Triangles in the Plane"

Speaker: Felix Clemen, University of Illinois Urbana-Champaign

Abstract: A triangle T' is epsilon-similar to another triangle T if their angles pairwise differ by at most epsilon. Given a triangle T, epsilon>0 and a natural number n, Bárány and Füredi asked to determine the maximum number of triangles being epsilon-similar to T in a planar point set of size n. We determine this quantity for almost all triangles T and sufficiently small epsilon. Exploring connections to hypergraph Turán problems, we use flag algebras and stability techniques for the proof. This is joint work with József Balogh and Bernard Lidický.

16/9: "Maximal sum-free sets in abelian groups"

Speaker: Andrew Treglown, University of Birmingham

Abstract: A sum-free set S in a group (or set of integers) G is a set which contains no solution to x+y=z. S is a maximal sum-free subset if it is not properly contained in any other sum-free subset of G.

Results of Diananda--Yap and Green--Ruzsa determine the size of the largest sum-free set in any finite abelian group. Green and Ruzsa also determined, up to an error term in the exponent, the number of sum-free sets in any finite abelian group. However, far less is known about the number of maximal sum-free sets in abelian groups.

In this talk I will outline an approach to this latter problem that I developed with Balogh, Liu and Sharifzadeh. In particular, I will describe an application of this method that gives a sharp count on the number of maximal sum-free subsets in both the binary and ternary spaces. This is joint work with Nathanael Hassler.

17/6, 10.15-11.15 Jie Ma (USTC)

10/6, 15.15-16.15 Laura Eslava (Mexico)

3/6, 14.15-15.15 Eoin Long (Birmingham)

27/5, 14.15-15.15 Maria Axenovich (Karlsruhe)

20/5, 14.15-15.15 Andrew Treglown (Birmingham)

6/5, 15.15-16.15 Yi Zhao (Georgia State)

29/4, 14.15-15.15   Vincent Pfenninger (Birmingham)

* cancelled:  13/1-14/1 Fourth Midwinter Meeting in Discrete Probability

organised by Klas Markström and Victor Falgas-Ravry *

 

2020

• 1/10 Victor Falgas-Ravry, Extremal problems for multigraphs
• 17/10 Erika Roldán, Topology of random 2-dimensional cubical complexes
• 22/10 Klara Stokes
• 29/10 Maryam Sharifzadeh
• 5/11 Victor Falgas-Ravry
• 12/11 Johanna Björklund
• 19/11 Klas Markström
• 26/11 Signe Lundqvist
• 3/12 Per-Håkan Lundow
• 10/12 Gerold Jäger
• 17/12 Klas Markström
• 1/3 Seminar series cancelled for the semester due to the Covid19 epidemic.3/2 Mittag-Leffler Mobility Programme Colloquium by Karim Adiprasito (Copenhagen University and Hebrew University  of Jerusalem), "Hodge theory between geometry, combinatorics and algebra", 13.15 in room MA346.
• 15/1-16/1 Third Midwinter Meeting in Discrete Probability, organised by Klas Markström and Victor Falgas-Ravry
  ancock, The Maker-Breaker Rado game on a random set of integers

2019

• 10/12 Michał Przykucki, Parking on the Integers
• 3/12  Jonas Westin and Anton Vernersson, Shortest Path Calculations for Routing Ambulances on the Swedish Road Network
• 20/11 Victor Falgas-Ravry, On 1-independent random graphs
• 14/11 Robert Johansson, Boolean analysis and Frankl’s Conjecture
• 6/11 Ian Hoffecker, Microscopy-by-sequencing: optics-free biological imaging using network topology
• 24/10 Per-Håkan London, Where discrete meets continuous (docent lecture)
• 23/10 A. Nicholas Day, Maximising the number of copies of a small graph in large graphs of fixed edge density
• 16/10 Andrew Treglown, Vertex Ramsey properties of randomly perturbed graphs
• 19/8 Marcel Turkensteen, The trade-off between costs and carbon emissions from lot-sizing decisions
• 14/6 Denys Shcherbchak, Enumerative Approaches and Structural Results for Selected Combinatorial Problems (thesis defence)
• 13/6 Armen Asratian, Local-global phenomena in Hamiltonian graph theory
• 24/5 Lan Anh Pham, On Avoiding and Completing Colorings
• 16/5 Lars-Daniel Öhman,  On Induction and Explanation
• 2/5 Robert Johanson, Remarks on the Union-Closed Sets Conjecture
• 25/4 Frank Drewes, A Biased Introduction to Automata and Grammars for Graph Languages
• 18/4 Lan Anh Pham,  Hypergraph expanders from Cayley graphs, after David Conlon
• 11/4 Victor Falgas-Ravry, Triangle degrees in graphs
• 28/3 Lan Anh Pham, A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound
• 21/3 A. Nicholas Day, Saturated Graphs of Prescribed Minimum Degree 
• 14/3 Klas Markström, Complete subgraphs in multipartite hypergraphs
• 2/21 Nicolás Sanhueza-Matamala,  Covering and tiling hypergraphs with tight cycles
• 2/14 Lan Anh Pham Improved small-set expansion from higher eigenvalues, after Ryan O'Donnell and David Witmer
• 5/2 Victor Falgas-Ravry, Colourings, cake and combinatorics: Sperner's Lemma and its applications (docent lecture)
• 16/1-17/1 Second Midwinter Meeting in Discrete Probability, organised by Klas Markström and Victor Falgas-Ravry

2018

• Fall 2018 - Discrete seminar on hibernation during Victor's parental leave.
• 13/6 Cory Palmer, The Szemerédi Regularity Lemma
• 1/6 Joel Larsson, On random satisfiability and optimization problems (thesis defence)
• 23/5 Andrew Treglown, A bandwidth theorem for locally dense graphs
• 17/5 Lan Anh Pham, On Avoiding and Completing Edge Colorings (licentiate thesis defence)
• 16/5 Dmitrii Zhelezov, Decoupling, induction on scales and sum-product estimates
• 25/4 A. Nicholas Day, Maximising the Number of k-cycles in Tournaments
• 14/3 Gerold Jäger, Optimal strategies and bounds for several variants of Black-Peg Static Mastermind and Black-Peg Static AB Game
• 7/3 Olof Sisask, A notion of VC-dimension for subsets of groups -- analysis, combinatorics and structure
• 21/2 Joel Larsson, Biased random k-SAT
• 14/2 Victor Falgas-Ravry, Square percolation
• 24/1 Robert H

2010-2017

2017

• 21/9 Jakub Sliacan, Improving bounds on packing densities of 4-point permutations
• 5/10 Victor Falgas-Ravry, Covering problems for 3-graphs
• 19/10 Klas Markström, Non-jumps for hypergraphs
• 26/10 Roland Häggkvist, Towards a disproof of the Fulkerson Conjecture
• 9/11 Denys Shcherbak, Efficient removal lemmas of matrices (after Alon and Ben-Eliezer)
• 16/11 Lan Anh Pham, Komlós's tiling theorem via graphon covers (after Hladký, Hu and Piguet)
• 30/11 Roland Häggkvist, Talk without a title
• 12/12 Denys Shcherbak, Algorithmical Approaches and Structural Results for Selected Combinatorial Optimization Problems (Licentiate thesis defence)
• 11/1 Marcel Turkensteen, The usage of tolerances, MA136
• 18/1-19/1 Midwinter Meeting in Discrete Probability, organised by Klas Markström and Victor Falgas-Ravry
• 2/2 Per Håkan Lundow, Some distributions related to the Ising model
• 2/3 Klas Markström, Condorcet Domains --- and more!
• 15/3 Victor Falgas Ravry, Long paths in 1-independent percolation
• 30/3 Jonas Westin, The impact of modelling sea transport loops
• 3/5 Nicholas Day, Multicolour Ramsey Numbers of Odd Cycles, MA346, 15:30
• 11/5 Martin Rosvall, Maps of sparse Markov chains efficiently reveal overlapping and hierarchical community structure in network flows with memory
• 12/6-15/6 Special session on Graphs, Hypergraphs and Set Systems organised by Victor Falgas-Ravry, as part of the Meeting of the Swedish, Spanish and Catalan Mathematical Societies
• 21/6 Lan Anh Pham, The list chromatic number of graphs with small clique number
• 21/6 Joel Larsson, Complex martingales and asymptotic enumeration, 14:15

2016

• 6/9 Lars-Daniel Öhman, Vad jag talar om när jag talar om de naturliga talen, N450 (docent lecture)
• 5/10 Victor Falgas-Ravry, Multicolour containers, extremal entropy and counting, MA406
• 3/11 Klas Markström, Random simplicial complexes
• 30/11 Roland Häggkvist, Variations on the Cycle Double Cover Conjecture and a Brilliant Idea of Uldis Celmins, MA378
• 1/12 Christian Glazik, A lower Bound for Permutation-Mastermind, MA146
• 1/12 Gerold Jäger, An Optimal Strategy for Static Black-Peg
  Mastermind with Two Pegs, MA146
• 7/12 Lan Anh Pham, Asymptotic normality of the k-core in random graphs, after Svante Janson and Malwina Luczak
• 7/12 Joel Larsson, Factors in random graphs, after Anders Johansson, Jeff Kahn and Van Vu
• 14/12 Joel Larsson, Cardy's formula on the triangular lattice, the easy way (after Vincent Beffara), MA378
• 19/12 Julian Sahasrabudhe, C-Ramsey graphs induce many subgraphs with distinct sizes
• 11/2 Roland Häggkvist, Frames and the cycle double cover conjecture
• 17/5 Denys Shcherbak, Latin Squares
• 9/6 Joel Larsson, Balanced Matroids

2015

• 25/9 Denys Shcherbak, The Zero Forcing Number of Bijection Graphs, MA346
• 4/10 Lan Anh Pham, Structure of classes of graphs defined by constraints on chords, 11:00
• 22/10 Joel Larsson, Lovasz' Theta function and the Sandwich Theorem
• 12/2 Trevor Pinto, Edge-disjoint directed paths in the hypercube, MA346
• 26/2 Ahmad Hosseini, Multi-Period Multi-Product Distribution Planning Problems: Model-Based and Network-Based Approaches, MA346
• 6/3 Klas Markström, Full subgraphs, MA356

2014

• 15/1-15/5, Research Programme "Graphs, Hypergraphs and Computing" at the Institut Mittag-Leffler, organised by Klas Markström
• 6/5 Nils-Hassan Quttineh, Using rolling horizon techniques in the planning process for a Chemical Process Industry, MA356
• 4/6 Andrew Uzzell, Graph limits and the structure of random graphs in monotone graph classes
• 12/6 Alexander Engström, Connectivity of graphs from Gröbner and Graver bases

2013

• 12/9 Joel Larsson, Minimum matching in pseudo-dimension 0<d<1, MA346
• 20/9 Fei Song, To apply the Regularity Lemma in the monochromatic vertex partition problem, MC343
• 1/11 Victor Falgas-Ravry, On Sperner's problem for G-independent hypercubes
• 8/11 Roland Häggkvist, CDC and the second Hamiltonian circuit, MA346
• 15/11 Gerold Jäger, SAT and IP Based Algorithms for Magic Labeling with Applications
• 6/12 Victor Falgas-Ravry, Separating path systems
• 13/12 Lars-Daniel Öhman, Alcuin numbers of graphs
• 20/12 Klas Markström, Random subcubes of hypercubes

2012

• 27/9 Victor Falgas-Ravry, Flag algebras and applications to extremal combinatorics, UB341
• 2/2 Arthur Hoffman Ostenhof, Structures in Cubic Graphs, MA356
  Fall 2011:
• 8/12 Roland Häggkvist, 1-factor coverings, MA356
  Spring 2011:
• 31/3 Robert Johnson, Universal cycles for permutations and other combinatorial families, MA378
• 7/4 Allan Lo, Dirac-type degree thresholds for perfect matchings in hypergraphs
• 5/5 Jonas Hägglund, The hunting of the snark, MA346
• 12/5 Roland Häggkvist, Factor theorems, MA378
• 20/5, Carl Johan Casselgren, PhD Thesis defense, MA121

2010

• 4/11 Lars-Daniel Öhman, How many colours suffice? MA346
• 11/11 Alan Lo, A Dirac type condition for properly coloured paths and cycles
• 18/11 Roland Häggkvist, Orthogonal factors
• 25/11 Tomas Nilson, Inner balance of designs, MA346
• 2/12 Roland Häggkvist, Orthogonal factors, part II
• 9/12 Jonas Hägglund, Covering graphs by cycles and perfect matchings
• 16/12 Lars Hellström, An ordering problem
• 18/2 Lars Hellström Deletion contraction graph polynomials
• 4/3 Carl-Johan Casselgren Backbone colourings, t-tuple colourings and generalized Mycielski graphs
• 11/3 Lina Andrén List colouring squares of planar graphs
• 18/3 Roland Häggkvist Probabilities for iterated Latin squares
• 25/3 Jonas Hägglund On Tutte's conjecture and the proof that disappeared
• 8/4 Daniel Andrén
• 15/4 Klas Markström