Tuesday, 1/17
Organizational meeting
Time: 1:30-2:00
Location: WH 100E and Zoom https://binghamton.zoom.us/j/95302383985

Tuesday, 1/24
Title: Progress on Projective Rectangles
Speaker: Thomas Zaslavsky (Binghamton)
Time: 1:15-2:15
Location: WH 100E

A projective rectangle is like a projective plane, but narrower. Rigoberto Florez and I have been developing a theory. It's a big project. I will give background and some properties. I will not assume you know what a projective plane is.

Tuesday, 1/31
No seminar today.

Thursday, 2/2: Special lecture
Title: Matroids of Gain Signed Graphs
Speaker: Thomas Zaslavsky (Binghamton)
Time: 3:00-4:00 (EDT)
Location: WH-309 and the Matroid Union Zoom link https://gatech.zoom.us/j/8802082683

For standard affinographic hyperplane arrangements (a.k.a. deformations of the Type A root system arrangement or “braid” arrangement), integral gain graphs give a simpler method to compute the characteristic polynomial, a fundamental invariant. For more general affinographic arrangements (a.k.a. deformations of the Type B root system arrangement), one has to combine gains with signs. How to do this has been a puzzle. The obvious method is to put signs on top of gains. The right method is to put gains on top of signs. Laura Anderson, Ting Su, and I found out how to do this, constructing the natural matroid and the corresponding semimatroid, which latter gives the characteristic polynomial of these more general arrangements when the gain group is the additive group of integers. I will explain some of this. It does get complicated.

Tuesday, 2/7
No seminar today.

Tuesday, 2/14
No seminar today.

Tuesday, 2/21
No seminar today.

Tuesday, 2/28
Title: Current Research on a Weird Poset
Speakers: Michael Gottstein (Binghamton)
Time: 1:15-2:15
Location: WH 100E

Mike will tell us about his work on flat low-dimensional embedding of the simplicial complex of partial partitions.

Tuesday, 3/7
Title: Loose Elements in Some Matroids
Speaker: Jagdeep Singh + Thomas Zaslavsky (Binghamton)
Time: 1:15-2:15
Location: WH 100E

Jagdeep (& Tom) will tell us about loose and nearly loose points in a binary or ternary matroid. Knowledge of matroids will not be necessary.

Tuesday, 3/14
Postponed to next week due to threatening weather.

Tuesday, 3/21
Title: Apex Cographs
Speaker: Jagdeep Singh (Binghamton)
Time: 1:15-2:15
Location: WH 100E

A cograph is a graph that can be built from a vertex by repeated operations of disjoint union and complementation. An apex cograph is a graph that has a vertex $a$ such that deleting $a$ gives a cograph. There is a project to characterize apex cographs, by Vaidy Sivaraman, Tom Zaslavsky, and myself. I will report on it.

Tuesday, 3/28
Title: Cyclic Flats of Matroids and Examples of Why they are Useful
Speaker: Tara Fife (Queen Mary, University of London)
Time: 1:15-2:15
Location: WH 100E and Zoom https://binghamton.zoom.us/j/95302383985

A matroid is an abstract notion of independence derived from vector spaces, as well as from graphs. Matroids can be characterised in many different ways. Among these is via cyclic flats, that is, the flats of the matroid which are unions of cycles. I will review the definitions of matroids and of cyclic flats. I will explore various classes of matroids and see how cyclic flats were used to characterise them. I will present Joseph Bonin and Anna de Mier's work which characterises matroids via the lattice of cyclic flats. Lastly, we will see how cyclic flats are related to a certain structure used in viewing matroids from an algebraic-geometric perspective.

I am presenting two of my projects, one joint with James Oxley and the other with Felipe Rincon.

Tuesday, 4/11
Title: Classification of Distance Regular Graphs with Diameter $D=3$ and Fixed Eigenvalue
Speaker: Quaid Iqbal (Center for Combinatorics, Nankai University)
Time: 1:15-2:15
Location: WH 100E and Zoom https://binghamton.zoom.us/j/95302383985

A graph is distance regular if, for any two vertices $v$ and $w$ at distance $d$, the number of vertices at distance $j$ from $v$ and distance $k$ from $w$ depends only on $i$, $j$, and $k$. Distance-regular graphs have very nice eigenvalue properties (e.g., they have $d+1$ distinct eigenvalues) and are a lively topic in spectral graph theory. Distance-regular graphs with diameter 2, which are called strongly regular, have been important in the classification of finite groups.

Given a graph $\Gamma$, the distance-2 graph $\Gamma_2$ is the graph on the same vertices, in which vertices are adjacent if they have distance 2.

I consider the distance-regular graphs $\Gamma$ whose distance-$2$ graphs $\Gamma_2$ are strongly regular. If $\Gamma$ is bipartite, then its distance-$2$ graph is not connected. So, I am interested in the class of non-bipartite distance-regular graphs. First, I will show that the distance-$2$ graph of a non-bipartite distance-regular graph with diameter $3$ and eigenvalue $a_2-c_3$ is strongly regular, and then I will give several kinds of classification of non-bipartite distance-regular graphs with diameter $3$ and eigenvalue $a_2-c_3$ under various conditions, for example when the valency $k$ of $\Gamma$ is at most $2(a_1+1)$, $c_3\leq9$, $a_2\leq 7,$ $\tilde{c} \leq 26$ (where $\tilde{c}$ is the number of common neighbors between any two non-adjacent vertices) and $\theta_{min}(\Gamma) > -3$.

This is joint work with J.H. Koolen, Jongyook Park, and Masood Ur Rehman.

Tuesday, 4/18
Title: TBA
Speaker: Prairie Wentworth-Nice (Cornell)
Time: 1:15-2:15
Location: WH 100E

Tuesday, 4/25
Title: [Something about the Penrose polynomial of a graph and a bit of TFQT (topological quantum field theory)]
Speaker: Scott Baldridge (Lousiana State)
Time: 1:15-2:15
Location: WH 100E and Zoom https://binghamton.zoom.us/j/95302383985

Tuesday, 5/2
No seminar: today is officially Friday.

Tuesday, 8/23
Organizational meeting
Time: 2:00-2:30 (Note special time)
Location: WH 100E and Zoom https://binghamton.zoom.us/j/95302383985

Tuesday, 8/30
Title: What I'm Doing
Speakers: Stefan Viola, Tara Koskulitz, Jagdeep Singh (Binghamtons)
Time: 1:15-2:15
Location: WH 100E

Tuesday, 9/6
No seminar: it is “Monday”.

Tuesday, 9/13
Title: Perfectly Matchable Set Polynomials and an Application to Ehrhart Theory
Speaker: Robert Davis (Colgate)
Time: 1:15-2:15
Location: WH 100E

A subset S of vertices of a graph G is called a perfectly matchable set of G if the subgraph induced by S contains a perfect matching. The perfectly matchable set polynomial of G, first made explicit by Ohsugi and Tsuchiya, is the (ordinary) generating function p(G; z) for the number of perfectly matchable sets of G. I will compare p(G; z) to the classical matching polynomial and provide explicit recurrences for computing p(G; z) for an arbitrary (simple) graph. I will use these to compute the Ehrhart h*-polynomials for certain lattice polytopes, which was the original motivation for this work. Namely, I show that p(G; z) is the h*-polynomial for certain classes of stable set polytopes, whose vertices correspond to stable sets of G.

