Events

Title: Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth, Part II

Abstract: I will present a recent max-flow min-cut type result for graphs of bounded treewidth. Multicommodity flow is a generalization of the well known s-t flow problem, where we are given multiple source-sink pairs and goal is to maximize the total flow. A natural upper bound on the value of total flow is the value of the minimum multicut : the minimum total capacity of edges that need to be removed in order to disconnect all the source-sink pairs. We will show that given a treewidth-r graph, there exists a (fractional) multi-commodity flow of value F, and a multicut of capacity C such that F ≤ C ≤ O(log r)·F.

Title: Kemeny’s constant for random walks on graphs

Abstract: Kemeny's constant, a fundamental parameter in the theory of Markov chains, has recently received significant attention within the graph theory community. Originally defined for a discrete, finite, time-homogeneous, and irreducible Markov chain based on its stationary vector and mean first passage times, Kemeny's constant finds special relevance in the study of random walks on graphs.

Title: Forest polynomials and harmonics for the ideal of quasisymmetric polynomials

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

Abstract: The type A coinvariant algebra, obtained by quotienting the polynomial ring by the ideal of positive degree symmetric polynomials, is a rich and active object of study. A distinguished basis for this quotient is given by Schubert polynomials. There is a dual to this story involving degree polynomials studied in depth by Postnikov-Stanley who shed light on their combinatorics. 

Title: Fast Combinatorial Algorithms for Efficient Sortation

Abstract: Modern parcel logistic networks are designed to ship demand between given origin, destination pairs of nodes in an underlying directed network. Efficiency dictates that volume needs to be consolidated at intermediate nodes in typical hub-and-spoke fashion. In practice, such consolidation requires parcel-sortation. In this work, we propose a mathematical model for the physical requirements, and limitations of parcel sortation.

Title: A Simple Sparsification Algorithm for Maximum Matching with Applications to Graph Streams 

Abstract: In this talk, we present a simple algorithm that reduces approximating the maximum weight matching problem in arbitrary graphs to few adaptively chosen instances of the same problem on sparse graphs.

Title: Higher-order correlation inequalities for random spanning trees

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

Abstract: The connection between enumerating spanning trees of a graph and the theory of (linear) electrical networks goes all the way back to Kirchhoff's 1847 paper. It is physically sensible that if one increases the conductance of one wire in an electrical network, then the overall conductance of the network can not decrease. This corresponds to the less obvious fact that any two distinct edges are non-positively correlated, when one chooses a random spanning tree. Covariance is the 2-point "Ursell function'', and expectation is the 1-point Ursell function. For any subset of edges there is an associated Ursell function, and these are related to occupation probabilities by Möbius inversion. I will discuss some situations in which the signs of these Ursell functions can be predicted, yielding higher-order correlation inequalities for random spanning trees.

Title: Chromatic Number of Random Signed Graphs

Abstract: A signed graph is a graph where edges are labelled {+1,-1}. A signed colouring in 2k colours maps the vertices of a signed graph to {-k,...,-1,1,...,k}, such that neighbours joined by a positive edge do not share the same colour, and those joined by a negative edge do not share opposite colours. It is a classical result that the chromatic number of a G(n,p) Erdos-Renyi random graph is asymptotically almost surely n/(2log_b(n)), where p is constant and b=1/(1-p). We extend the method used there to prove that the chromatic number of a G(n,p,q) random signed graph, where q is the probability that an edge is labelled -1, is also a.a.s. n/(2log_b(n)), if p is constant and q=o(1).

Title: Average plane-size

Abstract: In 1941, Eberhard Melchior proved that, given any finite set of points in the plane, not all on a single line, the average length of a spanned line is at most three.

Title: Graphs that Admit Orthogonal Matrices

Abstract: Given a simple graph $G=(\{1,\ldots, n},E), we consider the class $S(G)$ of real symmetric $n \times n$ matrices $A=[a_{ij}]$ such that for $i\neq j$, $a_{ij}\neq 0$ iff $ij \in E$. Under the umbrella of the inverse eigenvalue problem for graphs (IEPG), $q(G)$ - known as the minimum number of distinct eigenvalues of $G$ - has emerged as one of the most well-studied parameters of the IEPG. Naturally, characterizing graphs $G$ for which $q(G) \leq, =, \geq k$ is an important step for studying the IEPG.

Title: Snake decompositions of lattice path matroids

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

Abstract: We study Ehrhart theory of lattice path matroid polytopes motivated by a conjecture by De Loera, Haws and Köppe. More specifically, we aim to understand the h*-vector of this family of matroid polytopes. To do so, we subdivide them into smaller matroid polytopes such that each piece is a snake, which are matroids such that their matroid polytope coincides with the order polytope of a fence poset.