Events

Title: Refuting semirandom CSPs via spectral graph theory techniques

Abstract:

: In this talk, we will consider recent spectral techniques, developed by [HKM23] and [GKM22], for combinatorial and algorithmic problems. We shall focus, in particular, on designing algorithms for refuting semirandom instances of constraint satisfaction problems. The main component of the talk is a reduction to studying spectral properties of so-called "Kikuchi graphs" corresponding to a system of homogeneous degree-q multilinear polynomials.

No prerequisites in spectral graph theory beyond basic linear algebra are assumed.

[HKM23]: A simple and sharper proof of the hypergraph Moore bound

[GKM22]: Algorithms and Certificates for Boolean CSP Refutation: "Smoothed is no harder than Random"

Title:The external activity complex of a pair of matroids

Abstract: In 2016, Ardila and Boocher were investigating the variety obtained by taking the closure of a linear space within A^n in its compactification (P^1)^n; later work named this the "matroid Schubert variety". Its Gröbner degenerations led them to define, and study the commutative algebra of, the _external activity complex_ of a matroid. If the matroid is on n elements, this is a complex on 2n vertices whose facets encode the external activity of bases.

In recent work with Andy Berget on Speyer's g-invariant, we required a generalisation of the definition of external activity where the input was a pair of matroids on the same ground set. We generalise many of the results of Ardila--Boocher to this setting. Time permitting, I'll also present the tropical intersection theory machinery we use to understand the external activity complex of a pair.

For those who attended my talk at this year's CAAC on this paper, the content of the present talk is meant to be complementary.

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: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: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: 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: Almost Tight Additive Guarantees for k-Edge-Connectivity

Abstract: We consider the k-edge-connected spanning subgraph (k-ECSS) problem, where we are given an undirected graph G = (V, E) with nonnegative edge costs, and the goal is to find a minimum-cost subgraph H of G that is k-edge-connected; that is, there exist at least k edge-disjoint paths between every pair of vertices in H.

For even k, we present a polynomial-time algorithm that computes a (k−2)-edge-connected subgraph whose cost is at most that of the natural LP relaxation of k-ECSS. I will try to present an overview of our algorithm and analysis, which is based on the iterative rounding technique.

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: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: Fault Tolerant Routing and High Dimensional Expanders

Abstract: We will go over some recent results about fault tolerant routing from Bafna, Minzer, Vyas. Two parallel series of works from the last few years from Bafna, Lifshitz, Minzer, Vyas as well as Dikstein, Dinur, Lubotzky has led to size efficient PCPs by using high dimensional expanders. We will comment on the context for these works, and briefly go over some high level ideas. Then, we will talk about an application to fault tolerant rounding. The goal in this problem is to design a sparse network supporting efficient fault tolerant interactions between all pairs of nodes. Using the size efficient PCP construction, Bafna and Minzer gave a construction of constant degree networks with efficient protocols that tolerate a constant fraction of adversarial edge faults.