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.