Events

Title: A new formula for the symmetric Macdonald polynomials via the ASEP and TAZRP

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

Abstract: In this talk, I will describe some recently discovered connections between one-dimensional interacting particle models (the ASEP and the TAZRP) and Macdonald polynomials and show the combinatorial objects that make these connections explicit. I will give a new compact tableau formula for the symmetric Macdonald polynomials $P_{\lambda}(X;q,t)$ in terms of a queue inversion statistic on certain sorted non-attacking tableaux. The nonsymmetric components of our formula specialize to the probabilities of the asymmetric simple exclusion process (ASEP) on a circle; moreover, the queue inversion statistic is naturally related to the dynamics of the ASEP. The new formula arises from the plethystic correspondence between the classical and modified Macdonald polynomials, which is closely related to fusion in the setting of integrable systems which connects the ASEP to the TAZRP.

Title: Oracle separation of QMA and QCMA with bounded adaptivity

Abstract: It is a long-standing open problem in quantum complexity theory whether the two possible quantum analogs of NP are equivalent. QMA is defined as the class of decision problems that are solvable by a polynomial-time quantum algorithm that has access to a polynomial-sized quantum proof, whereas QCMA is the class of decision problems that are solvable by a polynomial-time quantum algorithm that only has access to the polynomial-sized classical proof. In other words, the QMA vs QCMA question asks: are quantum proofs more powerful than classical proofs?

Title: Quasi-graphic matroids

Abstract: I will discuss various matroids (cycle-matroid, lifted-graphic matroid, frame matroid, and quasi-graphic matroid) associated with a graph. I will mostly focus on quasi-graphic matroids and on older results and conjectures that are joint with Bert Gerards and Geoff Whittle.

Title: Lattice Paths Through ACSV

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

Abstract: Analytic combinatorics in several variables uses complex analytic results to find coefficients in the series expansions of meromorphic functions. Typically this is used to find asymptotics of sequences by examining their associated generating functions. In the 2000's Bousquet-Melou (and others) used the kernel method, introduced in the late 60s and 70s, to find generating function expressions (in terms of certain multivariate rational functions) for certain kinds of walks in restricted regions. In particular Melczer and Mishna found asymptotics for these restricted walks when the step sets are symmetric in every axis.

Title: Bridging the gap between Linear and Integer Programming

Abstract: Informally, an Integer Program is obtained from a Linear Program by adding the condition that some variables be restricted to be integer. What kind of other restrictions lead to interesting classes of optimization problems? One such class of problems is obtained by restricting the variables in a Linear Program to be dyadic rationals, i.e. rationals where the denominator is a power of two. These problems borrow features from both Linear Programming and Integer Programming. Notably, they can be solved in polynomial time, but optimal solutions may have large support.

Title: New strongly regular graphs from optimal line packings

Abstract: In this talk, we'll explore several new constructions of strongly regular graphs. Specifically, we will show how some known optimal line packings can be coerced into generating new families of SRGs. We will also introduce a new construction of optimal line packings, yielding additional infinite families of SRGs.

Title: Analytic Methods and Combinatorial Plants

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

Abstract: In this talk, I will present the results of my masters thesis. I examine three applications of analytic methods to problems in combinatorics. By coincidence, each problem involves a combinatorial structure named for a plant--AVL trees, cactus graphs, and sunflowers--which we refer to collectively as combinatorial plants.

Title: Abelian covers of association schemes with applications to SIC-POVM

Abstract: Godsil and Hensel (1992) developed a theory of abelian covers of complete graphs to construct antipodal distance-regular graphs of diameter 3. More recently, Coutinho, Godsil, Shirazi and Zhan (2016) showed that equiangular tight frames can be constructed from covers of complete graphs in terms of cyclic groups of prime order. In this talk, we introduce covers of (not necessarily symmetric) association scheme of d classes in terms of an (not necessarily cyclic) abelian group G of order d.

Title: Lorentzian polynomials

Abstract: Lorentzian (aka completely log-concave) polynomials were recently developed by Brändén-Huh and Anari-Liu-Oveis Gharan-Vinzant to settle Mason's conjectures on the log-concavity of the number of size-k independent sets of a matroid. In this talk, we will define these polynomials and sketch the proof of these conjectures. Along the way we will also state other results which will demonstrate the very strong connection between matroids and Lorentzian polynomials.

Title: Deza graphs and vertex connectivity

Abstract: A k-regular graph on v vertices is called a Deza graph with parameters (v, k, b, a), b ≥ a if the number of common neighbors of any two distinct vertices takes two values: a or b. A Deza graph is called a strictly Deza graph if it has diameter 2 and is not strongly regular.

In this talk we will discuss the enumeration of strictly Deza graphs and the enumeration of special subclass of strictly Deza graphs called divisible design graphs. We will also describe the constructions of divisible design graphs found during the enumeration.