This is joint work with Florian Kohl.

Tuesday, 9/20
Title: From Cographs to 2-Cographs and Comatroids
Speaker: Jagdeep Singh (Binghamton)
Time: 1:15-2:15
Location: WH 100E

A graph all of whose connected induced subgraphs have a disconnected complement is called a cograph. Such graphs can be recursively built from a single vertex via complementation and disjoint union and, therefore, are called complement-reducible graphs as well. Another characterization of cographs is that they are precisely the graphs that do not have an induced path of length three. In this talk, I replace connectivity with 2-connectivity and consider this natural generalization, called 2-cographs, of the class of cographs. I will talk about the corresponding results for the class of 2-cographs and an analogue of cographs for matroids.

This is joint work with James Oxley.

Tuesday, 9/27
No seminar; it is New Year's Day (Rosh Hashonah).

Tuesday, 10/4
No seminar; it is Yom Kippur Eve.

Tuesday, 10/11
Title: Whitney Numbers
Speaker: Thomas Zaslavsky (Binghamton)
Time: 1:15-2:15
Location: WH 100E

For each finite group $G$ and each rank $n$ there is a Dowling lattice, a geometric lattice, $Q_n(G)$. The coefficients of the characteristic polynomial of this lattice are the Whitney numbers of the first kind of $Q_n(G)$, $w_i$ for $i=0,1,\ldots,n$. They depend only on $n$ and the order of the group, $|G|$. It is easy to see that $w_i(|G|)$ is a polynomial function of $|G|$. I will discuss the not-so-easy details, such as the degree and the coefficients in the polynomial $w_i(q)$, for an extensive generalization of the Dowling lattices that is obtained by using gain graphs. I will explain almost all of this in the talk.

Tuesday, 10/18
Title: Monotonic Linear Models
Speaker: Laura Anderson (Binghamton)
Time: 1:15-2:15
Location: WH 100E

I'll discuss new methods for data analysis related to psychological models.

The models in question are of the form $y=f(Ax)$, where $x$ is a vector of independent variables that cannot be measured, $y$ is a vector of data to be measured in an experiment, $A$ is a matrix given by the theory being tested, and $f$ is an unknown coordinate-wise increasing function. (The first part of the talk will explore how such a model arises.)

Assume that you have run the experiment and have a bunch of vectors $y$ of data. How do you characterize how well your data fits the model?

If one assumes $f$ to be the identity function, then the answer is elementary. This explains why people frequently make this assumption, even when it has no theoretical justification. Answering the question without making assumptions about the form of $f$ leads one into combinatorics. A particularly knotty issue is the question of error: how does one measure how far a data point $y$ is from satisfying combinatorial conditions? I'll discuss joint work with John Dunn addressing this question.

Tuesday, 10/25
Title: Inscribable Order Types
Speaker: Michael Dobbins (Binghamton)
Time: 1:15-2:15
Location: WH 329 (Note change of room.)

We call an order type of points in the plane “inscribable” if it can be realized by a point configuration where all extreme points are on a circle. I will show that every simple order type with either at most 2 interior points or at most 5 extreme points is inscribable. Then, I will present an uninscribable configuration with 3 interior and 6 extreme points, which we call the non-Pascal configuration. Then, I will construct an infinite family of minimally uninscribable order types using properties of Möbius transformations.

This is joint work with Seunghun Lee.

Tuesday, 11/1
Speaker: No speaker today.

Tuesday, 11/8
Speaker: No speaker today.
It's Election Day: vote (if a U.S. citizen).

Tuesday, 11/15
Title: 1-Skeleton Posets of Bruhat Interval Polytopes
Speaker: Christian Gaetz (Cornell)
Time: 1:15-2:15 (followed by an Algebra Seminar talk; see below)
Location: WH 100E

Bruhat interval polytopes are combinatorially interesting polytopes arising from total positivity and from certain toric varieties. I study the 1-skeleta of these polytopes, viewed as posets interpolating between weak order and Bruhat order. Interestingly, these posets turn out to be lattices and the polytopes, despite not necessarily being simple, have interesting h-vectors. I will give a criterion for determining when these polytopes are simple, or equivalently when generic torus orbit closures in Schubert varieties are smooth, solving a conjecture of Lee and Masuda.

Algebra Seminar
Title: Stable Characters from Permutation Patterns
Speaker: Christian Gaetz (Cornell)
Time: 2:50-3:50
Location: WH 100E

Christopher Ryba, Laura Pierson, and I study the expected value (and higher moments) of the number of occurrences of a fixed permutation pattern on conjugacy classes of the symmetric group $S_n$. We prove that this virtual character stabilizes as n grows, so that there is a single polynomial computing these moments on any conjugacy class of any symmetric group. Our proof appears to be the first application of partition algebras to the study of permutation patterns. I’ll also discuss partial progress towards a conjecture on when these virtual characters are genuine characters.

Tuesday, 11/22
Title: Random Currents and Continuity of Ising Model’s Spontaneous Magnetization
Speaker: Gang Zhou (Binghamton)
Time: 1:15-2:15
Location: WH 100E

I will present the paper “Random currents and continuity of Ising model’s spontaneous magnetization” by M. Aizenman, H. Duminil-Copin and V. Sidoravicius (2015).

In the paper they considered three-dimensional ferromagnetic Ising model. It is known that at the high temperature, the system is at disorder; at the low temperature, the system exhibits ferromagnetic order, or magnetization. They proved that at the critical temperature, the magnetization is continuous, which was a long standing conjecture.

A crucial technique is the so-called switching lemma. It establishes a bijection between undirected graphs generated by the random current representation. In many important papers this was used, including the ones helping Hugo Duminil-Copin to win a Fields medal in 2022. However this technique does not work for the other spin models, for example, XY model or most of the quantum models.

This is the same talk I gave at the analysis seminar, but for the people who could not attend it for various reasons.

Tuesday, 11/29
Title: A New Length Estimate for Curve-Shortening Flow and Low Regularity Initial Data
Speaker: Shiyi Ma (Binghamton)
Time: 1:15-3:30 (Note longer duration.)
Location: WH 329 (Note special room.)

Part 1: We want to understand how Jordan curves evolve by curve-shortening flow in $\mathbb{R}^2$. Short-time existence for smooth initial data has been proved by Gage and Hamilton. When we are trying to show that curve-shortening flow is able to smooth non-smooth initial data, one of the major obstacles is that analytic estimates are difficult to control when the lengths of any approximating sequence are unbounded. I will be discussing work by Joseph Lauer in which he introduces a geometric quantity, the $r$-multiplicity, that controls the length of a smooth curve as it evolves by curve-shortening flow. The length estimates we obtain are used to prove results about the level set flow in $\mathbb{R}^2$.

Part 2: I will show the smoothness of level set flow. If $K$ is locally connected, connected and compact, then the level set flow of $K$ either vanishes instantly, fattens instantly or instantly becomes a smooth closed curve. If the compact set in question is a Jordan curve γ, then γ instantly becomes either a smooth curve or an annular region with smooth boundary.

This talk will be the candidacy exam of Shiyi Ma. The examining committee consists of Michael Dobbins (chair), Thomas Zaslavsky, and Gang Zhou.

Tuesday, 12/6
Title:
Speaker:
Time: 1:15-2:15
Location: WH 100E

