Events

Title: A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length - Part 1

Abstract: It is well known that the proof of some prominent results in mathematics took a very long time --- decades and even centuries. The first proof of the Micali-Vazirani (MV) algorithm, for finding a maximum cardinality matching in general graphs, was recently completed --- over four decades after the publication of the algorithm (1980). MV is still the most efficient known algorithm for the problem. In contrast, spectacular progress in the field of combinatorial optimization has led to improved running times for most other fundamental problems in the last three decades, including bipartite matching and max-flow.

The new ideas contained in the MV algorithm and its proof remain largely unknown, and hence unexplored, for use elsewhere.

The purpose of this two-talk-sequence is to rectify that shortcoming.

Title: Introducing the interval poset associahedron

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

Abstract: Given a permutation, we define its interval poset to be the set of all intervals ordered by inclusion. In this framework, a 'tube' is a convex connected subset, while a 'tubing' denotes a collection of tubes, that are pairwise either nested or disjoint. The interval poset associahedron is a polytope, whose faces correspond to proper tubes and whose vertices correspond to maximal tubings of the interval poset of a given permutation.

If we start with a simple permutation, the resulting interval poset associahedron will be isomorphic to the permutahedron. And if we consider inverse permutations, it turns out, that they yield identical associahedra.

If there is time, I will discuss another order on permutations, the Bruhat order, and compare it to the permutahedron.

Title: A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length - Part 2

Abstract: It is well known that the proof of some prominent results in mathematics took a very long time --- decades and even centuries. The first proof of the Micali-Vazirani (MV) algorithm, for finding a maximum cardinality matching in general graphs, was recently completed --- over four decades after the publication of the algorithm (1980). MV is still the most efficient known algorithm for the problem. In contrast, spectacular progress in the field of combinatorial optimization has led to improved running times for most other fundamental problems in the last three decades, including bipartite matching and max-flow.

The new ideas contained in the MV algorithm and its proof remain largely unknown, and hence unexplored, for use elsewhere.

The purpose of this two-talk-sequence is to rectify that shortcoming.

Title: Infinite matroids on lattices

Abstract: There are at least two well-studied ways to extend matroids to more general objects - one can allow the ground set to be infinite, or instead define the concept of independence on a lattice other than a set lattice. I will discuss some nice ideas that arise when combining these two generalizations. This is joint work with Andrew Fulcher.

Title: Which graphs are determined by their total numbers of walks?

Abstract: Walks and closed-walks are ubiquitous in graph theory, which capture lots of important structural information of graphs. In this talk, we shall consider the question in the title. The same question for closed walks is precisely the problem of spectral characterizations of graphs. We show that for most graphs, the number of walks determines the generalized spectrum of graphs and vice versa. Then the above question is equivalent to the problem of generalized spectral characterizations of graphs, a topic which has been studied extensively in recent years. Some simple criterions are provided for graphs G to be determined by their total number of walks, based on some recent results on the generalized spectral characterizations of graphs. Numerical results are also provided to illustrate the effectiveness of the proposed method. This is a joint work with Weifang Lv, Finjin Liu and Wei Wang.

Title: Multicommodity Flows and Cuts

Abstract: Flow and cut problems occupy a central place in discrete optimzation and algorithms. The well known max-flow min-cut theorem states that there exists a s-t flow of value d in a network if and only if the minimum capacity of edges whose removal separates s and t is at least d. In this talk, we will discuss a generalization of this problem to the multicommodity setting and study natural necessary and sufficient conditions for the existence of a feasible flow. We will discuss connections to approximation algorithms, metric embeddings and partitions, and survey some of the classical results, open problems and recent progress.

Title: Central Limit Theorems via Analytic Combinatorics in Several Variables

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

Abstract: Analytic combinatorics in several variables is a field of study focused on the derivation of limit behaviours of multivariate sequences. In this talk, I will describe a local central limit theorem and its applications to a variety of examples. Included in these examples will be a family of permutations with restricted cycles, integer compositions with tracked summands and n-colour compositions with tracked summands. The proof of this new, automated, local central limit theorem will also be briefly discussed, using techniques from the theory of analytic combinatorics in several variables. I will also provide background for proving central limit theorems probabilistically.

Title: Recent Progresses on Correlation Clustering

Abstract: Correlation Clustering is one of the most well-studied graph clustering problems. The input is a complete graph where each edge is labeled either "+" or "-", and the goal is to partition the vertex set into (an arbitrary number of) clusters to minimize (the number of + edges between different clusters) + (the number of - edges within the same cluster). Until recently, the best polynomial-time approximation ratio was 2.06, nearly matching the integrality gap of 2 for the standard LP relaxation. Since 2022, we have bypassed this barrier and progressively improved the approximation ratio, with the current ratio being 1.44. Based on a new relaxation inspired by the Sherali-Adams hierarchy, the algorithm introduces and combines several tools considered in different contexts, including "local to global correlation rounding" and "combinatorial preclusering". In this talk, I will describe the current algorithm as well as how it has been inspired by various viewpoints. Joint work with Nairen Cao, Vincent Cohen-Addad, Shi Li, Alantha Newman, and Lukas Vogl.

Title: A general theorem in spectral extremal graph theory

Abstract: The extremal graphs $\mathrm{EX}(n,\mathcal F)$ and spectral extremal graphs $\mathrm{SPEX}(n,\mathcal F)$ are the sets of graphs on $n$ vertices with maximum number of edges and maximum spectral radius, respectively, with no subgraph in $\mathcal F$. We prove a general theorem which allows us to characterize the spectral extremal graphs for a wide range of forbidden families $\mathcal F$ and implies several new and existing results. In particular, whenever $\mathrm{EX}(n,\mathcal F)$ contains the complete bipartite graph $K_{k,n-k}$ (or certain similar graphs) then $\mathrm{SPEX}(n,\mathcal F)$ contains the same graph when $n$ is sufficiently large. We prove a similar theorem which relates $\mathrm{SPEX}(n,\mathcal F)$ and $\mathrm{SPEX}_\alpha(n,\mathcal F)$, the set of $\mathcal F$-free graphs which maximize the spectral radius of the matrix $A_\alpha=\alpha D+(1-\alpha)A$, where $A$ is the adjacency matrix and $D$ is the diagonal degree matrix.

Title: Rate-distortion theory for quantum data compression

Abstract: Quantum data compression is a fundamental quantum information processing task, where the sender compresses many copies of a given quantum state into the smallest possible storage space before transmitting it to the receiver. Among various quantum data compression setups and analyses, the trade-off between the efficiency (rate) and the error of the compression has been investigated using the framework of quantum rate-distortion theory, in which a small error is tolerated to improve the rate. In this talk, adopting the quantum rate-distortion theory, we reveal the optimal rate-error trade-off of quantum data compression with and without the assistance of quantum entanglement. Moreover, we generalize these results to figure out the full rate region where both the communication and entanglement rates vary. Thus, we successfully obtain a complete form of the rate-distortion theory of quantum data compression with entanglement.