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)
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:
This is joint work with Oleg Karpenkov, Christian Mueller, Gaiane Panina, Herman Servatius, and Dirk Siersma.
- Stress monodromies,
- Exact discrete 1-forms
- In Cayley algebra.
Apr 30, 2021: Joao Costalonga (Universidade Federal Do Espirito Santo, Brazil)
Title: Contractible edges in graphs that preserve a minor and a version for binary matroids.
Abstract: An edge in a 3-connected graph is contractible provided its contraction results in a 3-connected graph. There are many results about the amount and distribution of contractible edges in 3-connected graphs. We will talk about similar results for edges that when contracted not only preserve 3-connectivity but also preserve the existence of a fixed minor up to isomorphisms. We will also extend these results for binary matroids.
May 7, 2021: Diego Villamizar (Tulane University)
Title: A refinement of Dyck paths
Abstract: We will discuss restricted d-Dyck paths. These are paths such that either:
We will present different statistics on these paths and discuss their relation to other combinatorial objects.
This is joint work with Rigoberto Florez, Jose Luis Ramirez, and Fabio A. Velandia.
- There is none or one valley (local minima); or
- For every consecutive pair of valleys, the distance of their heights is at least d.
May 28, 2021: Chandrika Sadanand (University of Illinois Urbana-Champaign) and Nissim Ranade (Cold Spring Harbor Laboratory)
Title: Structure on the top homology and related algorithms
Abstract: We explore the special structure of the top-dimensional homology of any compact triangulable space X of dimension d. Since there are no (d+1)-dimensional cells, the top homology equals the top cycles and is thus a free abelian group. There is no obvious basis, but we show that there is a canonical embedding of the top homology into a canonical free abelian group which has a natural basis up to signs. This embedding structure is an invariant of X up to homeomorphism. This circumstance gives the top homology the structure of an (orientable) matroid, where cycles in the sense of matroids correspond to the cycles in the sense of homology. This adds a novel topological invariant to the topological literature. We apply this matroid structure on the top homology to give a polynomial-time algorithm for the construction of a basis of the top homology (over Z coefficients). This is joint work with Dennis Sullivan.
Round the World Relay in Combinatorics
June 8, 2021 at 9:00 am: Deepak Bal (Montclair State University)
Title: Size Ramsey numbers of paths and cycles
Abstract: Let F1 and F2 be two families of graphs. The size Ramsey number R(F1, F2) is the smallest number m such that there exists a graph G with m edges in which every red-blue coloring of E(G) contains either a red graph from F1 or a blue graph from F2. Let Pn represent the path on n vertices and let 𝒞 represent the family of all cycles. We discuss some recent progress on size Ramsey numbers in the cases where F1 = F2 = Pn (improvement of lower bound) and where F1 = Pn, F2 = c (improvement of lower and upper bounds). We will also discuss some recent results concerning the size Ramsey number of hypergraph paths. This is based on joint works with DeBiasio and Schudrich.
Christopher Hanusa (Spring 2011 - Spring 2015)
Spring and Summer 2018
Previous Talks hosted by Janos Pach