Past Events

 

 

Past Combinatorics Seminars

 

2022/23

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.

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