• home

The Turan density of a forbidden hypergraph F is the largest edge density a large hypergraph H can have without containing any copy of F, and determining this number for various F is a notoriously difficult problem. One on-ramp to this question (from Erdos and Sos) is to furthermore require that the hyperedges of H are distributed nearly uniformly across the vertices, giving the uniform Turan density of F. All known examples of such uniformly dense H avoiding some F follow the so-called “palette” construction of Rodl. In this talk we will introduce each of these notions before discussing our main result, that any palette can be obtained as an extremal construction for some finite family of forbidden subgraph F, which will require the tools of hypergraph regularity and Lagrangians. As an application we can obtain some (interesting) new values as the uniform Turan density of forbidden families.

Based on joint work with Simon Piga, Marcelo Sales, and Bjarne Schuelke.

Abstract: A 2-cell embedding of a graph G in an orientable surface of genus k is an embedding in which each face is homeomorphic to an open disk. The distribution of genus across all 2-cell embeddings of G is called the genus distribution of G. In this talk, we explore embeddings of cubic planar graphs, particularly those with small genus. Using local rotations, we explore ways of describing each embedding of a cubic planar graph and how the face structure differs from that of a planar embedding. We introduce the unstable dual of an embedding of a cubic planar graph, a subgraph of the dual graph, and show how the genus of the corresponding embedding can be determined from properties of this unstable dual.

This is joint work with Bojan Mohar (Simon Fraser University and University of Ljubljana).

ABSTRACT: The question of whether one graph can be embedded in another is a fundamental problem in graph theory. In 2020, Joos and Kim introduced a generalization of the basic graph embedding problem to graph collections. Let G={G_1,...,G_m} be a collection of not necessarily distinct graphs on a common vertex set V with |V|=n. Given a graph H with at most m edges, a rainbow copy of H in G is a copy of H on V using at most one edge from each graph G_i. Joos and Kim showed that Dirac's Theorem can be generalized to this setting; that is, if m=n and the minimum degree of each graph in G is at least n/2, then G contains a rainbow Hamilton cycle. Recently, Bowtell, Morris, Pehova, and Staden proved an asymptotically best possible strengthening of this result when we instead require the existence of Hamilton cycles with every possible edge-colouring. We prove a version of their result for powers of Hamilton cycles. Based on work with Emily Heath, Joseph Hyde, and Natasha Morrison.

Abstract: We will discuss a class of ideals in a polynomial ring studied by Mark Haiman in his work on the Hilbert scheme of points and discuss how they are related to homology of affine Springer fibers, Khovanov-Rozansky homology of links, and to the ORS conjecture. We will do some explicit examples of computing KR-homology using combinatorial link recursions developed by Elias and Hogancamp.

An F-decomposition of a graph G is a set of subgraphs of G, each isomorphic to F, whose edge sets partition the edge set of G.  I will speak about a result showing that, for each odd k ≥ 5, any graph G of sufficiently large order n with minimum degree at least (1/2+1/(2k-4)+o(1))n has a C_k-decomposition if and only if k divides |E(G)| and all vertex degrees in G are even.  Our methodology also leads to results on F-decompositions for other 3-partite graphs F. This is joint work with Darryn Bryant, Daniel Horsley, Barbara Maenhaut and Richard Montgomery.

Abstract: The log-rank conjecture is a longstanding open problem with multiple equivalent formulations in complexity theory and mathematics. In its linear-algebraic form, it asserts that the rank and partitioning number of a Boolean matrix are quasi-polynomially related.

In this talk, I will present a relaxed but still equivalent version of the conjecture based on a new matrix parameter, $\pm$-rank: the minimum number of all-1 rectangles needed to express the Boolean matrix as a $\pm 1$-sum. $\pm$-rank lies between rank and partition number, and our main result shows that it is in fact equivalent to rank up to a logarithmic factor.

This reframes the log-rank conjecture as: can every signed decomposition of a Boolean matrix be made positive with only quasi-polynomial blowup?

Additionally, I will show that the log-rank conjecture is equivalent to a conjecture on cross-intersecting set systems.

The talk is based on joint work with Shachar Lovett and Morgan Shirley.