1/17/22 through 1/30/22

Graph Theory and Combinatorics Seminar: Almost k-Covers of Grids

Alon and Furedi determined the minimum number of affine hyperplanes needed to cover all but one vertex of an $n$-cube. We extend this question to the case where all vertices must be covered at least k times, except for one which is not covered at all. Using the Punctured Combinatorial Nullstellensatz of Ball and Serra, we solve the problem completely for $k=3$ and establish a nontrivial lower bound when k>3. Time permitting, we will also discuss this problem for more general grids, including an exact solution for k=2.

Joint work with Hao Huang.

Special Colloquium/Candidate Presentation: Non-stationary difference equation for q-Virasoro algebra

Abstract: Conformal blocks of q,t-deformed Virasoro and W-algebras are important special functions in representation theory with applications in geometry and physics. In the Nekrasov-Shatashvili limit t -> 1, whenever one of the representations is degenerate then conformal block satisfies a difference equation with respect to the coordinate associated with that degenerate representation. This is a stationary Schrodinger equation for an appropriate relativistic quantum integrable system. It is expected that generalization to generic t <> 1 is a non-stationary Schrodinger equation where t parametrizes shift in time. In this paper we make the non-stationary equation explicit for the q,t-Virasoro block with one degenerate and four generic Verma modules, and prove it when three modules out of five are degenerate, using occasional relation to Macdonald polynomials. 

Special Colloquium/Candidate Presentation: Invasion and fixation in structured populations

Abstract: In evolving populations, mutant traits can establish colonies through a combination of selection and genetic drift. A common measure of the evolutionary success of such a trait is its fixation probability, which quantifies how likely a mutant is to invade and replace the resident type. In this talk, I will discuss several existing approaches to calculating fixation probabilities, as well as the difficulties that arise in computing them in spatially-heterogeneous populations. This leads naturally to recent work on formal mathematical models of evolving populations with arbitrary population structure. I will conclude with a general result on fixation probabilities within this class of models, which both recovers many known findings and allows for new extensions.

The research of Dr. McAvoy is in Evolutionary Game Theory and Stochastic Processes, with interests in stochastic evolution, learning in populations and mutation-selection dynamics. Dr. McAvoy graduated from the University of British Columbia in 2016 with a PhD in mathematics, then held a postdoctoral position at Harvard University and currently is a Simons Postdoctoral Fellow at the University of Pennsylvania.

Special Colloquium/Candidate Presentation: Mathematical approaches to biodiversity conservation: some recent developments and challenges in phylogenetic diversity research

Abstract: Facing a major extinction crisis and constrained resources, conservation planning often involves difficult choices about which species to protect. Phylogenetic trees, i.e., leaf-labeled directed acyclic graphs, play an important role in this regard as they can be used to estimate how much “evolutionary heritage" is captured by each species and thus may be lost due to the current high rates of species extinction. Mathematically, this is formalized by the concepts of phylogenetic diversity (PD), a metric quantifying the biodiversity of sets of species based on their evolutionary relatedness, and phylogenetic diversity indices, measures that quantify the importance of species to overall biodiversity and provide prioritization criteria for conservation decisions.

In this talk, I will give a general introduction to phylogenetics and its use in biodiversity conservation. In particular, I will define the concept of phylogenetic diversity and introduce the Fair Proportion (FP) index, a popular PD index. I will then discuss two recent developments and challenges arising in conservation phylogenetics. First, I will consider the scenario of gene and species tree discordance, a scenario where phylogenetic trees obtained from individual genes differ from each other and the species tree, and analyze its effects on phylogenetic diversity conservation. Using the probabilistic multispecies coalescent model, I will show how prioritization decisions based on the FP index are affected by the phenomenon of gene and species tree discordance. Second, I will discuss the challenge of non-tree-like evolution and present some recent approaches towards defining and optimizing variants of PD on phylogenetic networks. In particular, I will explore the computational complexity of determining the maximum PD score over all subsets of species of fixed size under these variants and for different types of phylogenetic networks.

Special Colloquium/Candidate Presentation: Regularity lemma: discrete and continuous perspectives

Abstract: Szemerédi's regularity lemma is a game-changer in extremal combinatorics and provides a global perspective to study large combinatorial objects. It has connections to number theory, discrete geometry, and theoretical computer science. One of its classical applications, the removal lemma, is the essence for many property testing problems, an active field in theoretical computer science. Unfortunately, the bound on the sample size from the regularity method typically is either not explicit or is enormous. For testing natural permutation properties, we show one can avoid the regularity proof and yield a tester with polynomial sample size. For graphs, we prove a stronger, "L_\infty'' version of the graph removal lemma, where we conjecture that the essence of this new removal lemma for cliques is indeed the regularity-type proof. The analytic interpretation of the regularity lemma also plays an important role in graph limits, a recently developed powerful theory in studying graphs from a continuous perspective. Based on graph limits, we developed a method combining with both analytic and spectral methods, to answer and make advances towards some famous conjectures on a common theme in extremal combinatorics: when does randomness give nearly optimal bounds?

These works are based on joint works with Jacob Fox, Dan Kral',  Jonathan Noel, Sergey Norin, and Jan Volec.

Special Colloquium/Candidate Presentation: Efficient learning algorithms through geometry, and applications in cancer research

