Sponsored by the Graduate Center's Math Department and Computer Science Department

Fridays 11:45 am - 12:45 am in Room 4419

This seminar covers a wide range of topics in combinatorics and its applications.

The CUNY Graduate Center is located at 365 Fifth Avenue (at the corner of 34th Street), New York. It can be easily reached by subway using the B,D,F,N,Q,R, or 6 train.

Seminar Co-Organizers:
CUNY: Nadia Benakli (City Tech) Ezra Halleck (City Tech), Sandra Kingan (Brooklyn College), Joseph Malkevitch (York College), Kerry Ojakian (BCC), Mingxian Zhong (Lehman College),
Montclair State University: Deepak Bal, Jonathan Cutler
Hofstra University: Kira Adaricheva, Eric Rowland

Spring 2019 Talks

Feb 15, 2019: Nadia Benakli (New York City College of Technology)

Title: k-neighborhood degree list of a graph
Abstract: The k-neighborhood degree list of a vertex v in a graph G, denoted by N_kDL(v), is the list of degrees of vertices at distance k from v. In this talk I will present some results for 2-neighborhood degree lists. A 2-switch operation that preserves degrees is the replacement of a pair of edges v1v2 and w1w2 such that deg(v1)=deg(w1) and deg(v2)=deg(w2) by the edges v1w2 and v2w1, given that they did not appear in the graph originally. Building on results by Barrus and Donavan (Discrete Mathematics 341(2018)) and Bassler et al (New J. Phys. 17(2015)), I will prove that within the class of diameter 2 graphs, the 2-switch operation that preserves degrees also preserves 2-neighborhood degree lists. Then I will present a generalization of this operation that preserves 2-neighborhood degree lists in any graph. This is joint work with E. Halleck and S. Kingan.

Mar 1, 2019: Shahriar Shahriari (Pomona College)

Title: Combinatorics of Posets of Subspaces
Abstract: Let V be a finite dimensional vector space over a finite field, and consider the poset of subspaces of V ordered by inclusion. The combinatorial properties of this partially ordered set often resemble those of the Boolean lattices, the subsets of a finite set ordered by inclusion. Often the case of subsets is easier to handle, but, there are situations where a combinatorial question is easier to answer for subspaces. In this talk, we discuss a few combinatorial problems in the poset of subspaces including forbidden configuration problems: Given a small poset P, what is the largest number of subspaces of V that do not contain a copy of P? The latter is joint work with Song Yu.

Mar 8: Pawel Pralat (Ryerson University, Toronto, Canada)

Title: Thresholds in random graphs with focus on thresholds for k-regular subgraphs
Abstract: The most intriguing discovery made by Erdos and Renyi in random graphs is the phenomenon of thresholds. For many graph properties the limiting probability that a random graph possesses them jumps from 0 to 1 (or vice versa) very rapidly, that is, with a rather small increase in the (expected) number of edges. We present a few classical and well understood examples but then move to new results. We prove that the binomial random graph $G_{n,p=c/n}$ with high probability has a k-regular subgraph if c is at least $e^{-\Theta(k)}$ above the threshold for the appearance of a subgraph with minimum degree at least k; i.e. a non-empty k-core. In particular, this pins down the threshold for the appearance of a k-regular subgraph to a window of size $e^{-\Theta(k)}$.

Mar 15, 2019: Rigoberto Florez (The Citadel)

Title: Projective rectangles
Abstract: A projective rectangle is a generalization of the projective plane concept. The elements of this incidence structure are called points and lines. There is a special point and the lines containing the special point are called special. A projective plane is a known example of a projective rectangle. In this case any point can play the role of special. However, in a more general case there is a unique special point, as well special lines and parallel lines. This is a work in progress. In this talk we discuss an axiomatization of projective rectangle. We give examples and properties. We also present some connections with graphs theory, biased graphs, harmonic matroids, and orthogonal arrays.

Mar 29, 2019: Alexander McDonough (Brown University)

Title: Higher Dimensional Chip-Firing and Matroids.
Abstract: The critical group and its relation to spanning trees has been studied extensively in the graphical setting in the context of chip-firing. A more recent area of research has been to generalize chip-firing results to a larger class of objects. In this talk, we explore chip-firing on simplicial complexes as well as regular matroids. Through combining these topics, we produce a bijective proof for Duval-Klivans-Martin's Simplicial Matrix Tree Theorem on a particular class of simplicial complexes. This bijection provides representatives for the elements of the critical groups for these complexes that depend only on a vertex ordering. This talk does not assume any prior knowledge of chip-firing or matroids.

Apr 5, 2019: Alex Kodess (SUNY Farmingdale)

Title: Algebraically Defined Directed Graphs
Abstract

Note: Sat Apr 6, 2019: Graph Theory Day 77 Main Speakers: Mingxian Zhong and Neil Sloane

May 3, 2019: Christophe Hohlweg (Université du Québec à Montréal, Canada)

Title: Combinatorics of reduced words in Coxeter groups and Shi arrangements
Abstract: To tackle many open problems involving a Coxeter group W, a group generated by a particular finite set of mirrors S called the simple reflections, we need to deepen our understanding of the combinatorics of the reduced words on the alphabet S that are describing its elements. In this talk, I will first survey two classes of finite automata that produce the set of reduced words. The first class arises from an ordering of the Cayley graph of (W,S) called the weak order, and the second one arises from particular hyperplanes arrangements called Shi arrangements. It turns out that these two classes are conjectured to be the same. In the second part of this talk, we will discuss how this conjecture is intimately linked to a class of polytopes called “inversions polytopes”, which tight up the relationship between the combinatorics of reduced words and the geometry of the mirrors of W.

Tuesday June 4, 2019: Riste Skrekovski (University of Ljubljana and FIS, Slovenia)

Title: Some results on unique-maximum coloring of plane graphs
Abstract: A unique-maximum coloring of a plane graph is a proper vertex coloring by natural numbers where on each face F the maximal color appears exactly once on the vertices of F. Fabrici and Göring proved that six colors are enough for any plane graph and conjectured that four colors suffice. Thus, this conjecture is a strengthening of the Four Color Theorem. Wendland later decreased the upper bound from six to five. We first show that the conjecture holds for various subclasses of planar graphs but then we disprove it for planar graphs in general. So, we conclude that the facial unique-maximum chromatic number of the sphere is not four but five. Additionally, we will consider some open problems. This is joint work with Vesna Andova, Bernard Lidický, Borut Lužar, and Kacy Messerschmidt.

Friday July 19, 2019: Apoorva Khare (Indian Institute of Science, Bangalore, India)

Title: Distance matrices of graphs: invariants, old and new
Abstract: In 1971, Graham and Pollak showed that if D is the distance matrix of a tree T on n nodes, then det(D) depends only on n, not T. This independence from the tree structure has been verified for many different variants of weighted bi-directed trees. In my talk:

1. I will present a general setting which strictly subsumes every known variant, and where we show that det(D) - as well as another graph invariant, the cofactor-sum - depends only on the edge-data, not the tree-structure.
2. More generally - even in the original unweighted setting - we strengthen the state-of-the-art, by computing the minors of D where one removes rows and columns indexed by equal-sized sets of pendant nodes. (In fact we go beyond pendant nodes.)
3. We explain why our result is the "most general possible", in that allowing greater freedom in the parameters leads to dependence on the tree-structure.
4. Our results hold over an arbitrary unital commutative ring. This uses Zariski density, which seems to be new in the field, yet is richly rewarding.