Friday, 7/1
Title: Geometry of Matroids and Hyperplane Arrangements
Speaker: Jaeho Shin (Korea Institute for Advanced Study)
Time: 3:30-4:30 p.m. Note special time
Location: WH 100E and Zoom https://binghamton.zoom.us/j/95302383985

There is a trinity relationship between hyperplane arrangements, matroids and convex polytopes. There are at least three different starting points to understand the relationship. In this talk, I will take a path from the hyperplane arrangements and explain as much as time allows.

Thursday, 7/14
Titles:
Part 1. Combinatorial Obstructions to the Lifting of Link Diagrams
Part 2. Cycling in Link Diagrams and Noneuclidean Oriented Matroids
Speaker: Tara Koskulitz (Binghamton)
Time: 1:00–3:15
Location: WH 100E

Part 1: Consider a line arrangement in $\mathbb{R}^3$. When we draw it in the plane, we draw an arrangement of lines together with some indication of the above-below relations at each point where two lines intersect. This realizable situation inspires the general definition of a link diagram: a pair consisting of a line arrangement in $\mathbb{R}^2$ with a function giving “above-below” relations at each intersection. We can then ask whether or not a general link diagram is liftable to an actual arrangement of lines in $\mathbb{R}^3$. I will be discussing work by Jürgen Richter-Gebert in which he introduces methods for using oriented matroids to solve these liftability problems.

Part 2: A particular type of obstruction to lifting occurs when the link diagram contains a nondegenerate cycle. In this case, the associated (partial) oriented matroid is noneuclidean.

This is Ms. Koskulitz's candidacy exam. All are invited. The examining committee consists of Laura Anderson (chair), Michael Dobbins, and Thomas Zaslavsky.

Wednesday, 7/20
Title: Mutations of Mystic Monoliths
Speaker: Christopher Eppolito (Binghamton)
Time: 1:00–3:15 (with a break)
Location: WH 100E

A Pythagorean hyperplane arrangement is determined by a configuration of reference points in affine space and a real gain graph. The combinatorics of such arrangements is thus related to both the geometry of these points and the combinatorics of the gain graph. Previous work in this area by T. Zaslavsky determined region-counting formulas for the configuration-generic Pythagorean arrangements, i.e., those with stable intersection pattern under perturbation of the reference points.

In recent work, I proved two results on Pythagorean hyperplane arrangements. The first theorem constructs the intersection pattern of arbitrary Pythagorean arrangements, from which region-counting formulas follow via T. Zaslavsky's thesis. The main tool is an auxiliary hyperplane arrangement in the real edge space of the graph which incorporates the geometry of a fixed set of reference points. The flats of this arrangement are in bijection with the possible intersection patterns. The second theorem is an extension result for configuration-generic arrangements. The main gadget here is a new operation on gain graphs. Fixing a gain graph, we use this operation to construct a finite set of spheres and hyperplanes in affine space which determine the locus of the extra points that result in a configuration-nongeneric arrangement.

This talk begins with an overview of my dissertation. Following this I discuss the results on Pythagorean arrangements in detail. I include many pictures (the true purpose of the talk).

This is Mr. Eppolito's dissertation defense. All are invited. The examining committee consists of Laura Anderson (co-advisor), Michael Dobbins, Leslie Lander (outside examiner), and Thomas Zaslavsky (chair and co-advisor).

Thursday, 7/21
Titles:
Part 1. Geometric Algebra for Matroids
Part 2. Foundation of a Matroid (brief summary)
Speaker: Stefan Viola (Binghamton)
Time: 1:00–3:00
Location: WH 100E

Part 1: In 1989 Dress and Wenzel showed that for any matroid $M$ on a finite set $E$, a certain abelian group $T_M^H$ (called the extended Tutte group of $M$) can be canonically associated with $M$. The extended Tutte group has several cryptomorphic characterizations, but I will focus only on the characterization given by the hyperplanes of $M$. I will show that the cross-ratio, which is an important tool in classical projective geometry, extends naturally to matroids via the theory of Tutte groups. I will give a non-realizability condition in terms of cross-ratios and a Tutte-group theoretic proof of Pappus's theorem.

This talk is based on the paper “On Combinatorial and Projective Geometry” by Andreas Dress and Walter Wenzel (1990).

Part 2 (will be a short summary): In 2020 Baker and Lorscheid introduced the foundation of a matroid, which is an algebraic invariant that classifies all realizations of the matroid up to rescaling. I will give a presentation for the foundation of a matroid in terms of generators and relations, where the generators are the universal cross-ratios of the matroid and all relations between universal cross-ratios are inherited from embedded minors having at most 7 elements.

This talk is based on the paper “Foundations of Matroids Part 1: Matroids without Large Uniform Minors” by Matthew Baker and Oliver Lorscheid (2020).

This is Mr. Viola's candidacy exam. All are invited. The examining committee consists of Laura Anderson (chair), Michael Dobbins, and Thomas Zaslavsky.

Tuesday, 1/25
Title: Organizational meeting
Speaker: Everyone and anyone
Time: 1:30-2:15 (Note special starting time.)
Location: WH 100E and Zoom https://binghamton.zoom.us/j/95302383985

Tuesday, 2/1
Title: Unimodular Triangulations of Sufficiently Large Dilations
Speaker: Gaku Liu (U. of Washington)
Time: 1:15-2:15
Location: WH 100E and Zoom https://binghamton.zoom.us/j/95302383985Dilations

An integral polytope is a polytope whose vertices have integer coordinates. A unimodular triangulation of an integral polytope in $\mathbb R^d$ is a triangulation in which all simplices are integral with volume $1/d!$. A classic result of Kempf, Mumford, and Waterman states that for every integral polytope $P$, there exists a positive integer $c$ such that $cP$ has a unimodular triangulation. I strengthen this result by showing that for every integral polytope $P$, there exists $c$ such that for every positive integer $c' \ge c$, $c'P$ admits a unimodular triangulation.

Tuesday, 2/8
Title: Open Problems
Speaker: Seunghun Lee et al. (Binghamton)
Time: 1:15-2:15
Location: WH 100E

Tuesday, 2/15
Title: Sweep Oriented Matroids
Speaker: Arnau Padrol (Institut de Mathématiques de Jussieu)
Time: 1:15-2:15
Location: WH 100E and Zoom https://binghamton.zoom.us/j/95302383985

A sweep of a point configuration is an ordered partition induced by a linear functional. The set of orderings obtained this way is highly structured: isomorphic to the face lattice of a convex polytope, the sweep polytope. In the plane, they were formalized and abstracted by Goodman and Pollack under the theory of allowable sequences of permutations, but a high dimensional generalization was missing. Mimicking the fact that sweep polytopes of point configurations are projections of permutahedra, we define sweep oriented matroids as strong maps of the braid oriented matroid. Allowable sequences are then the sweep oriented matroids of rank 2, and many of their properties extend to higher rank. I will present sweep oriented matroids, their connection with Dilworth truncations and the generalized Baues problem for cellular strings, and many open questions.

This is based on joint work with Eva Philippe.

Tuesday, 2/22
Title: A Dr. Strange Partial Ordering of Partial Partitions
Speaker: Mike Gottstein (Binghamton)
Time: 1:15-2:15
Location: WH 100E

I will introduce the poset of partial set partitions ordered by set inclusion, as opposed to the typical ordering by refinement. The goal is to see what the homology of this poset is. I will first argue by an elementary approach, and then introduce the concept of shellability to see how this gives the same solution only in a much wider scope.

