Past Events

 

 

Past Combinatorics Seminars

 

2023/24

Forbidden spiders: A forbidden substructure characterisation of temporal planarity

Many topoligcal properties of combinatorial objects can be characterised by the forbidden substructures. In this talk we will explore a temporal analogue of planar graphs and prove a forbidden substructure result.

Given a graph $G$, we can obtain a \emph{minor} $H$ of $G$ by deleting and contracting edges from $G$. A \emph{temporal sequence} is a sequence of graphs $(G_1,\ldots,G_n)$ such that $G_i$ is a graph minor of $G_{i+1}$, or $G_{i+1}$ is a graph minor of $G_i$ for each $i\in[n-1]$. A temporal sequence generalises the notion of a temporal graph; indeed, a temporal graph can be thought of as a temporal sequence where the minor operations are only deletions.

Given a temporal sequence $(G)=(G_1,\ldots,G_n)$, we say that a sequence of planar embeddings $I=(\iota_i:G_i\hookrightarrow S^2)$ is a \emph{simultaneous embedding} of $(G)$ if the embeddings are `compatible with respect to the minor relations’. We will investigate when a temporal sequence has a simultaneous embedding.

This will be difficult in general, but we will be able to provide characterisations for some classes of temporal sequence.

My conjectures in spectral graph theory

Spectral graph theory uses the eigenvalues and eigenvectors of matrices that represent graphs, for example to bound NP-complete graph parameters. I will review generic applications of spectral graph theory and then discuss four of my conjectures that have been proved (by others). I will then discuss four of my conjectures that are unproven, and indicate potential ways forward for each of them.

Improving graph's parameters through random perturbation

Let G be a graph on n vertices, and assume that its minimum degree is at least k, or its independence number is at most t. What can be said then about various graph-theoretic parameters of G, such as connectivity, large minors and subdivisions, diameter, etc.? Trivial extremal examples (disjoint cliques, unbalanced complete bipartite graphs, random graphs and their disjoint unions) supply rather prosaic bounds for these questions.

We show that the situation is bound to change dramatically if one adds relatively few random edges on top of G (the so called randomly perturbed graph model, launched in a paper by Bohman, Frieze and Martin from 2003). Here are representative results, in a somewhat approximate form:

- Assuming delta(G)>=k, and for s < ck, adding about Cns*log (n/k)/k random edges to G results with high probability in an s-connected graph;

- Assuming alpha(G)<= t and adding cn random edges to G typically produces a graph containing a minor of a graph of average degree of order n/sqrt{t}.

In this talk I will introduce and discuss the model of randomly perturbed graphs, and will present our results.

A joint work with Elad Aigner-Horev and Dan Hefetz.

An Autumn Day of Combinatorics

This one-day meeting will focus on Combinatorics as well as its links to other areas, including Computer Science. The lectures will take place in Lecture Rooms A and C of the Watson Building. The meeting is supported by the EPSRC grant ‘Matchings and tilings in graphs’.

Website: https://web.mat.bham.ac.uk/A.Treglown/autumndayofcombinatorics Timetable: https://web.mat.bham.ac.uk/A.Treglown/WorkshopTimetable.pdf

No seminar

—-

Colouring d-dimensional triangulations

We consider d-dimensional triangulations and show structural equivalences for (d+1)-colourability and (d+2)-colourability of the vertices of such triangulations. In particular, we show that a d-dimensional triangulation admits a proper (d+1)-colouring if and only if every (d-2)-cell is incident with an even number of (d-1)-cells. Moreover, a d-dimensional triangulation C admits a proper (d+2)-colouring if and only if there exists a triangulation C’ that contains C such that for every (d-2)-cell in C’, the number of incident (d-1)-cells is divisible by three.

Hamilton decompositions of regular tripartite tournaments- a partial resolution

Given a Hamiltonian graph $G$, it is natural to ask whether it admits a full Hamilton decomposition. In the setting of regular oriented graphs, this has been confirmed for sufficiently large regular tournaments (Kühn, Osthus (2013)), bipartite tournaments (Granet (2022)), and $k$-partite tournaments when $k\geq 4$ (Kühn, Osthus (2013)).

For tripartite tournaments, a complete decomposition is not always possible; the known counterexample, $\mathcal{T}(\Delta)$, consisting of the blowup of $C_3$ with a single triangle reversed. However, it is reasonable to suggest that all such non-decomposable regular tripartite tournaments fall within a specifiable class, and perhaps are even are all isomorphic to $\mathcal{T}(\Delta)$.

In this talk we give a partial resolution towards this problem. We show that regular tripartite tournaments fall within one of three structural families. We prove Hamilton decomposability of two of these, and indicate a general strategy towards approaching the third.

Joint work with Francesco Di Braccio, Viresh Patel, Yanitsa Pehova, and Jozef Skokan.

Width parameters and the maximum independent set problem

Width parameters are graph invariants that measure the “complexity” of a graph. Treewidth, the most well-known graph width parameter, has important algorithmic implications: problems that are NP-hard in general, such as finding a maximum independent set in a graph, can be solved in polynomial time in graphs of bounded treewidth. However, treewidth does not capture the solvability of maximum independent set very well: there are many graph classes with unbounded treewidth which admit efficient algorithms for the maximum independent set problem. Recently, a number of new graph width parameters have been introduced with the intention of better representing the solvability of maximum independent set. In this talk, I will introduce these new width parameters, discuss recent results on induced matching treewidth, and describe several interesting open problems. This talk is based on joint work with Marcin Brianski, Jadwiga Czyżewska, Rose McCarty, Martin Milanic, Pawel Rzazewski, and Bartosz Walczak.

Counting cycles in planar graphs

Basic Turán theory asks how many edges a graph can have, given certain restrictions such as not having a large clique.

A more generalized Turán question asks how many copies of a fixed subgraph H the graph can have, given certain restrictions.

There has been a great deal of recent interest in the case where the restriction is planarity. In this talk, we will discuss some of the general results in the field, primarily the asymptotic value of N𝒫(n,H), which denotes the maximum number of copies of H in an n-vertex planar graph.

In particular, we will focus on the case where H is a cycle. It was determined that N𝒫(n,C2m)=(n/m)m+o(nm) for small values of m by Cox and Martin and resolved for all m by Lv, Győri, He, Salia, Tompkins, and Zhu. The case of H=C2m+1 is more difficult and it is conjectured that N𝒫(n,C2m+1)=2m(n/m)m+o(nm).

We will discuss recent progress on this problem, including verification of the conjecture in the case where m=3 and m=4 and a lemma which reduces the solution of this problem for any m to a so-called “maximum likelihood” problem.

The maximum likelihood problem is, in and of itself, an interesting question in random graph theory.

This is joint work with Emily Heath and Chris (Cox) Wells.

Hypergraphs with arbitrarily small codegree Turán density

Let k ≥ 3. Given a k-uniform hypergraph H, the minimum codegree δ(H) is the largest d ∈ ℕ 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 γ(F) of F is the smallest γ ∈ [0, 1) such that every k -uniform hypergraph on n vertices with δ(H) ≥ (γ+o(1))n contains a copy of F. Similarly as 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.

In this work, we show that for every ε > 0, there is a k-uniform hypergraph F with 0 < γ(F) < ε. This is in contrast to the classical Turán density, which cannot take any value in the interval (0,k!/kk) due to a fundamental result by Erdős.

This talk is part of the Birmingham Warwick Joint Combinatorics Seminar.

Ramsey goodness of bounded degree trees versus general graphs

Let G and H be graphs and assume the chromatic number of H is k. Motivated by a general lower bound result of Burr, we say that G is H-good if the Ramsey number R(G,H) is equal to (|G|-1)(k-1)+σ(H), where σ(H) is the minimum possible size of a colour class across all proper k-colourings of H. In this joint work with Richard Montgomery and Matías Pavez-Signé, we show that for every k and Δ, there exists a constant C=C(Δ,k), such that for every graph H with chromatic number k, every tree T with at least C|H| vertices and Δ(T) ≤ Δ is H-good. This confirms a conjecture of Balla, Pokrovskiy and Sudakov.

This talk is part of the Birmingham Warwick Joint Combinatorics Seminar.

A bipartite version of the Erdős--McKay conjecture

A set of vertices in a graph is said to be ‘homogeneous’ if it is a clique or an independent set. An old conjecture of Erdős and McKay states that if all homogeneous sets in an n-vertex graph are of order at most O(log n), then the graph contains induced subgraphs of each size from {0,1,...,Ω(n2)}. We prove a bipartite analogue of this conjecture: if all balanced homogeneous sets in an n by n bipartite graph are of order at most O(log n), then the graph contains induced subgraphs of each size from {0,1,...,Ω(n2)}. Based on joint work with Eoin Long.

This talk is part of the Birmingham Warwick Joint Combinatorics Seminar.

Counting copies with containers

If X is a finite subset of ℕd then what is the maximum size of a subset of {1,...,n}d that does not contain a scaled and/or translated copy of X? Let rX(n) denote this quantity. The Multidimensional Szemeredi Theorem (due to Furstenberg and Katznelson) states that rX(n) = o(nd), although rX(n) is not known more precisely. A follow-up question is, how many such X-free subsets of ℕd are there? Clearly, there are at least 2rX(n), by taking all subsets of a maximal one. We use the powerful hypergraph container lemma to show that for any |X|> 2 and infinitely many n ∈ ℕd, the number of X-free subsets of {1,...,n}d is at most 2O(rX(n)). This generalises work of Balogh, Liu, and Sharifzadeh on k-AP-free sets and Kim on corner-free sets.

This is joint work with Joseph Hyde, Natasha Morrison, Jonathan A. Noel and Ashna Wright.

This talk is part of the Birmingham Warwick Joint Combinatorics Seminar.

Orthogonal Circles in the Plane

By Eulers formula every planar graph on n vertices has at most 3n-6 edges. We investigate related extremal problems concerning graph classes that arise from orthogonal circle packings in the plane. We prove that the intersection graph of a non-nested circle arrangement is always planar. An application is an exact bound for the number of edges in this case. In the general case we present a conjecture for the exact bound and give heuristic evidence.

This talk is part of the Birmingham Warwick Joint Combinatorics Seminar.

Kalai's conjecture for coordinate-symmetric polytopes

Polyhedral combinatorics is an active area of research with many intriguing questions. Especially our understanding of the combinatorics and geometry of centrally symmetric polytopes is severely limited, as best illustrated by two elementary yet wildly open conjectures due to Kalai and Mahler. Kalai’s 3d conjecture asserts that the d-cube has the minimal number of faces among all centrally symmetric d-polytopes (that is, 3d many). Mahler’s conjecture asserts that the d-cube has the minimal Mahler volume (= volume times volume of dual) among all centrally symmetric d-polytopes. Both conjectures claim the same family of minimizers (the Hanner polytopes) and generally show many parallels, though their connection is not well understood. A polytope is coordinate-symmetric (or unconditional) if it is invariant under reflection on coordinate hyperplanes. While Mahler’s conjecture was spectacularly solved for this class of polytopes already in 1987, the same special case was still open for Kalai’s conjecture. In joint work with Raman Sanyal, we found two short and elegant proofs for Kalai’s conjecture for coordinate-symmetric (actually, locally coordinate-symmetric) polytopes, that I will present in this talk.

This talk is part of the Birmingham Warwick Joint Combinatorics Seminar.

(CANCELLED) Cycle partitions of directed and oriented graphs

  • Viresh Patel (QMUL)
  • Thursday 18 January 2024, 15:00, Physics West SR1 (103)

A conjecture of Jackson from 1981 states that every n -vertex d -regular oriented graph where n ≤ 4d + 1 has a Hamilton cycle. In the talk I will discuss a proof of this conjecture (for large n ). In fact, I’ll discuss a more general result that establishes, for each fixed k , the degree threshold guaranteeing that a regular directed/oriented graph can be covered with k vertex-disjoint cycles. This is joint work with Allan Lo and Mehmet Akif Yildiz.

Random Turán and counting results for general position sets over finite fields

  • Yaobin Chen (Fudan University)
  • Thursday 25 January 2024, 15:00, Physics West SR1 (103)

Let α(𝔽qd,p) denote the maximum size of a general position set in a p -random subset of 𝔽qd . We determine the order of magnitude of α(𝔽q2,p) up to polylogarithmic factors for all possible values of p , improving the previous best upper bounds obtained by Roche-Newton–Warren and Bhowmick–Roche-Newton. For d ≥ 3 we prove upper bounds for α(𝔽qd,p) that are essentially tight within certain intervals of p .

We establish the upper bound 2(1+o(1))q for the number of general position sets in 𝔽qd , which matches the trivial lower bound 2q asymptotically in the exponent. We also refine this counting result by proving an asymptotically tight (in the exponent) upper bound for the number of general position sets with fixed size. The latter result for d = 2 improves a result of Roche-Newton–Warren.

Our proofs are grounded in the hypergraph container method, and additionally, for d = 2 we also leverage the pseudorandomness of the point-line incidence bipartite graph of 𝔽q2 . This is a joint work with Xizhi Liu, Jiaxi Nie, Ji Zeng.

On the (k+2,k)-problem of Brown, Erdos and Sos for k=5,6,7

  • Shumin Sun (Warwick)
  • Thursday 1 February 2024, 15:00, Physics West SR1 (103)

Let f(r)(n;s,k) denote the maximum number of edges in an n-vertex r-uniform hypergraph containing no subgraph with k edges and at most s vertices. In 1973, Brown, Erdős and Sos conjectured that the limit limn → ∞n−2f(3)(n;k+2,k) exists for all k. The value of the limit was previously determined for k = 2 in the original paper of Brown, Erdős and Sos, for k = 3 by Glock and for k = 4 by Glock, Joos, Kim, Kuhn, Lichev and Pikhurko while Delcourt and Postle proved the conjecture (without determining the limiting value).

We determine the value of the limit in the Brown-Erdős-Sos problem for k = 5, 6, 7. More generally, we obtain the value of limn → ∞n−2f(r)(n;rk−2k+2,k) for all r ≥ 3 and k = 5, 6, 7.

This is joint work with Stefan Glock, Jaehoon Kim, Lyuben Lichev and Oleg Pikhurko.

Rigid partitions

  • Peleg Michaeli (Oxford)
  • Thursday 8 February 2024, 15:00, Physics West SR1 (103)

A graph is called d-rigid if there exists a "generic" embedding of its vertex set into R^d such that every continuous motion of the vertices that preserves the lengths of all edges actually preserves the distances between all pairs of vertices. In this talk, I will present new sufficient conditions for the d-rigidity of a graph in terms of the existence of "rigid partitions" - partitions of the graph that satisfy certain connectivity properties. Following this, I will outline several broadly applicable conditions for the existence of rigid partitions and discuss a few applications, among which are new results on the rigidity of highly connected, (pseudo)random graphs, and dense graphs.

The talk is based on joint work with Michael Krivelevich and Alan Lew.

Optimal Hamilton covers and linear arboricity for random graphs

  • Stefan Glock (Passau)
  • Thursday 15 February 2024, 15:00, Physics West SR1 (103)

We discuss the following recent result: for p ≥ Clog n/n, with high probability, the edges of the binomial random graph G ∼ G(n,p) can be covered by ⌈Δ(G)/2⌉ Hamilton cycles. This resolves a problem of Glebov, Krivelevich and Szabó, and improves upon previous work of Hefetz, Kühn, Lapinskas and Osthus, and of Ferber, Kronenberg and Long.

The talk is based on joint work with Nemanja Draganic, David Munha Correia and Benny Sudakov.

Weighted intersecting families

  • Allan Flower (Birmingham)
  • Thursday 22 February 2024, 15:00, Physics West SR1 (103)

Given natural numbers k and n, a k-uniform intersecting family is a subfamily of $[n]^{(k)}$ such that any two elements have non-empty intersection. In this talk, we will discuss the technique of left-compression (shifting) and explore a theory of generating elements for maximally left-compressed intersecting families (MLCIFs). We present an extension of the much-celebrated Erdős-Ko-Rado Theorem, showing that only the k `canonical' k-uniform MLCIFs can be made uniquely optimal under an increasing weight function.