Abstract:  In this talk, I will discuss how incorporating geometric information into classical learning algorithms can improve their performance. The main focus will be on optimal mass transport (OMT), which has evolved as a major method to analyze distributional data. In particular, I will show how embeddings can be used to build OMT-based classifiers, both in supervised and unsupervised learning settings. The proposed framework significantly reduces the computational effort and the required training data. Using OMT and other geometric data analysis tools, I will demonstrate applications in cancer research, focusing on the analysis of gene expression data and on protein dynamics.

Special Colloquium/Candidate Presentation: Combinatorial atlas for log-concave inequalities

Abstract: The study of log-concave inequalities for combinatorial objects have seen much progress in recent years. One such progress is the solution to the strongest form of Mason's conjecture (independently by Anari et. al. and Brándën-Huh). In the case of graphs, this says that the sequence $f_k$ of the number of forests of the graph with $k$ edges, form an ultra log-concave sequence. In this talk, we discuss an improved version of all these results, proved by using a new tool called the combinatorial atlas method. This is a joint work with Igor Pak. This talk is aimed at a general audience.

Special Colloquium/Candidate Presentation: A proof of the Erdős–Faber–Lovász conjecture and related problems

Abstract: The famous Erdős—Faber—Lovász conjecture states that the chromatic index of any linear hypergraph on n vertices is at most n. This long-standing conjecture was posed 50 years ago and Erdős considered it to be one of his favorite open problems. In this talk, I will briefly sketch a proof of this conjecture for every large n. If time permits, I will also talk about our solution to another problem of Erdős from 1977 about the chromatic index of hypergraphs with bounded codegree.  Joint work with D. Kang, T. Kelly, D. Kühn and D. Osthus.

Graph Theory and Combinatorics Seminar: Two conjectures on the spread of graphs

Given a graph G let lambda_1 and lambda_n be the maximum and minimum eigenvalues of its adjacency matrix and define the spread of G to be lambda_1 - lambda_n. In this talk we discuss solutions to a pair of 20-year-old conjectures of Gregory, Hershkowitz, and Kirkland regarding the spread of graphs.

We show that the spread conjecture is true for all sufficiently large n, and we prove an asymptotic version of the bipartite spread conjecture. Furthermore, we exhibit an infinite family of counterexamples to the bipartite spread conjecture which shows that our asymptotic solution is tight up to a multiplicative factor in the error term. This is joint work with Jane Breen, Alex Riasanovsky, and John Urschel.

Special Colloquium/Candidate Presentation: Gapped Ground State Phases of Quantum Lattice Models

Abstract: Quantum spin systems are many-body physical models where particles are bound to the sites of a lattice. These are widely used throughout condensed matter physics and quantum information theory, and are of particular interest in the classification of quantum phases of matter. By pinning down the properties of new exotic phases of matter, researchers have opened the door to developing new quantum technologies.

One of the fundamental quantitites for this classification is whether or not the Hamiltonian has a spectral gap above its ground state energy in the thermodynamic limit. Mathematically, the Hamiltonian is a self-adjoint operator and the set of possible energies is given by its spectrum, which is bounded from below. While the importance of the spectral gap is well known, very few methods exist for establishing if a model is gapped, and the majority of known results are for one-dimensional systems. Moreover, the existence of a non-vanishing gap is generically undecidable which makes it necessary to develop new techniques for estimating spectral gaps. In this talk, I will discuss my work proving non-vanishing spectral gaps for key quantum spin models, and developing new techniques for producing lower bound estimates on the gap. Two important models with longstanding spectral gap questions that I recently contributed progress to are the AKLT model on the hexagonal lattice, and Haldane's pseudo-potentials for the fractional quantum Hall effect. Once a gap has been proved, a natural next question is whether it is typical of a gapped phase. This can be positively answered by showing that the gap is robust in the presence of perturbations.

Ensuring the gap remains open in the presence of perturbations is also of interest, e.g., for the development of robust quantum memory. A second topic I will discuss is my research studying spectral gap stability.

GGD/GEAR/Quantum Topology Seminar: The k-local Cohomology Problem and the Complexity of Supersymmetric Systems

I will discuss various aspects on the interplay of supersymmetry, quantum computation, and computational topology. After introducing some basic elements of supersymmetric quantum mechanics and elements of quantum complexity theory, I will show that the determining the computational complexity of various problems in computational topology/cohomology amounts to determining the Hamiltonian complexity of supersymmetric systems. In particular, studying the k-local Hamiltonian problem for supersymmetric systems will lead us to define the problem “k-local cohomology” and I will show that its complexity lies somewhere between QMA_1 and QMA. This reveals that many problems in computational topology/cohomology are intrinsically quantum mechanical. No prior knowledge of supersymmetry or cohomology will be assumed.

Student Cluster Algebra Seminar: Cluster Exchange Pattern of the Lambda Length

Lambda length was introduced by R. Penner in the study of the decorated Teichmuller space. I will talk about how to construct the lambda length on the hyperbolic space and then talk about the cluster exchange relation holds in this space. Additionally, I will talk about this also holds on the surface with orbifolds.

Graduate Student Homotopy Theory Seminar: Organizational Meeting

This is the organizational meeting for this semester's homotopy theory seminar.