Tuesday, 3/1
Title: A New Matroid Lift Construction and an Application to Gain Graphs
Speaker: Zach Walsh (Louisiana State)
Time: 1:15-2:15
Location: WH 100E and Zoom https://binghamton.zoom.us/j/95302383985

Crapo constructs an elementary lift of a matroid $M$ from a linear class of circuits of $M$. I generalize by constructing a rank-$k$ lift of $M$ from a rank-$k$ matroid on the set of circuits of $M$. I conjecture that every lift of $M$ arises via this construction.

I apply this result to gain graphs, generalizing a construction of Zaslavsky. Given a graph $G$ with gains (edges labeled invertibly by a group), Zaslavsky’s lift matroid $K$ is an elementary lift of the graphic matroid $M(G)$ that respects the gains; specifically, the cycles of $G$ that are circuits of $K$ coincide with the cycles that have neutral gain. For $k \geq 2$, when does there exist a rank-$k$ lift of $M(G)$ that respects the gains? For abelian groups, I show that such a matroid exists if and only if the group is the additive group of a non-prime finite field.

Tuesday, 3/8
Title: The Inverse Kakeya Problem
Speaker: Michael Dobbins (Binghamton)
Time: 1:15-2:15
Location: WH 100E

I show that the largest convex body that can be placed inside a given convex body $Q$ in $\mathbb{R}^d$ in every orientation is the largest inscribed ball of $Q$. This is true for both largest volume and for largest surface area. Furthermore, the ball is the unique solution, except when maximizing the perimeter in the two-dimensional case.

This is joint work with Sergio Cabello and Otfried Cheong.

Tuesday, 3/15
No seminar; happy holiday!

Tuesday, 3/22
Title: Mix-Ups of Matrices and Graphs
Speaker: Thomas Zaslavsky (Binghamton)
Time: 1:15-2:15
Location: WH 100E

There are many kinds of graph, from simple graphs to complex unit gain graphs and including directed graphs, oriented graphs, signed graphs, mixed graphs, mixed-up graphs, and whatever. Each one has an adjacency matrix—or two or three—that describes the graph. I will survey what little I know about all those matrices and what people are studying about them.

Tuesday, 3/29
Title: Coloring Graphs and Their Complements
Speaker: Peter Maceli (Ithaca)
Time: 1:15-2:15
Location: WH 100E

Nordhaus and Gaddum showed that for any graph the sum of its chromatic number together with the chromatic number of its complement is at most one more than the number of vertices in the graph. The class of graphs which satisfy this upper bound with equality have long been understood; however, not much beyond this initial case is known in terms of characterizing graphs via the sum of complementary chromatic numbers. I will discuss how adopting a more structural approach to this general problem leads to an interesting method of graph decomposition, which in turn allows one to generalize and extend several previous results.

Tuesday, 4/5
Title: Higher Nerves and Applications
Speaker: Hai Long Dao (Kansas)
Time: 1:15-2:15
Location: WH 100E and Zoom https://binghamton.zoom.us/j/95302383985

I introduce a generalized version of the nerve complexes. I show that when applied to the Stanley–Reisner scheme of a simplicial complex, these higher nerve complexes can be used to compute important homological and combinatorial invariants such as depth, the $h$-vector, and the $f$-vector.

Tuesday, 4/12
Special Event
Discrete & Computational Geometry Day
In Memory of Eli Goodman and Ricky Pollack

Location: Zoom https://springer.zoom.us/j/6440052748
Time: 12:30-4:05

Program
12:30 Janos Pach (Renyi Institute): Welcome & Introduction
12:40 Andreas Holmsen (KAIST): An allowable feast
13:15 Micha Sharir (Tel Aviv University): Polynomial partitioning: The hammer and some (recent algorithmic) nails
13:50 Esther Ezra (Bar Ilan University): Recent developments on intersection searching
14:25 Xavier Goaoc (Loria, Nancy): Some questions on order types
15:00 Andrew Suk (UC San Diego): Unavoidable patterns in simple topological graphs
15:35 Sylvain Cappell (Courant Institute): Mesh matrices of graphs, of simplicial complexes and of matroids and the significance of their eigenvalues

Tuesday, 4/19
No seminar; it's “Monday”.

Tuesday, 4/26
Title: What I Remember From Saturday's Discrete Math Day at Colgate
Speaker: Thomas Zaslavsky (Binghamton)
Time: 1:15-2:15
Location: WH 100E

Very Abstract: There were interesting if weird talks, and I spoke with several people about various kinds of math.

Tuesday, 5/3
No seminar. We are closed for repairs until next week.

Tuesday, 5/10
Title: Projectivities in Simplicial Complexes and Balanced Spheres
Speaker: Seunghun Lee (Binghamton)
Time: 1:15-2:15
Location: This will be a remote talk. View in WH 100E and Zoom https://binghamton.zoom.us/j/95302383985

In his paper “Projectivities in simplicial complexes and colorings of simple polytopes”, Joswig studied the group of projectivities of a simplicial complex, and applied it to obtain equivalent conditions to define a balanced sphere, a d-dimensional simplicial sphere whose graph is properly (d+1)-colorable. Main results and proof ideas will be introduced in this talk.

Wednesday, 5/11 (Special day)
Talk 1: Homeomorphism Type of Combinatorial Grassmannian and Flag Manifold
Talk 2: Space of Flattenings of Spheres and Homotopy Type of Combinatorial Grassmannian Bundles
Speaker: Olakunle Abawonse (Binghamton)
Time: 3:30 p.m.
Location: WH 100E and on Zoom https://binghamton.zoom.us/j/95738127171

This is Mr. Abawonse's dissertation defense. The dissertation committee consists of Laura Anderson (chair), Michael Dobbins, Cary Malkiewich, and Florian Frick (outside examiner).

The dissertation defense is open to the public. All are invited to attend.

Abstract:

I will show that the geometric realizations of the poset of rank two oriented matroids and the poset of flags of rank one and rank two oriented matroids are homeomorphic to their corresponding Grassmannian counterparts. The proof will involve shellings of intervals in the two posets and face collapse on the boundary of a polytope.

I will also establish that the space of flattenings of some simplicial spheres, like a simplicial one-sphere and the join of the boundaries of a 1-simplex and a k-simplex, is homotopy equivalent to an orthogonal group.

Lastly, I will establish sufficient combinatorial conditions under which there is a fixing cycle associated to a triangulation of a smooth manifold. A fixing cycle is a homology class analogous to the fundamental class of a Grassmannian bundle. In the course of this proof, I will consider the concept of a poset of oriented matroid charts as a combinatorial abstraction to the space of flattenings of spheres.

Thursday, 5/12 (Special day)
Title: On the Topology of Corank 1 Tropical Phased Matroids
Speaker: Ulysses Alvarez (Binghamton)
Time: 5:00 p.m.
Location: WH G002 and on Zoom, https://binghamton.zoom.us/j/97930954632

This is Mr. Alvarez's dissertation defense. The dissertation committee consists of Laura Anderson (chair), Michael Dobbins, Ross Geoghegan (co-advisor), and Les Lander (outside examiner).

The dissertation defense is open to the public. All are welcome to attend.

