Events

Title: Finding and Counting k-cuts in Graphs

Abstract:

For an undirected graph with edge weights, a k-cut is a set of edges whose deletion breaks the graph into at least k connected components. How fast can we find a minimum-weight k-cut? And how many minimum k-cuts can a graph have? The two problems are closely linked. In 1996 Karger and Stein showed how to find a minimum k-cut in approximately n^{2k-2} time; their proof also bounded the number of minimum k-cuts by n^{2k-2}, using the probabilistic method.

Title: Various Maximum Nullities Associated with a Graph

Abstract:

Given a graph, we associate a collection of (typically symmetric) matrices S whose pattern of non-zero entries off of the main diagonal respects the edges in the graph. To this set, we let M denote the maximum possible nullity over all matrices in S. Depending on the choice of the set S, and the family of graphs considered, the parameter M often corresponds to an interesting combinatorial characteristic (planarity, connectivity, coverings, etc.) of the underlying graph.

Title: The growth of groups and algebras

Abstract:

We give an overview of the theory of growth functions for associative algebras and explain their significance when trying to understand algebras from a combinatorial point of view.  We then give a classification for which functions can occur as the growth function of a finitely generated associative algebra up to asymptotic equivalence. This is joint work with Efim Zelmanov.

Title: Fast simulation of planar Clifford circuits

Abstract:

Clifford circuits are a special family of quantum circuits that can be simulated on a classical computer in polynomial time using linear algebra. Recent work has shown that Clifford circuits composed of nearest-neighbor gates in planar geometries can solve certain linear algebra problems provably faster --as measured by circuit depth-- than classical computers.

Title: The Matchings Polynomial

Abstract:

A $k$-matching in a graph is a matching of size $k$, and $p(X,k)$ denotes the number of $k$-matchings in $X$.

The matching polynomial of a graph is a form of generating function for the sequence $(p(X,k))_{k\ge0}$.

If is closely related to the characteristic polynomial of a graph. I will discuss some of the many interesting properties of this polynomial, and some of the related open problems.

Title: The multispecies TAZRP and modified Macdonald polynomials

Abstract:

Recently, a formula for the symmetric Macdonald polynomials $P_{\lambda}(X;q,t)$ was given in terms of objects called multiline queues, which also compute probabilities of a statistical mechanics model called the multispecies asymmetric simple exclusion process (ASEP) on a ring. It is natural to ask whether the modified Macdonald polynomials $\widetilde{H}_{\lambda}(X;q,t)$ can be obtained using a combinatorial gadget for some other statistical mechanics model.

Title: Finding twin smooth integers for isogeny-based cryptography

Abstract:

Efficient and secure instantiations of cryptographic protocols require careful parameter selection. For the isogeny-based cryptographic protocol B-SIDH, a variant of the Supersingular-Isogeny Diffie Hellman (SIDH) key exchange, one needs to find two consecutive B-smooth integers of cryptographic size such that their sum is prime. The smaller the smoothness bound B is, the more efficient the protocol becomes. This talk discusses a sieving algorithm to find such twin smooth integers that uses solutions to the Prouhet-Tarry-Escott problem.

Title: Promotion and rowmotion – an ocean of notions

Abstract: 

Dynamical Algebraic Combinatorics studies objects important in algebraic combinatorics through the lens of dynamical actions. In this talk, we give a flavor of this field by investigating ever more general domains in which the actions of promotion on tableaux (or tableaux-like objects) and rowmotion on order ideals (or generalizations of order ideals) correspond. This is based on joint works with J. Bernstein, K. Dilks, O. Pechenik, C. Vorland, and N. Williams.

Title: Probabilistic Aspects of Voting, Intransitivity, and Manipulation

Abstract:

Marquis de Condorcet, a French philosopher, mathematician, and political scientist, studied mathematical aspects of voting in the eighteenth century. Condorcet was interested in studying voting rules as procedures for aggregating noisy signals and in the paradoxical nature of ranking  3 or more alternatives. We will begin with a quick survey of some of the main mathematical models, tools, and results in this theory and discuss some recent progress in the area. 

Title: Cospectral Vertices and Isospectral Reductions

Abstract:

Understanding cospectral vertices in graphs is fundamental to understanding what the spectrum of the adjacency matrix can tell us about a graph.  Furthermore, cospectral vertices are necessary in constructions of graphs exhibiting perfect quantum state transfer.  I will talk about how to recognize cospectral vertices via a tool from network dynamics: the isospectral reduction of a graph.  I will explore possible ways of getting new constructions of cospectral vertices by looking at isospectral reductions.