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

Fridays Noon - 1:00 pm (Online)

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 2021 Talks

The zoom link is https://us02web.zoom.us/j/86335030379
Email any one of the co-organizers for the password. It is the same as last semester.

Feb 5, 2021: Guy Moshkovitz (Baruch College, CUNY)

Title: Maximizing Projections
Abstract: How many distinct projections onto k coordinates are guaranteed for any set of m binary vectors of length n? This fundamental question is intimately connected to important topics in combinatorics and computer science (Turan numbers, the Sauer-Perles-Shelah Lemma, the Kahn-Kalai-Linial Theorem), and is generally wide open. We almost completely settle the question for a wide range of parameters: linear k and sub-exponential m. Based on joint work with Noga Alon and Noam Solomon.

Feb 12, 2021: CUNY is closed

Feb 19, 2021: Novi Bong (University of Delaware)

Title: The degree diameter problem
Abstract: The degree/diameter problem is a problem to determine the largest (in terms of vertices) graphs or digraphs or mixed graphs of given maximum degree, respectively maximum out degree or mixed degree and given diameter. The general upper bounds for this problem are called the Moore bounds and the graphs that attain this bound are called Moore graphs. Since there are not many Moore graphs, the research in this area then focuses on two approaches: finding a tighter upper bound or constructing large graphs to improve the lower bounds. Besides, the degree/diameter problem has also been generalized. One of its generalization is the maximum degree and diameter-bounded subgraph (MaxDDBS) problem, which aims to determine the maximum order in a graph, but the graph should lie in a given host graph or architecture. Some examples of architectures/host graphs are mesh, triangular network, butterfly networks, etc. In this talk, I will give an overview about the degree/diameter problem for undirected graphs and maximum degree diameter-bounded subgraph for certain host graphs.

Feb 26, 2021: Hua Wang (Georgia Southern University)

Title: Graph invariants and extremal trees
Abstract: Many graph invariants, also referred to as topological indices by some, have been proposed from applications in Biochemistry, Information technology, Phylogeny reconstruction, as well as pure mathematical questions. We present an overview of some of such concepts and the corresponding extremal problems in trees. Some fundamental ideas of the mathematical proofs will be introduced, but most of the technical details will be skipped. Relations between different graph invariants will also be examined along the way.

March 5, 2021: Lutz Warnke (Georgia Institute of Technology)

Title: Prague dimension of random graphs
Abstract: The Prague dimension of graphs was introduced by Nesetril, Pultr and Rodl in the 1970s: as a combinatorial measure of complexity, it is closely related to clique edges coverings and partitions. Proving a conjecture of Furedi and Kantor, we show that the Prague dimension of the binomial random graph is typically of order n/(log n) for constant edge-probabilities. The main new proof ingredient is a Pippenger-Spencer type edge-coloring result for random hypergraphs with large uniformities, i.e., edges of size O(log n). This is based on joint work with He Guo and Kalen Patton, see https://arxiv.org/abs/2011.09459

March 12, 2021: Erkko Lehtonen (Universidade Nova de Lisboa, Portugual)

Title: Associative spectra of graph algebras
Abstract: The associative spectrum was introduced by Csakany and Waldhauser in 2000 as a method of quantifying the non-associativity of binary operations or the corresponding groupoids. The associative spectrum of a groupoid G is an integer sequence, the n-th member of which equals the number of distinct term operations induced on G by the bracketings of n variables. Graph algebras were introduced by Shallon in 1979 and provide a useful representation of directed graphs as algebras with a binary operation. In this talk, we report our work on associative spectra of graph algebras. We classify undirected graphs according to the associative spectra of their graph algebras; there are only three distinct possibilities: constant 1, powers of 2, and Catalan numbers. For arbitrary digraphs, the situation is considerably more complicated. We provide a necessary and sufficient condition for a graph algebra to satisfy a given bracketing identity, expressed in terms of several numerical structural parameters associated, on the one hand, with the graph and, on the other hand, with a pair of bracketings. Based on this, we establish bounds on the possible associative spectra of graph algebras; such a spectrum is either a constant sequence bounded above by 2 or it grows exponentially. This stands in stark contrast with associative spectra of arbitrary groupoids, for which other constant and subexponential spectra are also possible. This is joint work with Tamas Waldhauser (University of Szeged).

Mar 19, 2021: John Saccoman (Seton Hall University)

Title: Extending Spectral Graph Theory Results to Multigraphs
Abstract: Most results in Spectral Graph Theory involved simple graphs. Over the last fifteen years, often along with undergraduate researchers at Seton Hall University, several spectral results have been extended to multigraphs. We present some of them here. This talk is given in memory of Dr. Charles Suffel.

Mar 26, 2021: Charlotte Aten (University of Rochester)

Title: Title: Multiplayer rock-paper-scissors
Abstract: The theory of tournament algebras lies in the intersection of graph theory, universal algebra, and game theory. In this talk we introduce a family of algebras/hypergraphs/games which may be viewed as multiplayer versions of the game rock-paper-scissors as well as n-ary generalizations of tournament algebras. We show how to construct an infinite collection of such algebras via group actions. These algebras are used to show that every finite hypertournament can be embedded into a finite balanced hypertournament. We'll pose a question about the optimality of this embedding.

Apr 9, 2021: Shuxing Li (Simon Fraser University, Canada)

Title: Packings of Partial Difference Sets
Abstract: As the underlying configuration behind many elegant finite structures, partial difference sets have been intensively studied in design theory, finite geometry, coding theory, and graph theory. Over the past three decades, there have been numerous constructions of partial difference sets in abelian groups with high exponent, accompanied by numerous very different and delicate techniques. Surprisingly, we manage to unify and extend a great many previous constructions in a common framework, using only elementary methods. The key insight is that, instead of focusing on one single partial difference set, we consider a packing of partial difference sets, namely, a collection of disjoint partial difference sets in a finite abelian group. Although the packing of partial difference sets has been implicitly studied in various contexts, we recognize that a particular subgroup reveals crucial structural information about the packing. Identifying this subgroup allows us to formulate a recursive lifting construction of packings in abelian groups of increasing exponent. This is joint work with Jonathan Jedwab (arXiv:2012.00979).

Apr 16, 2021: Jozef Skokan (London School of Economics, Great Britain)

Title: Factors in randomly perturbed graphs
Abstract: We study the model of randomly perturbed dense graphs, which is the union of any n- vertex graph Gα with minimum degree αn and the binomial random graph G(n,p). In this talk, we shall examine in detail one of the central questions in this area: to determine when Gα ∪ G(n, p) contains clique factors, i.e. spanning subgraphs consisting of vertex disjoint copies of the complete graph K_k. Time permitting, we shall also discuss related questions about other spanning subgraphs and 2-universality. This is joint work with Julia Böttcher, Olaf Parczyk and Amedeo Sgueglia.

Apr 23, 2021: Brigitte Servatius (Worcester Polytechnic Institute)

Title: Multidimensional tensegrities
Abstract: We develop an equilibrium stressability criterium for trivalent multidimensional tensegrities. The criterium appears in different languages:

1. Stress monodromies,
2. Surgeries
3. Exact discrete 1-forms
4. In Cayley algebra.