Min-cut Preserving Decompositions in Graphs and Hypergraphs

  • Sagnik Mukhopadhyay (Sheffield)
  • Thursday 14 March 2024, 15:00, Physics West SR1 (103)

I will discuss the recent advances in graph and hypergraph decompositions that maintain minimum cuts in them. Such decompositions, such as the Kawarabayashi-Thorup decomposition, the expander decomposition and contraction-based decompositions, have seen several implications in fast algorithm design in various models of computation. I will survey these recent results and briefly present our contributions to this end. The talk will borrow materials from a number of works that appeared in STOC, FOCS and SODA in recent years as well as our FOCS 2022 and IPCO 2022 papers.

The Quantitative Helly Theorem

  • Nóra Frankl (Open)
  • Thursday 21 March 2024, 15:00, **ARTS LR7**

Helly's theorem states that if the intersection of any d+1 members of a finite family F of convex sets in R^d is nonempty, then the intersection of the whole family is nonempty. The Fractional Helly theorem of Katchalski and Liu, and the Quantitative Helly theorem of Bárány, Katchalski, and Pach are two famous extensions of this result. Improving on several recent works, we prove an optimal combination of these two extensions. We show that if a positive fraction of the (d+1)-tuples of F intersect in large volume, then a positive fraction of F intersects in large volume as well. Joint work with Attila Jung and Istvan Tomon.

Maximising copies of H in K_{r+1}-free graphs

  • Natasha Morrison (University of Victoria)
  • Thursday 25 April 2024, 15:00, **ARTS LR7**

Let H be a graph. We show that if r is large enough as a function of H, then the r-partite Turán graph maximizes the number of copies of H among all K_{r+1}-free graphs on a given number of vertices. This confirms a conjecture of Gerbner and Palmer.

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, 2023/24