|
Discrete Mathematics Day At Bard College Saturday, November 8, 2008 |
|
Schedule All talks are in the Reem Kayden Center auditorium (RKC 103).
Cristina Ballantine, College of the Holy Cross Expander Graphs - Algebraic and Combinatorial Constructions Expander graphs are well connected yet sparse graphs. The expansion property of a graph is governed by the second largest eigenvalue of the adjacency matrix. Infinite families of optimal regular expanders (Ramanujan graphs) with constant degree have been constructed by Lubotzky-Phillips-Sarnak as quotients of the Bruhat-Tits building of GL_2(Q_p). The spectrum of the graph is analyzed via the representation theory of the group. I will briefly introduce the LPS construction and its generalizations to hypergraphs and biregular graphs. The focus of the talk is a beautiful and simple combinatorial construction of infinite families of constant degree expanders (with square degree) which are close to being Ramanujan. This construction, called the zig-zag product of graphs, is due to Reingold, Vadhan and Wigderson. I will also describe a generalization of the zig-zag product construction (joint work with Matthew Horton). Debra Boutin, Hamilton College The Determining Set: A (Smallest) Set that Identifies Every Vertex in a Graph There has been considerable interest in finding ways to identify all vertices in a graph. One way has been to find a subset that uniquely identifies each vertex by its relationship with the vertices in that set. Various types of identifying sets have been defined. The one that we will focus on in this talk is the determining set. A set of vertices D of a graph G is called a determining set if every automorphism of G is uniquely determined by its action on the vertices of D. Each vertex of G is then uniquely identified by its graph theoretic properties and its relationship to the vertices of D. Every other type of identifying set is also a determining set, but not conversely. In particular, every identifying set is at least as large as a smallest determining set. We will see for instance that in hypercubes determining sets are significantly smaller and easier to find than their counterparts. In this talk we will look at determining sets and their minimum size in various graph families. These families include trees, hypercubes, Kneser graphs, and Cartesian products. We will also look at two questions for which determining sets can be a useful tool, and some of the results obtained using them. Finally we will explore when a determining has the exchange property and thus behaves like a basis in a vector space or a matroid. In each topic, I will present a few open questions. Robert McGrail, Bard College Knots, Quandles, and the Constraint Satisfaction Problem The speaker will report the progress of the Quandle research group of the Laboratory for Algebraic and Symbolic Computation. In particular, a natural notion of a constraint satisfaction problem over a given three-dimensional knot will be introduced. This relies heavily on the notion of a knot quandle as well as recent results linking universal algebra to the constraint satisfaction problem. Student contributions in the areas of knot theory, universal algebra, computational complexity, symbolic computing, and knowledge management will be showcased. Margaret Bayer, University of Kansas Flag Vectors of Polytopes - An Overview The talk deals with the study of convex polytopes from a combinatorial point of view. The face vector of a polytope counts the faces of each fixed dimension. The flag vector captures more combinatorial information--it counts sequences of faces, of specified dimensions, ordered by inclusion. The problems of characterizing the face vectors and flag vectors of polytopes are open for dimensions four and up... wide open, in the sense that we lack even reasonable conjectures. In this talk I will highlight results, examples, techniques, and connections with other areas of mathematics. Ed Swartz, Cornell University f-Vectors of Manifolds In the over 100 years since the discovery of the Euler-Poincaré formula there have been tremendous advances in the understanding of the geometry and topology of manifolds. However, the enumerative properties of triangulations remain mysterious. For instance, there is no manifold of dimension five or higher whose f-vector is completely understood. We will look at a number of recent advances in this subject. |