Please email any errors or updates to our website support/editor.
PDF files require Adobe Acrobat Reader.
Monday, July 13, 2020 — 11:30 AM EDT
Title: On the flip graph on perfect matchings of complete graphs and sign reversal graphs
| Speaker: | Sebastian Cioaba |
| Affiliation: | University of Delaware |
| Zoom: | Contact Soffia Arnadottir |
Abstract:
In this talk, we study the flip graph on the perfect matchings of a complete graph of even order. We investigate its combinatorial and spectral properties including connections to the signed reversal graph and we improve a previous upper bound on its chromatic number.
Thursday, July 16, 2020 — 2:30 PM EDT
Title: Dynamics of plane partitions
| Speaker: | Oliver Pechenik |
| Affiliation: | University of Waterloo |
| Zoom: | Contact Karen Yeats |
Abstract:
Consider a plane partition P in an a X b X c box. The rowmotion operator sends P to the plane partition generated by the minimal elements of its complement. We show rowmotion resonates with frequency a+b+c-1, in the sense that each orbit size shares a prime divisor with a+b+c-1. This confirms a 1995 conjecture of Peter Cameron and Dmitri Fon-Der-Flaass. (Based on joint works with Kevin Dilks & Jessica Striker and with Becky Patrias.)
Friday, July 17, 2020 — 1:30 PM EDT
Title: Two unsolved problems: Birkhoff--von Neumann graphs and PM-compact graphs
| Speaker: | Nishad Kothari |
| Affiliation: | CSE Department, Indian Institute of Technology Madras |
| Zoom: | Contact Sharat Ibrahimpur |
Abstract:
A well-studied object in combinatorial optimization is the {\it perfect matching polytope} $\mathcal{PMP}(G)$ of a graph $G$ --- the convex hull of the incidence vectors of all perfect matchings of $G$. A graph $G$ is {\it Birkhoff--von Neumann} if $\mathcal{PMP}(G)$ is characterized solely by non-negativity and degree constraints, and $G$ is {\it PM-compact} if the combinatorial diameter of $\mathcal{PMP}(G)$ equals one.
Friday, July 17, 2020 — 3:30 PM EDT
Title: Point Location and Active Learning - Learning Halfspaces Almost Optimally
| Speaker: | Shachar Lovett |
| Affiliation: | UC San Diego |
| Zoom: | Please email Emma Watson |
Abstract:
The point location problem is a central problem in computational geometry. It asks, given a known partition of R^d by n hyperplanes, and an unknown input point, to find the cell in the partition to which the input point belongs. The access to the input is via linear queries. A linear query is specified by an hyperplane, and the result of the query is which side of the hyperplane the input point lies in.