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.
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)
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 Frazier University, Canada)
Apr 16, 2021: Jozef Skokan (London School of Economics, Great Britian)
Apr 23, 2021: Brigitte Servatius (Worchester Polytechnic Institute)
Apr 30, 2021: Joao Costalonga (Universidade Federal Do Espirito, Brazil)
May 7, 2021: Diego Villamizar (Tulane University)
May 14, 2021: Pamela Harris (Williams College)
Title: Kostant's partition function and magic multiplex juggling sequences
Abstract Kostant’s partition function is a vector partition function that counts the number of ways one can express a weight of a Lie algebra g as a nonnegative integral linear combination of the positive roots of g. Multiplex juggling sequences are generalizations of juggling sequences that specify an initial and terminal configuration of balls and allow for multiple balls at any particular discrete height. Magic multiplex juggling sequences generalize further to include magic balls, which cancel with standard balls when they meet at the same height. In this talk, we present a combinatorial equivalence between positive roots of a Lie algebra and throws during a juggling sequence. This provides a juggling framework to calculate Kostant’s partition functions, and a partition function framework to compute the number of juggling sequences. This is joint work with Carolina Benedetti, Christopher R. H. Hanusa, Alejandro Morales, and Anthony Simpson.
Christopher Hanusa (Spring 2011 - Spring 2015)
Spring and Summer 2018
Previous Talks hosted by Janos Pach