Graduate Center, CUNY

Fridays 11:00 am - 12:00 am Room 4419

This seminar covers a wide range of topics in combinatorics and its applications to other disciplines, especially computer science.

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

Seminar organizers are Kira Adaricheva, Deepak Bal, Jonathan Cutler, Ezra Halleck, Sandra Kingan, and Kerry Ojakian.

Fall 2016 Talks

Sep 16, 2016: Matthew Hyatt (Pace University)

Title: Frobenius seaweed Lie algebras

Abstract: Meander graphs, introduced by Dergachev and A. Kirillov, provide a method for determining the index of seaweed (also called biparabolic) subalgebras of the special linear Lie algebras. In the case of a Frobenius seaweed, we use the meander to prove that the spectrum of the adjoint of a principal element is an unbroken sequence of integers. Additionally, we show that the sequence of the dimensions of the associated eigenspaces is symmetric. Symplectic seaweed subalgebras enjoy the same properties, and we use symplectic meanders to prove this.

Nov 18, 2016: Louis DeBiasio (Miami University)

Title: Density of infinite monochromatic subgraphs

Abstract: For any countably infinite graph G, Ramsey's theorem guarantees a infinite monochromatic copy of G in any r-coloring of the edges of the complete graph K_N on the natural numbers. Taking this a step further, it is natural to wonder if it's possible to measure the "size" of G, for instance by measuring the density of the vertex set of G in the natural numbers. Erdös and Galvin proved that in every 2-coloring of K_N, there exists a monochromatic path whose vertex set has upper density at least 2/3, but it is not possible to do better than 8/9. They also showed that there exists a monochromatic path such that for infinitely many n, the set {1,2,...,n} contains the first n/(3+sqrt{3}) vertices, but it is not possible to do better than 2n/3. We improve both results, in the latter case obtaining a tight bound. We also consider related problems for directed paths, trees (connected subgraphs), and a more general result which includes locally finite graphs. This is joint work with Paul McKenney.

Dec 2, 2016: Pat Devlin (Rutgers University)

Title: Perfect fractional matchings in k-out hypergraphs

Abstract: In the traditional Erdos–Rényi model for random graphs, certain properties (such as Hamiltonicity or having a perfect matching) are likely to appear precisely when certain easy-to-state minimum degree requirements are met. Thus, to get a more precise understanding of these properties, researchers turned their attention to random models where these minimum degree requirements are already built in. One of the most convenient such models is the k-out random graph. In this talk, we will discuss this model and some of the known results about graphs as well as an analogous random structure for hypergraphs. In particular, we will address for which values of k the k-out r-uniform hypergraph is likely to have a perfect fractional matching (as well as similar results in the setting of k-out r-uniform r-partite hypergraphs). No particular background knowledge is assumed.

Dec 9, 2016: Patrick Bennett (Western Michigan University)

Title: Rainbow Hamilton cycles in random geometric graphs

Abstract: Given a graph on n vertices and an assignment of colors to the edges, a rainbow Hamilton cycle is a cycle of length n visiting each vertex once and with pairwise different colors on the edges. Consider n points (i.e. vertices) chosen independently and uniformly at random from the unit square. Form a sequence of graphs on these n vertices by adding edges one by one between each possible pair of vertices. Edges are added in increasing order of length. Each time a new edge is added, it receives a color chosen uniformly at random and with repetition from a set of Kn colors, where K is a large constant. Then, w.h.p. the first graph in the sequence with minimum degree at least 2 contains a rainbow Hamilton cycle. Joint work with Deepak Bal, Xavier Pérez-Giménez, and Pawel Pralat.

Dec 16, 2016: Charles Wolf (Rutgers University)

Title: On the number of ordinary lines determined by sets in complex space

Abstract: The classical Sylvester-Gallai theorem states the following: Given a finite set of points in the 2-dimensional Euclidean plane, not all collinear, there must exist a line containing exactly 2 points (referred to as an ordinary line). In a recent result, Green and Tao were able to give optimal lower bounds on the number of ordinary lines for large finite point sets. In this talk we will consider the situation over the complex numbers. While the Sylvester-Gallai theorem as stated is false in the complex plane, Kelly's theorem states that if a finite point set in 3-dimensional complex space is not contained in a plane, then there must exist an ordinary line. Using techniques developed for bounding ranks of design matrices, we will show that either such a point set must determine at least 3n/2 ordinary lines or at least n-1 of the points are contained in a plane. (Joint work with Abdul Basit, Zeev Dvir and Shubhangi Saraf.)