For each topological poset X we can associate a topological space we call the topological order complex of X. Past work done by Ross Geoghegan and me shows that the set of nonzero covectors of a matroid over the tropical phase hyperfield, which can be given a topological poset structure, has the same weak homotopy type as its associated order complex. Given such a matroid of corank (i.e., dual rank, or nullity) 1, the work in this dissertation shows that the associated order complex is homeomorphic to a sphere by equipping the order complex with a regular cell decomposition. Thus the set of nonzero covectors of a corank 1 matroid over the tropical phase hyperfield is weakly homotopy equivalent to a sphere.

Tuesday, 8/31
Title: Polytopes Arising From {1,3}-Graphs: Ehrhart Quasi-Polynomial and Scissors Congruence Phenomenon
Speaker: Jorge L. Ramírez Alfonsín (Montpellier)
Time: 1:15-2:15
Location: Zoom https://binghamton.zoom.us/j/95302383985
in WH 100E and wherever you want to Zoom.

Liu and Osserman introduced a family of polytopes, naturally associated to graphs whose vertices have degrees one and three, and studied their Ehrhart quasi-polynomials. The scissors congruence conjecture for the unimodular group is an analogue of Hilbert's third problem, for the equidecomposability of polytopes. After a gentle introduction to Ehrhart theory, I present a proof of this conjecture for the class of polytopes mentioned above. The key ingredient in the proof is the nearest neighbor interchange on graphs.

I also present some results on the period of the Ehrhart quasi-polynomial as well as some nice geometric and combinatorial properties of such polytopes.

This is joint work with Cristina G. Fernandes, José C. de Pina, and Sinai Robins.

Tuesday, 9/7
No seminar (holiday).

Tuesday, 9/14
Title: What I've Been Thinking About, Part I
Speakers: Uly Alvarez (Topological posets), Seunghun Lee (Geometric hypergraph transversals)
Time: 1:15-2:15
Location: WH 100E

Tuesday, 9/21
Title: What I've Been Thinking About, Part II
Speakers: Chris Eppolito (Pythagorean hyperplanes), Mike Gottstein (Partition containment), Tom Zaslavsky (Projective rectangles)
Time: 1:15-2:15
Location: WH 100E

Thursday, 9/23, in the Geometry/Topology Seminar
Title: A Strong Equivariant Deformation Retraction from the Homeomorphism Group of the Projective Plane to the Special Orthogonal Group
Speaker: Michael Dobbins (Binghamton)
Time: 2:50-3:50
Location: WH 100E

I will present the construction of a strong G-equivariant deformation retraction from the homeomorphism group of the 2-sphere to the orthogonal group, where G acts on the left by isometry and on the right by reflection through the origin. This induces a strong G-equivariant deformation retraction from the homeomorphism group of the projective plane to the special orthogonal group, where G is the special orthogonal group acting on the projective plane. The same holds for subgroups of homeomorphisms that preserve the system of null sets. This confirms a conjecture of Mary-Elizabeth Hamstrom.

Tuesday, 9/28
Title: Recent Work of Baker and Lorscheid on “Foundations of a Matroid”
Speaker: Laura Anderson (Binghamton)
Time: 1:15-2:15
Location: WH 100E

Thursday, 9/30, in the Geometry/Topology Seminar
Title: The topology of a corank-1 matroid over Φ
Speaker: Ulysses Alvarez (Binghamton)
Time: 2:50-3:50
Location: WH 100E

Topological posets allow for the construction of a space which can be viewed as a generalization of the order complex of a discrete poset. We will discuss how this structure can be used to understand the topology of a corank 1 matroid over the tropical phase hyperfield on 4 elements.

AND: Thursday, 9/30, UCLA Combinatorics Seminar
Title: Log-Concave Inequalities for Posets
Speaker: Swee Hong Chan (UCLA)
Time: 2:00-3:00 PDT, 5:00-6:00 EDT
URL for livestream access from UCLA: https://www.math.ucla.edu/~galashin/ucla_comb_sem.html

The study of log-concave inequalities for combinatorial objects has seen much progress in recent years. One such progress is the solution to the strongest form of Mason's conjecture (independently by Anari et al. and Brándën–Huh) that the $f$-vectors of matroid independence complexes are ultra-log-concave [i.e., binomially concave–T.Z.]. In this talk, I discuss a new proof of this result through linear algebra and discuss generalizations to greedoids and posets. This is a joint work with Igor Pak.

The talk is aimed at a general audience.

Tuesday, 10/5
Title: Ehrhart Theory of Rank-Two Matroids
Speaker: Benjamin Schröter (KTH Royal Institute of Technology)
Time: 1:15-2:15
Location: Zoom https://binghamton.zoom.us/j/95302383985
in WH 100E and wherever you want to Zoom.

There are many questions that are equivalent to the enumeration of lattice points in convex sets. Ehrhart theory is the systematic study of lattice point counting in dilations of polytopes. Over a decade ago De Loera, Haws and Köppe conjectured that the lattice point enumerator of dilations of matroid basis polytopes is a polynomial with positive coefficients. This intensively studied conjecture has recently been disproved in all ranks greater than or equal to three. However, the questions of what characterizes these polynomials remain wide open.

In this talk I will report on my work, with Katharina Jochemko and Luis Ferroni, in which we complete the picture on Ehrhart polynomials of matroid basis polytopes by showing that they have indeed only positive coefficients in low rank. Moreover, we also prove that the closely related $h^*$-polynomials of sparse paving matroids of rank two are real-rooted, which implies that their coefficients form log-concave and unimodal sequences.

Tuesday, 10/12
Title: Balanced Matchings and Admissible Division
Speaker: Joseph Briggs (Auburn University)
Time: 1:15-2:15
Location: Zoom https://binghamton.zoom.us/j/95302383985
in WH 100E and wherever you want to Zoom.

The KKM theorem offers a sufficient topological condition for a collection of $d$ closed sets covering the $(n-1)$-dimensional simplex to have a common point in their intersection. It is a continuous version of Sperner's Lemma, and it has important relations to game theory. For example, a classical result of Gale, Woodall and Stromquist says that it is always possible to divide a cake among $n$ hungry players so that each is content with their own assigned piece.

But unfortunately, the same desirable situation is no longer true once there is more than one cake. I will introduce this multiple-cake division problem: If we allow some pieces of cake to be left uneaten (or some players left hungry), how many players can still be simultaneously placated? I will also discuss its relation to an extremal parameter involving matchings in fractionally balanced hypergraphs, which I will use to answer some questions of this form.

Tuesday, 10/19
Title: Quiver Representations Over the Field with One Element
Speaker: Jaiung Jun (New Paltz)
Time: 1:15-2:15
Location: Zoom https://binghamton.zoom.us/j/95302383985
in WH 100E and wherever you want to Zoom.

A quiver is a directed graph, and a representation of a quiver assigns a vector space to each vertex and a linear map to each arrow. Quiver representations arise naturally from problems in the representation theory of associative algebras. Instead of vector spaces and linear maps, one may consider a combinatorial model for quiver representations by replacing vector spaces and linear maps with “vector spaces over the field with one element $F_1$” and “$F_1$-linear maps”. I will introduce several aspects of quiver representations over the field with one element.

This is joint work with Jaehoon Kim and Alex Sistko.

Tuesday, 10/26
Title: Covering Numbers of Graphs
Speaker: Casey Donoven (Montana State-Northern)
Time: 1:15-2:15
Location: WH 100E (in person)

