Seminar

Title:Oriented graded Möbius algebras

Abstract:The graded Möbius algebra B(M) of a matroid M contains much combinatorial information about the flats of M. Its algebraic properties were instrumental in the proof of the Dowling—Wilson top-heavy conjecture. We will introduce a skew-commutative analogue OB(M) associated to every oriented matroid M, and discuss its algebraic structure. This is part of ongoing work joint with Yu Li.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:30pm,

Title:Worst-case instances of the stable set problem of graphs for the Lovász–Schrijver SDP hierarchy

Abstract:(Based on joint work with Levent Tunçel.)

In this talk, we discuss semidefinite relaxations of the stable set problem of graphs generated by the lift-and-project operator LS_+ (due to Lovász and Schrijver), and present some of our recent progress on this front. In particular, we show that for every positive integer k, the smallest graph with LS_+-rank k contains exactly 3k vertices. This result is sharp and settles a conjecture posed by Lipták and Tunçel from 2003.

The talk will be accessible to a general audience, and does not assume any prior knowledge of lift-and-project methods.

Title: Two Distinct Eigenvalues from a New Graph Product

Abstract:The parameter q(G) of a graph G is the minimum number of distinct eigenvalues of a symmetric matrix whose pattern is given by G.  We introduce a novel graph product by which we construct new infinite families of graphs that achieve q(G)=2.  Several graph families for which it is already known that q(G)=2 can also be thought of as arising from this new product.

Title:Complete bipartite induced minors (and treewidth)

Abstract:I will present a result that describes the unavoidable induced subgraphs of graphs with a large complete bipartite induced minor, and will discuss the connections and applications to bounding the treewidth in hereditary classes of graphs. If time permits, I will also sketch some proofs.

 Joint work with Maria Chudnovsky and Sophie Spirkl.

Title:The Abelian/non-Abelian correspondence and Littlewood-Richardson

Abstract:The Abelian/non-Abelian correspondence gives rise to a natural basis for the cohomology of flag varieties, which - except for Grassmannians - is distinct from the Schubert basis. I will describe this basis and its multiplication rules, and explain how to relate it to the Schubert basis for two-step flag varieties. I will then explain how this leads to new tableaux Littlewood--Richardson rules for many products of Schubert classes. This is joint work (separately) with Wei Gu and Linda Chen.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:30pm,

Title: 2-Y-homogeneous distance-biregular graphs

Abstract: Distance-biregular graphs (DBRGs) generalize distance-regular graphs by admitting a bipartition of the vertex set, where each part satisfies local distance-regularity  under distinct intersection arrays. In recent years, a particular subclass of these graphs, those satisfying the so-called 2-Y-homogeneous condition, has garnered increasing attention due to its rich connections with combinatorial design theory and the representation theory of Terwilliger algebras. In this talk, we will examine the key structural conditions that characterize 2-Y-homogeneous DBRGs. We will survey recent progress in their classification under various combinatorial constraints, highlighting both known results and open problems.

Title:The first-order logic of graphs

Abstract:Over the last ten years, many wonderful connections have been established between structural graph theory, computational complexity, and finite model theory. We give an overview of this area, focusing on recent progress towards understanding the "stable" case. We do not assume any familiarity with first-order logic

Title:Power sum expansions for the Kromatic symmetric function

Abstract:The Kromatic symmetric function was introduced by Crew, Pechenik, and Spirkl (2023) as a K-analogue of Stanley's chromatic symmetric function. While the chromatic symmetric function encodes proper colorings of a graph (where each vertex gets a color and adjacent vertices get different colors), the Kromatic symmetric function encodes proper set colorings (where each vertex gets a nonempty set of colors and adjacent vertices get non-overlapping color sets). The expansion of the chromatic symmetric function in the basis of power sum symmetric functions has several nice interpretations, including one in terms of source components of acyclic orientations, due to Bernardi and Nadeau (2020). We lift that expansion formula to give expansion formulas for the Kromatic symmetric function using a few different K-analogues of the power sum basis. Our expansions are based on Lyndon heaps, introduced by Lalonde (1995), which are representatives for certain equivalence classes of acyclic orientations on clan graphs (graphs formed from the original graph by removing vertices and adding extra copies of vertices).

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:30pm,

Title: A Sudoku Baranyai's Theorem

Abstract: Motivated by constructing higher dimensional Sudokus we generalize the famous Baranyai's theorem. Let$n=\prod_{i=1}^d a_i$. Suppose that an $n\times\dots \times n$ ($d$ times) array $L$ is partitioned into$n/a_1\times\dots\times n/a_d$ sub‐arrays (called blocks). Can we color the $n^d$ cells of $L$ with $n^{d21}$ colors so that each layer (obtained by fixing one coordinate) and each $n/a_1\times\dots\times n/a_d$block contains each color exactly once? We generalize the well‐know theorem of Baranyai to answer this queestion. The case $d=2 a_1=a_2=3$ corresponds to the usual Sudoku. We also provide finite fieldconstruction of various related objects. This is joint work with Sho Suda.

Title: A hereditary generalization of Nordhaus-Gaddum graphs

Abstract: This talk will be an expanded version of the speaker's CanaDAM talk, the abstract of which is as follows:

Nordhaus and Gaddum proved in 1956 that the sum of the chromatic number of a graph G and its complement is at most |G| + 1. The Nordhaus-Gaddum graphs are the class of graphs satisfying this inequality with equality, and are well-understood. In this paper we consider a hereditary generalization: graphs G for which all induced subgraphs H of G satisfy that the sum of the chromatic numbers of H and its complement are at least |H|. We characterize the forbidden induced subgraphs of this class and find its intersection with a number of common classes, including line graphs. We also discuss chi-boundedness and algorithmic results.