### The Claremont Center for the Mathematical Sciences Algebra/Number Theory/Combinatorics Seminar Spring 2010

Tuesdays 12:15 - 1:10 PM
Millikan 208
Pomona College, Department of Mathematics
610 N. College Ave. (Corner of 6th and College Ave.)
Claremont, CA 91711

email: lenny@cmc.edu
Our Webpage at CCMS: CCMS's ANTC Seminar

Our Next Speaker | Upcoming Seminars | Abstracts | Archive

Our Next Speaker | Upcoming Seminars | Abstracts
Calendar and Upcoming Seminars

Our Next Speaker | Upcoming Seminars | Abstracts
Abstracts
• Revisiting the hexagonal lattice: on optimal lattice circle packing
Lenny Fukshansky (Claremont McKenna College)
The classical circle packing problem asks for an arrangement of non-overlapping circles in the plane so that the largest possible proportion of the space is covered by them. This problem has a long and fascinating history with its origins in the works of Albrecht Durer and Johannes Kepler. The answer to this is now known: the largest proportion of the real plane, about 90.7%, is covered by the arrangement of circles with centers at the points of the hexagonal lattice. Although there were previous claims to a proof, it is generally believed that the first complete flawless argument was produced only in 1940 by Laszlo Fejes-Toth. On the other hand, the fact that the hexagonal lattice gives the maximal possible circle packing density among all lattice arrangements has been known at least as early as the end of 19-th century; in fact, all the necessary ingredients for the first such proof were present already in the work of Lagrange. In this talk we outline a modern proof of this classical result, which emphasizes the importance of well-rounded lattices for discrete optimization problems.
• Counting points on hypersurfaces
Daqing Wan (University of California, Irvine)
Point counting over a finite field is a central topic in algorithmic number theory. It has attracted a great deals of attention in recent years due to its diverse applications in areas such as cryptography, coding theory, and computer science. In this lecture, we shall give a self-contained expository introduction to counting the number of rational points on a hypersurface defined over a finite field, covering both algorithmic and complexity aspects.
• Disjoint Chains and Matchings in Posets
Shahriar Shahriari (Pomona College)
Let [n] = {1, 2, ..., n} be a set with n elements. Assume that A_1, ..., A_m are subsets of size k and B_1, ..., B_m are subsets of size h. Furthermore, assume that A_i is a subset of B_i for i = 1 ... m. Can you find m disjoint skipless chains in the poset of subsets of [n] that joins the As to the Bs? A skipless chain from A_i to B_i is a collection of h-k+1 subsets C_0 = A_i, C_1, C_2, ..., C_{h-k-1}, C_{h-k} = B_i such that C_{j-1} is a subset of C_j and has one less element than C_j. We will introduce a new matching property that allows us to discuss this question in general partially ordered sets.
• Quadratic forms over number rings
Larry Gerstein (University of California, Santa Barbara)
The beloved Gram-Schmidt orthogonalization process - the key to classifying inner-product spaces over R - falls short when we consider inner products on modules over rings. For example, if one takes a basis for R^n and generates the linear combinations using only integer coefficients, the result is a Z-lattice L (picture a crystal structure filling R^n), and L need not have any orthogonal decomposition at all. When are two such lattices isometric? What numbers qualify as lengths of vectors in L? These and other issues will be explored for Z-lattices and for lattices over other rings of number-theoretic interest in this expository talk.
• Blackboard biracks
Sam Nelson (Claremont McKenna College)
A blackboard birack is a solution to the set-theoretic Yang-Baxter equation with additional properties making it suited for defining labeling invariants of blackboard-framed knots and links. We will see some examples of blackboard biracks and some of the knot and link invariants they define.
• Sums of triangular numbers
Wai Kiu Chan (Wesleyan University)
In 1796 Gauss wrote in his mathematical diary the theorem that every natural number is the sum of three triangular numbers. In today's terminology, we say that the sum of three triangular numbers is universal. Later Liouville proved a generalization of Gauss' theorem which determines all ternary sums of triangular numbers that are universal. In this talk, I will describe the recent result by W. Bosma and B. Kane which provides a simple characterization of universal sums of triangular numbers and my joint work with B.K. Oh on almost universal sums of triangular numbers.
• Incomplete character sums over finite fields
Mei-Chu Chang (University of California, Riverside)
The aim of this talk is to present new results on incomplete character sums over finite fields. The problems go back to the work of D. Burgess in the seventies. The presentation will be mostly self contained and accessible to non-experts.
• Approximating the permanent of a matrix with nonnegative entries
Mark Huber (Claremont McKenna College)
Finding the determinant of a matrix is made easy by taking advantage of invariants arising from its geometric nature. The permanent slightly tweaks the formula for the determinant, but changes it into a combinatorial entity, making calculation far more difficult. Finding the permanent of a matrix, even when all the entries of the matrix are 0 or 1, is a #P complete problem. Still, all is not lost, as there are upper bounds like Minc's inequality, and lower bounds like Van der Waerden's Inequality. I will show how these two inequalities can be effectively used to construct a Monte Carlo algorithm for approximating the permanent. The permanent is related to counting perfect matchings in a bipartite graph, and this algorithm gives the first method for exact uniform simulation of perfect matchings for a nontrivial class of bipartite graphs.
• Random surfaces
Nicholas Pippenger (Harvey Mudd College)
A number of results will be presented concerning the following model for random surfaces: take an even number n of triangular surfaces and pair their 3n edges at random, with all (3n-1)(3n-3) ... 3 pairings being equally likely. Glue the triangles along the paired edges to obtain an orientable surface with one or more components. We are interested in the topological invariants of the resulting surface. The talk includes joint work with Kristin Schleich and Kevin Fleming.
• Extremal and Probabilistic Combinatorics
Choongbum Lee (University of California, Los Angeles)
Extremal Combinatorics studies the maximum or minimum size of discrete structures (e.g., graphs, set systems) with certain properties. Many questions in this area are motivated by problems in analysis, number theory, probability, theoretical computer science, etc., and numerous problems which seem to be purely combinatorial can only be proved by relying on tools from algebra, analysis, topology, probability and other areas. Moreover, the tools that were developed for one problem turn out to have striking applications in other problems as well. The most successfully developed tool among them is the so-called probabilistic method. Probabilistic Combinatorics, on one hand is the study of this universal framework, which can be potentially applied to any combinatorial problem, and on the other refers to the study of random objects such as the Erdos-Renyi random graphs. There are now fields of Graph Theory and Combinatorics that combine both extremal and probabilistic problems in the most natural ways. Extremal Theory of Random Graphs is one such subject, where we study the typical behavior of basic graph theoretic parameters over the probability space of random graphs. In this talk, I will give a brief introduction to the two topics mentioned above, and then discuss some recent developments in this new field. Joint work with Hao Huang, Michael Krivelevich, Wojciech Samotij, and Benny Sudakov.
• Faces of weight polytopes and a generalization of a result of Vinberg
Tim Ridenour (University of California, Riverside)
This is a preliminary talk on results of joint work with V. Chari and A. Khare. We give an explicit description of the faces of the convex hull of the weights of Generalized Verma Modules for a semisimple Lie algebra g over C. Furthermore, we give a description of faces of certain polyhedra which is a generalization of Vinberg's description of faces of certain polytopes. We also use subsets of weights of finite dimensional irreducible highest weight modules that are contained in a proper face of the weight polytope to construct examples of Koszul algebras.
• The combinatorialization of linear recurrences
Art Benjamin (Harvey Mudd College)
We provide an original combinatorial proof of Binet's formula for Fibonacci numbers: $$F_n = (a^n - b^n)/\sqrt{5},$$ where $a = (1 + \sqrt{5})/2$ and $b = (1 - \sqrt{5})/2$. Naturally, any k-th order linear recurrence with constant coefficients has a closed form solution, obtainable by factoring its (k-th degree) characteristic polynomial. We extend our proof of Binet's formula to show that these closed form solutions can also be given a combinatorial interpretation, even in the repeated roots situation. Based on joint work with Halcyon Derks and Jennifer Quinn.

Our Next Speaker | Upcoming Seminars | Abstracts
Archive

 Claremont Center for the Mathematical Sciences The Claremont Colleges Claremont McKenna College's Department of Mathematics & Computer Science Harvey Mudd College's Department of Mathematics Mathematics at Pitzer College Pomona College's Mathematics Department Scripps College's Mathematics Department Claremont Graduate University's School of Mathematical Sciences