Given a structure $A$ and a class $C$ of substructures, the covering number of $A$ with respect to $C$ is the minimum number of substructures whose union is $A$. Covering numbers have been explored in various disciplines, such as algebra (for groups, rings, loops, semigroups, etc.) and graph theory (biparticity, etc.). I will discuss several covering numbers for graphs, including: covering graphs with complete subgraphs, covering bipartite graphs with complete bipartite subgraphs, and covering digraphs with dicuts. For each, I will establish a theorem describing the covering number obeying the following meta-theorem: there exists a sequence of graphs $\Delta_n$ such that the covering number of $\Gamma$ is the minimum $n$ such that there is an appropriate function from $\Gamma$ into $\Delta_n$.

Tuesday, 11/2
Title: Pairs of Graphs With the Same Even Cycles
Speaker: Bertrand Guenin (Waterloo)
Time: 1:15-2:15
Location: Zoom https://binghamton.zoom.us/j/95302383985
in WH 100E and wherever you want to Zoom.

Whitney proved that if two 3-connected graphs have the same set of cycles (or equivalently, the same set of cuts) then both graphs must be the same. I characterize when two 4-connected signed graphs have the same set of even cycles, and I characterize when two 4-connected grafts have the same set of even cuts.

This is joint work with Cheolwon Heo and Irene Pivotto.

[Notes: “Even” means positive. A graft is a kind of dual of a signed graph. – TZ]

Tuesday, 11/9
No seminar today.

Tuesday, 11/16
Title: Point Arrangements and Oriented Matroids from Biological Data
Speaker: Caitlin Leinkamper (Penn State)
Time: 1:15-2:15
Location: WH 100E (in person)

Determining the rank of a matrix derived from data is a fundamental problem in many fields of biology. However, it is often impossible to measure the true quantity of interest, and we must instead measure a proxy value which has a monotone relationship with the true value. This motivates the following definition: the underlying rank of a matrix A is the minimum rank d such that there is a rank-d matrix B whose entries are in the same order as the entries of A. I introduce a variety of strategies for estimating underlying rank. Using results about random polytopes, I give techniques for estimating the underlying ranks of random matrices which I use to estimate the dimensionality of neural activity in zebrafish. Next, I use Radon's theorem to derive a basic lower bound for underlying rank. I show that underlying rank can exceed this bound using examples derived from oriented matroids and allowable sequences. I show that for d≥2, determining whether a matrix has underlying rank at most d is complete for the existential theory of the reals, and therefore NP hard. However, for d=2, one can solve a combinatorial relaxation of this problem in polynomial time.

Tuesday, 11/23
No seminar today.

Tuesday, 11/30
Title:
Speaker:
Time: 1:15-2:15
Location:

Tuesday, 12/7
Title:
Speaker:
Time: 1:15-2:15
Location:

Friday, 7/9 (special day)
Title: Homotopy Type of the Independence Complexes of Forests
Speaker: Michael Gottstein (Binghamton)
Time: 1:00-3:00

Zoom meeting https://binghamton.zoom.us/j/95302383985

Abstract: I first will show the independence complexes of forests are instances of a class of simplicial complexes for which I show that each member is contractible or homotopy equivalent to a sphere. I then will provide an inductive method of detecting the contractibility of the complex or the dimension of the sphere associated to a forest. Time permitting I will mention other examples of complexes in this class. The talk is based on two papers: “The topology of the independence complex” by Richard Ehrenborg and Gabor Hetyei (2006) and “Homotopy types of independence complexes of forests” by Kazuhiro Kawamura (2010).

This is Mr. Gottstein's examination for admission to candidacy. The examining committee consists of Laura Anderson, Michael Dobbins, and Thomas Zaslavsky (chair).

All interested persons are welcome to participate by Zoom.

Tuesday, 2/16
Organizational meeting
Time: 1:15-2:15

Zoom meeting id: 953 0238 3985

Tuesday, 2/23
Title: What I've Been Doing, Part I
Speakers: Thomas Zaslavsky, James West, Michael Dobbins
Time: 1:15-2:15

Zoom meeting id: 953 0238 3985

Tuesday, 3/2
Title: What I've Been Doing, Part II
Speakers: Olakunle Abawonse, Seunghun Lee
Time: 1:15-2:15

Zoom meeting id: 953 0238 3985

Tuesday, 3/9
Title: None
Speakers: None
Time: 1:15-2:15

Zoom meeting https://binghamton.zoom.us/j/95302383985

Tuesday, 3/16
Title: The Erdös–Faber–Lovász Conjecture and Related Results
Speaker: Dong-yeap Kang (Birmingham [U.K.])
Time: 1:15-2:15

A hypergraph is linear if every pair of two distinct edges shares at most one vertex. A longstanding conjecture by Erdös, Faber, and Lovász in 1972, states that the chromatic index of any linear hypergraph on $n$ vertices is at most $n$. I will discuss the ideas to prove the conjecture for all large $n$.

This is joint work with Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus.

Zoom meeting https://binghamton.zoom.us/j/95302383985

Tuesday, 3/23
Title: Chi-Boundedness
Speaker: Peter Maceli (Ithaca College)
Time: 1:15-2:15

Zoom meeting https://binghamton.zoom.us/j/95302383985

If a graph has bounded clique number and sufficiently large chromatic number, what can we say about its induced subgraphs? In the early 1980’s András Gyárfás made a number of challenging conjectures about this. I will give a survey of how these questions seek to generalize the class of perfect graphs, along with some recent results.

Tuesday, 3/30
Title: Quantitative Helly Theorems
Speaker: Pablo Soberón (Baruch)
Time: 1:15-2:15

Given a family of convex sets in R^d, how do we know that their intersection has a large volume or a large diameter? A large family of results in combinatorial geometry, called Helly-type theorems, characterize families of convex sets whose intersections are not empty. I will describe how some bootstrapping arguments allow us to extend classic results, to describe when the intersection of a family of convex sets in R^d is quantifiably large.

The work presented in this talk was done in collaboration with Travis Dillon, Jack Messina, Sherry Sarkar, and Alexander Xue.

Zoom meeting https://binghamton.zoom.us/j/95302383985

Thursday, 4/1 in the Topology Seminar
Title: Gelfand and MacPherson's Combinatorial Formula for Pontrjagin Classes, Part I: The Topology
Speaker: Olakunle Abawonse
Time: 2:50-3:50
Zoom meeting TBA

See the abstract for the next talk, 4/6.

Tuesday, 4/6
Title: Gelfand and MacPherson's Combinatorial Formula for Pontrjagin Classes, Part II: The Combinatorics
Speaker: Laura Anderson
Time: 1:15-2:15

Let X be a simplicial manifold. A smoothing of X is a smooth manifold M together with a homeomorphism from X to M that is smooth on each closed simplex. Rohlin and Švarc(1957) and Thom(1958) showed that all smoothings of X have the same rational Pontrjagin classes. This raised the hope for a combinatorial formula for these classes. In 1992 Gelfand and MacPheron announced such a formula and gave a very terse proof. In these two talks we'll explain their proof.

The first part of their proof is an alternative form of Chern–Weil theory, which will be the topic of Part I (in the Topology Seminar on 4/1). The second part is a combinatorial model for differential manifolds that admits a combinatorialization of this Chern–Weil theory. We'll discuss this in Part II (in the Combinatorics Seminar on 4/6).

