• home

Defined as the difference between its two largest eigenvalues, the spectral gap of a graph plays an important role on our understanding of its connectivity as observed by Godsil and Royle (2001). Since computing the largest eigenvalue of a graph is generally not too difficult, the crux to understanding the spectral gap of a graph is to compute its second largest eigenvalue. In this talk, we will consider the spectral gap of certain graphs in the perfect matching association scheme. Since these graphs are part of the same association scheme, they have the same eigenspaces. These eigenspaces correspond to certain irreducible representations of the symmetric group and thus, one could use these irreducible representations to compute the eigenvalues of each graph. In practice, such computations are difficult to perform which makes it difficult to find the eigenspace that realizes the second largest eigenvalue. The focus of my talk will be to identify this eigenspace for selected graphs in the scheme. This is joint work with Himanshu Gupta, Allen Herman, Roghayeh (Mitra) Maleki, and Karen Meagher.

Abstract: I will discuss several recent results on the Turán density of long cycle-like hypergraphs. These results (due to Kamčev–Letzter–Pokrovskiy, Balogh–Luo, and myself) all follow a similar framework, and I will outline a general strategy to prove Turán-type results for tight cycles in larger uniformities or for other "cycle-like" hypergraphs.

One key ingredient in this framework, which I hope to prove in full, is a hypergraph analogue of the statement that a graph has no odd closed walks if and only if it is bipartite. More precisely, for various classes C of "cycle-like" r-uniform hypergraphs — including, for any k, the family of tight cycles of length k modulo r — we equiivalently characterize C-hom-free hypergraphs as those admitting a certain type of coloring of (r-1)-tuples of vertices. This provides a common generalization of results due to Kamčev–Letzter–Pokrovskiy and Balogh–Luo.

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.