Georgia Institute of Technology College of Sciences

I will briefly survey the theory of matroids with coefficients, which was introduced by Andreas Dress and Walter Wenzel in the 1980s and refined by the speaker and Nathan Bowler in 2016. This theory provides a unification of vector subspaces, matroids, valuated matroids, and oriented matroids. Then I will outline an intriguing connection between Lorentzian polynomials, as defined by Petter Brändén and June Huh, and matroids with coefficients.  The second part of the talk represents ongoing joint work with June Huh, Mario Kummer, and Oliver Lorscheid.

Motivated by applications to group synchronization and quadratic assignment on random data, we study a general problem of Bayesian inference of an unknown “signal” belonging to a high-dimensional compact group, given noisy pairwise observations of a featurization of this signal.

We establish a quantitative comparison between the signal-observation mutual information in any such problem with that in a simpler model with linear observations, using interpolation methods. For group synchronization, our result proves a replica formula for the asymptotic mutual information and Bayes-optimal mean-squared error. Via analyses of this replica formula, we show that the conjectural phase transition threshold for computationally-efficient weak recovery of the signal is determined by a classification of the real-irreducible components of the observed group representation(s), and we fully characterize the information-theoretic limits of estimation in the example of angular/phase synchronization over SO(2)/U(1). For quadratic assignment, we study observations given by a kernel matrix of pairwise similarities and a randomly permuted and noisy counterpart, and we show in a bounded signal-to-noise regime that the asymptotic mutual information coincides with that in a Bayesian spiked model with i.i.d. signal prior.

This is based on joint work with Kaylee Yang and Zhou Fan.

A matroid $M$ is a pair $(E, \mathcal{I})$ where $E$ is a finite set, called the {\em ground set} of $M$, and $\mathcal{I}$ is a non-empty collection of subsets of $E$, called {\em independent sets} of $M$, such that (1) a subset of an independent set is independent; and (2) if $I$ and $J$ are independent sets with $|I| < |J|$, then exists $x \in J \backslash I$ such that $I \cup \{x\}$ is independent. 

A graph $G$ gives rise to a matroid $M(G)$ where the ground set is $E(G)$ and a subset of $E(G)$ is independent if it spans a forest. Another example is a matroid that comes from a matrix over a field $F$: the ground set $E$ is the set of all columns and a subset of $E$ is independent if it is linearly independent over $F$. 

Tutte's Wheel and Whirl Theorem and Seymour's Splitter Theorem are two well-known inductive tools for proving results for 3-connected graphs and matroids. In this talk, we will give a survey on induction theorems for various versions of 4-connected matroids and graphs.