Either talk should be of interest independently of the other.

Zoom meeting https://binghamton.zoom.us/j/95302383985

Tuesday, 4/13
Title: Oriented Matroids from Triangulations of Products of Simplices
Speaker: Chi Ho Yuen (Brown)
Time: 1:15-2:15

Marcel Celaya, Georg Loho, and I introduce a construction of oriented matroids from a triangulation of a product of two simplices. For this, we use the structure of such a triangulation in terms of polyhedral matching fields. The oriented matroid is composed of compatible chirotopes on the cells in a matroid subdivision of the hypersimplex, which might be of independent interest. We also derive a topological representation of the oriented matroid using a variant of Viros patchworking and we describe the extension to matroids over hyperfields.

Zoom meeting https://binghamton.zoom.us/j/95302383985

Tuesday, 4/20
Title: Fork-Free Graphs and Perfect Divisibility
Speaker: Vaidyanathan Sivaraman (Mississippi State)
Time: 1:15-2:15

The fork is the graph obtained from the complete bipartite graph $K_{1,3}$ by subdividing an edge once. What is the structure of graphs not containing the fork as an induced subgraph? In particular, can we bound the chromatic number of such a graph in terms of its clique number? Such a chi-bounding function is known but it is not known whether a polynomial function would suffice. I conjectured that such graphs satisfy a strong property called ''perfect divisibility”, which in turn will yield a quadratic chi-bounding function. I will discuss results proving the conjecture in some subclasses of the class of fork-free graphs.

This is joint work with T. Karthick and Jenny Kaufmann.

Zoom meeting https://binghamton.zoom.us/j/95302383985

Tuesday, 4/27
Speaker: Nemo (the Odyssey)

Tuesday, 5/4
Title: Shellable Dissections for Root Polytopes of Graphs and Digraphs
Speaker: Lilla Tóthmérész (Eötvös)
Time: 1:15-2:15

The root polytope of a bipartite graph $G=(U,W,E)$ is a polytope in $\mathbb{R}^{U\cup W}$ defined as Conv$\{\mathbf{1}_u -\mathbf{1}_w : u \in U, w \in W, uv \in E\}$. This is a well-studied polytope that has nice connections to graph theory. For example its dimension is $|U|+|W|-2$ and its maximal simplices correspond to spanning trees of the graph.

I examine the root polytope of directed graphs $G=(V,E)$, defined as Conv$\{\mathbf{1}_h -\mathbf{1}_t : \overrightarrow{th} \in E\}$. The root polytope of a bipartite (undirected) graph is a special case in which we orient each edge towards $U$.

The root polytope of a digraph might have dimension $|V|-1$. I am interested in the case that the dimension is $|V|-2$ (as in the undirected case). This turns out to be true if each cycle of the digraph has equal numbers of edges going in the two cyclic directions. We call these digraphs semibalanced.

A reason why root polytopes of semibalanced digraphs are interesting is that the facets of so-called symmetric edge polytopes (yet another class of polytopes associated to graphs, whose volume has a relevance to physics) are root polytopes of semibalanced digraphs.

I show a shellable dissection for root polytopes of semibalanced digraphs. Combinatorially, this means giving a nice set of spanning trees. The elements of the $h$-vector also have a combinatorial meaning in terms of the spanning trees.

I also tangentially touch the theory of greedoids.

This is joint work with Tamás Kálmán.

Zoom meeting https://binghamton.zoom.us/j/95302383985

Tuesday, 5/11
Title: Expressing the Skew Spectrum of an Oriented Graphs in Terms of the Spectrum of an Associated Signed Graph
Speaker: Zoran Stanić (Belgrade)
Time: 1:15-2:15

For an oriented graph G′ = (G,σ′) and a signed graph G ̇ = (G,σ), both underlined by the same finite simple graph G, we say that the signature σ is associated with the orientation σ′, and simultaneously that G ̇ is associated with G′, if σ(ik)σ(jk) = s_iks_jk holds for every pair of edges ik and jk, where (s_ij) is the skew adjacency matrix of G′. We prove that such a signature and orientation exist if and only if G is bipartite. On the basis of this result, we prove that, in the bipartite case, the skew spectrum of G′ is fully determined by the spectrum of an associated signed graph G ̇, and vice versa. In the non-bipartite case, we prove that the skew spectrum of G′ is fully determined by the spectrum of a signed graph associated with the bipartite double of G′. In this way, we show that the theory of skew spectra of oriented graphs has a strong relationship with the theory of spectra of signed graphs. In particular, a problem concerning the spectrum of an oriented graph can be transferred to the domain of signed graphs, considered there (where we deal with spectra of real symmetric matrices) and then the result can be ‘returned’ to the framework of oriented graphs. We apply this approach to some particular problems.

Zoom meeting https://binghamton.zoom.us/j/95302383985

Tuesday, 5/18
Title: The Varchenko-Gel’fand Ring of a Hyperplane Arrangement or a Cone
Speaker: Galen Dorpalen-Barry (Minnesota)
Time: 1:15-2:15

The coefficients of the characteristic polynomial of an arrangement in a real vector space have many interpretations. An interesting one is provided by the Varchenko-Gel’fand ring, which is the ring of functions from the chambers of the arrangement to the integers with pointwise multiplication. Varchenko and Gel’fand gave a simple presentation for this ring, along with a filtration whose associated graded ring has its Hilbert function given by the coefficients of the characteristic polynomial. I generalize these results to cones defined by intersections of halfspaces of some of the hyperplanes.

Time permitting, I will discuss Varchenko–Gel’fand analogues of some well-known results in the Orlik–Solomon algebra regarding Koszulity and supersolvable arrangements.

Zoom meeting https://binghamton.zoom.us/j/95302383985

Tuesday, 9/8
Title: Like speed dating, except combinatorics
Speakers: Michael Dobbins, Laura Anderson, Tom Zaslavsky
Time: 1:10-2:10

Zoom meeting id: 925 2894 7102

Today some of us will give very brief introductions to our current research.

Tuesday, 9/15
Title: Like speed dating, except combinatorics, part 2
Speakers: Nick Lacasse, Seunghun Lee
Time: 1:15 - 2:15
Place: Zoomland, opening at 1:00.

Zoom meeting id: 925 2894 7102

Tuesday, 9/22
Title: Like speed dating, except combinatorics, part 3
Speakers: Chris Eppolito, Kunle Abawonse
Time: 1:15 - 2:15
Place: Zoomland, opening at 1:00.

Zoom meeting id: 925 2894 7102

Tuesday, 9/29
Speaker: Thomas Zaslavsky (Binghamton)
Title: Structure for Signed Graphs
Time: 1:15 - 2:15
Place: Zoomland, opening at 1:00.

Zoom meeting id: 925 2894 7102

A signed graph is a graph whose edges are labelled positive or negative. I survey a selection of aspects of signed-graph structure, beginning with Harary's founding “Structure Theorem” and including edges in circles, kinds of connection, a signed Kuratowski-type theorem, and structures that guarantee negative circles are not very disjoint.

Tuesday, 10/6
Speaker: Tillmann Miltzow (Utrecht University)
Title: A Practical Algorithm with Performance Guarantees for the Art Gallery Problem
Time: 1:15-2:15

Zoom meeting id: 925 2894 7102

