Events

Title: New Characterizations of Distance-Biregular Graphs

Abstract: Fiol, Garriga, and Yebra introduced the notion of pseudo-distance-regular vertices, and were able to use this notion to come up with a characterization of when a graph is distance-regular. Subsequently, Fiol and Garriga were able to use pseudo-distance-regular vertices and a bound on the excess of a vertex to come up with another characterization of distance-regular graphs. We will present an overview of their results, as well as recent extensions to distance-biregular graphs.

Title: High-Rank Matroids and Unavoidable Flats

Abstract: We discuss a variety of questions and results pertaining to conjectures of Geelen from 2021 on the unavoidable flats in matroids of sufficiently high rank. We will also explore the differences in how such questions are posed for various classes of matroids, why such differences are necessary, and how they could potentially be reconciled. A result for the class of binary matroids and an outline of its proof will be discussed in detail. Joint work with Jim Geelen.

Title: Strongly regular graphs with a regular point 

Abstract:  Arising from Hoffman and Singleton's study of Moore graphs, strongly regular graphs play an important role in algebraic graph theory. Strongly regular graphs can be construct from geometric objects, such as generalized quadrangles and certain geometric properties, such as having a regular point, can be studied in the context of graphs.

Title: Thresholds

Abstract: Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is never far from its "expectation-threshold," which is a natural (and often easy to calculate) lower bound on the threshold. In this talk, I will present recent progress on this topic. Based on joint work with Huy Tuan Pham.

Title: Non-realizability of polytopes via linear programming

Abstract: A classical question in polytope theory is whether an abstract polytope can be realized as a concrete convex object. Beyond dimension 3, there seems to be no concise answer to this question in general. In specific instances, answering the question in the negative is often done via “final polynomials” introduced by Bokowski and Sturmfels. This method involves finding a polynomial which, based on the structure of a polytope if realizable, must be simultaneously zero and positive, a clear contradiction.

Title: Stochastic Knapsack Problem

Abstract: The classical NP-hard Knapsack problem takes as input a set of items with some fixed values and weights. The goal is to compute a subset of items of maximum total value, subject to the constraint that the total weight of these elements is less than or equal to a given limit. In this talk we will review a paper by Dean, Goemans and Vondrák, in which an stochastic variation of this problem is considered. 

Title: Bipartite Matching in Almost-Linear Time and More

Abstract:  This talk will present an algorithm that computes maximum bipartite matchings in m^{1 + o(1)} time, and discuss its connections with optimization, graph algorithms, and data structures.

Title: Quasisymmetric functions,  descent sets, immaculate tableaux, and 0-Hecke modules

Abstract:

The first half of this talk will be expository and devoted to a discussion of (quasi)symmetric functions and tableaux.

We define new families of quasisymmetric functions, in particular the new basis of row-strict dual immaculate functions, with an associated cyclic, indecomposable 0-Hecke algebra module. Our row-strict immaculate functions are related to the dual immaculate functions of Berg-Bergeron-Saliola-Serrano-Zabrocki (2014-15) by the involution \psi on the ring Qsym of quasisymmetric functions. We uncover the remarkable properties of the immaculate Hecke poset induced by the 0-Hecke action on standard immaculate tableaux, revealing other submodules and quotient modules, often cyclic and indecomposable.

Title: A brief introduction to lattice-based cryptography

Abstract: A brief introduction to lattice-based cryptography, one of the leading candidates for building quantum-resistant cryptosystems.

Title: To be annouced.

Abstract: To be announced.