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: Ezra Halleck (City Tech), Sandra Kingan (Brooklyn College), Joseph Malkevitch (York College), Kerry Ojakian (BCC)
Montclair State University: Deepak Bal, Jonathan Cutler
Hofstra University: Kira Adaricheva

Fall 2018 Talks

Sep 7, 2018: Shweta Jain (John Jay College, CUNY)

Title: Role of power centers in a social network

Abstract: Network Science has emerged as a modern multidisciplinary field which finds application in areas as diverse as political science, economics, sociology and biology. As Computer Scientists, we are interested in studying processes executing on complex networks. We model a dynamical system as a complex network where pairs of nodes engage in a two player game such as the Prisoner's Dilemma, Hawk-Dove and the Stag Hunt. The system starts with a random assignment of game strategy and then evolves as players change their strategies using update rules defined in the system. Eventually, the system may reach a steady state or oscillate indefinitely between competing strategies. Our preliminary results show that a steady state is reached when the players observe payoffs after each round and choose to imitate the most successful neighbor in the next round. However, the speed of convergence as well as the point at which convergence happens depends on the type of network. We will present preliminary results and insights in this talk.

Sep 14, 2018: Michael Barrus (University of Rhode Island)

Title: Trends toward the top of the dominance order

Abstract: The dominance order is the partial order on integer partitions arising from majorization. Among the partitions of an even integer, those that are degree sequences of simple graphs form a downward-closed subset of the poset, with the maximal graphic partitions corresponding precisely to the degree sequences of threshold graphs. We show that several properties of degree sequences and their graphs, including forced adjacency relationships, the presence of certain induced subgraphs, and how tightly the Erdos-Gallai inequalities on degree sequences hold, are all related to the degree sequences' location in the dominance order. Popping up along the way are several graph classes that, like the threshold graphs, have degree sequence characterizations and intriguing structural properties.

Oct 26, 2018: Shadisadat Ghaderi (Guttman Community College, CUNY)

Title: The Matroid Intersection Conjecture

Abstract: The theory of finite matroids was introduced by Whitney to capture and generalize the concept of linear independence in vector spaces. This theory was later generalized to infinite sets in a series of papers and recently it attracts a substantial amount of attention. The most important open problem in the field is the Infinite Matroid Intersection conjecture proposed in 1990 by Nash-Williams. It says that each pair of matroids on the same ground set has the Intersection Property and is a suitable restatement in the infinite case of the well-known finite matroid intersection theorem of Edmonds. Some progress was made towards proving this conjecture, but it is still open even for finitary matroids on a countable ground set. We introduce two different methodologies to approach the conjecture. Our results enable us to prove that the Matroid Intersection Conjecture is true some families of matroids.

Nov 2, 2018: Moshe Cohen (Vassar College)

Title: The space of geometric realizations of matroids arising from line arrangements

Abstract: We begin with an example-driven introduction to matroids, which generalize both matrices and graphs. Additionally, they give an appropriate combinatorial structure to study finite collections of lines living in the plane. These line arrangements, as they are called, can also be studied using topology and algebraic geometry.

Zariski gave a pair of degree-six polynomials with the same types of singularities but whose complements have are non-homeomorphic. This motivates the search for similar "Zariski pairs" of line arrangements: two collections of lines with the same combinatorial intersection data but whose (complex projective) complements are not homeomorphic. Rybnikov produced one with thirteen lines in 1998 by gluing two smaller arrangements together. I will describe results from the literature that show that no such pair exists on nine lines or fewer. Together with Amram, Sun, Teicher, Ye, and Zarkh, we investigate arrangements of ten lines. Together with students Liu and Buhmann, May, and Shiyu, we begin to investigate arrangements of eleven lines.

Nov 9, 2018: Mingxian Zhong (Lehman College)

Title: Coloring graphs with forbidden induced subgraphs

Abstract: Graph coloring is a fundamental problem in graph theory and has a variety of applications. It is well known that deciding whether a graph can be colored within k colors is NP-complete for k>=3. Thus it is natural to ask that whether the complexity of the problem changes if we know that the input graph does not contain a particular induced subgraph, H. In this talk, I will first outline a polynomial-time algorithm which determines if an input graph containing no induced six-vertex path can be colored within 4 colors. Combined with previously known results this completes the classification of the complexity of the 4-coloring problem for graphs with a connected forbidden induced subgraph. This is joint work with Maria Chundnovsky and Sophie Spirkl. In the second part of this talk, I will characterize all graphs H for which there are only finitely many minimal non-three-colorable H-free graphs. This is joint work with Maria Chudnovsky, Jan Goedgebeur, and Oliver Schaudt.

Nov 30, 2018: Kira Adaricheva (Hofstra University)

Title:Representations of convex geometries by convex shapes

Abstract: The original problem of Erdos and Szekeres about points in the plane in convex positions (1935), was generalized by Bistriczky and Toth to convex bodies in the plane (1989). There is a similar trend in the study of representations of convex geometries, the closure systems with the anti-exchange axiom. The original problem of Edelman and Jamison (1985), about representation of a convex geometry by points in the plane, is now seen as an inspiration to represent convex geometries by various convex shapes, in the plane as well as higher dimensional spaces. In this talk, we will focus on the recent development about representations of convex geometries by the circles in the dimensions 1 and 2, as well as provide further outlook of representations with ``near-ball" shapes in the plane and in the high dimensional spaces.

Dec 7, 2018: Eric Rowland (Hofstra University)

Title: Extremal sequences avoiding a fractional power

Abstract: Is there an infinite sequence on the alphabet {0, 1, 2} containing no block that occurs twice consecutively? Questions like this were investigated over a century ago by Axel Thue, who discovered some of the earliest results in combinatorics on words. If a pattern is avoidable on a given alphabet, it is natural to ask about the lexicographically least sequence that avoids the pattern. Occasionally the structure of this sequence can be discovered and proved by hand. But for many patterns this sequence is sufficiently complex that computer-assisted discovery, followed by automated proofs, seems to be necessary to make any progress.