Given a closed simple polygon P, we say two points p,q see each other if the segment pq is fully contained in P. The art gallery problem seeks a smallest set G of guards that sees P completely. Previous algorithms for the art gallery problem either had theoretical run time bounds (not necessarily good ones) but were utterly impractical, or were practical but could take forever on certain inputs without ever terminating. I present an algorithm that has both theoretical guarantees and practical performance.

This is joint work with Simon Hengeveld.

Tuesday, 10/13
Speaker: Shira Zerbib (Iowa State)
Title: Cutting Cakes with Topological Hall
Time: 1:15-2:15
Place: Zoomland, opening at 1:00.

Zoom meeting id: 925 2894 7102

An r-partite hypergraph is called fractionally balanced if there exists a non-negative function on its edge set that has constant degree in each vertex side. Using a topological version of Hall's theorem, I prove bounds on the matching number of such hypergraphs. Combined with an approach of Meunier and Su (2018), this yields results on envy-free division of multiple cakes, and on rental harmony with multiple houses.

This is joint work with Ron Aharoni, Eli Berger, Joseph Briggs and Erel Segal-Halevi.

Tuesday, 10/20
Speaker: Geva Yashfe (Hebrew University of Jerusalem)
Title: Representability of $c$-Arrangements
Time: 1:15-2:15
Place: Zoomland, opening at 1:00.

Zoom meeting id: 925 2894 7102

This talk is about two undecidability results in matroid theory and their applications to secret-sharing and to the study of rank inequalities for representable matroids. After a brief discussion of the applications, I will outline a proof that the following problem, together with an approximate variant, is undecidable: given a matroid, decide whether its rank function has a positive multiple which is a representable polymatroid.

This is based on joint work with Lukas Kühne.

Tuesday, 10/27
Speaker: Michael Dobbins (Binghamton)
Title: Continuous Dependence of Curvature Flow on Initial Conditions in the Sphere
Time: 1:15-2:15
Place: Zoomland, opening at 1:00.

Zoom meeting id: 925 2894 7102

Consider the space of all simple closed curves of area 0 in the sphere that evenly divide the sphere. I will show that the restriction of level-set flow, which is a weakening of curvature flow, to this space is continuous. This was motivated by a problem of showing that the space of weighted pseudoline arrangements is homotopy equivalent to the corresponding rank 3 real Grassmannian.

Tuesday, 11/3
Speaker: Jo Ellis-Monaghan (Korteweg-de Vries Instituut voor Wiskunde, Universiteit van Amsterdam)
Title: An Introduction to Twualities
Time: 1:15-2:15
Place: Zoomland, opening at 11:45.

Zoom meeting id: 925 2894 7102

Zoomland LUNCH at noon with the speaker; all invited (no crowding, please).

We develop tools to identify and generate new surface embeddings of graphs with various forms of self-twuality including geometric duality, Petrie duality, Wilson duality, and both forms of triality (which is like duality, but of order three instead of two). Previous work typically focused on regular maps (special, highly symmetric, embedded graphs), but the methods presented here apply to general embedded graphs. In contrast to Wilson’s very large self-trial map of type {9,9}_9 we show that there are self-trial graphs on as few as three edges. We reduce the search for graphs with some form of self-twuality to the study of one-vertex ribbon graphs. Our results include a fast algorithm that will find all graphs with any of the various forms of self-twuality in the orbit of a graph that is isomorphic to any twisted dual of itself.

This is joint work with Lowell Abrams (George Washington University).

Tuesday, 11/10
Speaker: Seunghun Lee (Binghamton)
Title: The Near-$d$-Leray Property of Non-Matching Complexes
Time: 1:15-2:15
Place: Zoomland, opening at 1:00.

Zoom meeting id: 925 2894 7102

Given a graph $G$ on the fixed vertex set $V$, the non-matching complex of $G$, denoted by NM$_k(G)$, is the family of all subgraphs $G'$ of $G$ whose matching number $\nu(G')$ is strictly less than $k$. As an attempt to generalize a result by Linusson, Shareshian and Welker, we show that (i) NM$_k(G)$ is $(3k-3)$-Leray, and (ii) if $G$ is bipartite, then NM$_k(G)$ is $(2k-2)$-Leray. This result is obtained by analyzing the homology of the links of non-empty faces of the complex NM$_k(G)$, which vanishes in all dimensions $d \geq 3k-4$, and all dimensions $d \geq 2k-3$ when $G$ is bipartite.

As a corollary, we have the following rainbow matching theorem, which generalizes a result by Aharoni et al. and Drisko's theorem: Given a graph $G=(V,E)$, let $E_1,\ldots, E_{3k-2}$ be non-empty edge sets (not necessarily disjoint), each colored with a different color, that cover $E$. If $\nu(E_i\cup E_j) \geq k$ for every distinct $i$ and $j$, then $G$ has a rainbow matching (where each edge has a different color) of size $k$. The number of edge sets $E_i$ can be reduced to $2k-1$ when $G$ is bipartite.

This is a joint work with Andreas Holmsen.

Tuesday, 11/17
Speaker: Vaidy Sivaraman (Mississippi State)
Title: Double-Threshold Graphs
Time: 1:15-2:15
Place: Zoomland, opening at 1:00.

Zoom meeting id: 925 2894 7102

A graph is double-threshold if there exists a weight assignment to its vertices and real numbers $L$, $U$ such that two vertices are adjacent if and only if the sum of their weights is between $L$ and $U$. The class of double-threshold graphs is closed under induced subgraphs but not under complementation. Kobayashi, Okamoto, Otachi, Uno asked whether the set of forbidden induced subgraphs for the class is finite. We answer this question negatively and make progress on determining the complete set of forbidden induced subgraphs.

This is joint work with Deven Gill.

Tuesday, 11/24
Speaker: Kunle Abawonse (Binghamton)
Title: Homeomorphism Type of Combinatorial Grassmannnian and Combinatorial Flag Manifold
Time: 1:15-2:15
Place: Zoomland, opening at 1:00.

Zoom meeting id: 925 2894 7102

I will consider combinatorial analogues to the Grassmannian G(2,n) and flag manifold G(1,2,n), denoted by MacP(2,n) and MacP(1,2,n) respectively. R. MacPherson conjectured that MacP(2,n) is homeomorphic to G(2,n), while it was later proven by Eric Babson that the manifolds are homotopy equivalent to their respective combinatorial analogues. I will establish that the manifolds are homeomorphic to their combinatorial analogues.

Tuesday, 12/1
Speaker: Benjamin Schröter (KTH Royal Institute of Technology)
Title: Reconstructibility of Matroid Polytopes
Paper: arXiv:2010.10227
Time: 1:15-2:15
Place: Zoomland, opening at 1:00.

Zoom meeting id: 925 2894 7102

My talk will deal with two fundamental objects of discrete mathematics that are closely related - (convex) polytopes and matroids. Both appear in many areas of mathematics, e.g., algebraic geometry, topology and optimization.

A classical question in polyhedral combinatorics is, 'Does the vertex-edge graph of a d-dimensional polytope determine its face lattice?'. In general the answer is no, but a famous result of Blind and Mani, and later Kalai, is a positive answer to that question for simple polytopes. In my talk I discuss this reconstructability question for the special class of matroid (base) polytopes. Matroids encode an abstract version of dependency and independency, and thus generalize graphs, point configurations in vector spaces and algebraic extensions of fields.

This is joint work with Guillermo Pineda-Villavicencio.