The Claremont Center
for the Mathematical Sciences

Algebra/Number Theory/Combinatorics Seminar
Fall 2009

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

For more information contact: Lenny Fukshansky
email: lenny@cmc.edu
Our Webpage at CCMS: CCMS's ANTC Seminar

Our Next Speaker | Upcoming Seminars | Abstracts | Archive
Our Next Speaker
Our Next Speaker | Upcoming Seminars | Abstracts
Calendar and Upcoming Seminars
Our Next Speaker | Upcoming Seminars | Abstracts
Abstracts
  • Simulation reductions for the Ising model
    Mark Huber (Claremont McKenna College)
    The set of #P complete problems is the counting equivalent of NP complete problems. For instance, "Is there a Hamiltonian path of length less than 60?" is in NP, while "How many Hamiltonian paths of length less than 60 are there?" is a problem in #P. Often #P problems are of the form: let Z be the sum of w(x), where x ranges over a particular set of combinatorial objects. Then calculating Z exactly is often a #P complete problem. A famous example of this type of problem is the Ising model, where each node in a graph is assigned to be either spin up, or spin down, and w(x) is an energy of the configuration. In this talk, I will discuss three different forms of the Ising model. Two of these forms were already known to be linked by what is called a simulation reduction. Here I will present a result showing that the third form of the model can also be "simulation reduced" to the other two forms. This provides a new proof of a known result regarding the relationship between the values of Z for the different forms, and also results in several new algorithms for the Ising model.
  • The peculiar phase structure of random graph bisection
    Allon Percus (Claremont Graduate University)
    The mincut graph bisection problem involves partitioning the n vertices of a graph into disjoint subsets, each containing exactly n/2 vertices, while minimizing the number of "cut" edges with an endpoint in each subset. When considered over sparse random graphs, the phase structure of the graph bisection problem displays certain familiar properties, but also some surprises. It is known that when the mean degree is below the critical value of 2 log 2, the bisection width (or cutsize) is zero with high probability. We study how the minimum bisection width increases with mean degree above this critical threshold, finding a new analytical upper bound that improves considerably upon previous bounds. Combined with recent results on expander graphs, our bound suggests the unusual scenario that random graph bisection is replica symmetric up to and beyond the critical threshold, with a replica symmetry breaking transition possibly taking place above the threshold. An intriguing algorithmic consequence is that although the problem is NP-hard, we can conceivably find near-optimal bisection widths (whose ratio to the optimal value approaches 1 asymptotically) in polynomial time for typical instances near the phase transition. This is joint work with Gabriel Istrate, Bruno Goncalves, Robert Sumi and Stefan Boettcher.
  • Khovanov homology and the Jones polynomial
    Sam Nelson (Claremont McKenna College)
    In 1986, Vaughan Jones discovered the Jones Polynomial, a powerful invariant of knots and links. In 1998, Mikhail Khovanov took it one step further with a categorification of the Jones polynomial we now call Khovanov homology, which determines the Jones polynomial and is a stronger invariant. In this talk we will review the Jones polynomial and see the basics of Khovanov homology.
  • Generating an algebra from the probabilistic standpoint
    Bogdan Petrenko (SUNY Brockport)
    Let A be a ring whose additive group is free abelian of finite rank. The topic of this talk is the following question: what is the probability that k random elements of A generate it as a ring? After making this question precise I will show that it has an interesting answer which can be interpreted as a local-global principle. (This is joint work with Rostyslav Kravchenko and Marcin Mazur.)
  • Tests of uniformity for rank data, the symmetric group, and frames
    Michael Orrison (Harvey Mudd College)
    In this talk, I'll present some ongoing work I'm doing with Anna Bargagliotti (Univ. of Memphis) concerning linear tests of uniformity for rank data. In particular, I'll show how the representation theory of the symmetric group plays a natural role when trying to understand why different tests of uniformity might react differently to the same data set. I'll also say something about the intriguing appearance of "group frames" in the computation of a couple of popular linear test statistics.
  • Fourier analysis, linear programming, and densities of distance avoiding sets
    Frank Vallentin (TU Delft, Netherlands)
    In this talk I will consider the problem of determining the maximum density of sets in Euclidean space which avoid some given distances, in the sense that there are no two points in the set at the given distances. To find upper bounds for the maximum density we use the Fourier coefficients of the autocorrelation function of the characteristic function of a distance avoiding set together with linear programming. This method is a continuous analog of the sphere packing bound due to Cohn and Elkies. I will show two applications of the bound: Computing new upper bounds for the density of sets avoiding the unit distance in dimension 2,...,24. Giving an alternative, quantitative, and extremely simple proof of a result of Furstenberg, Katznelson, Weiss, proved by ergodic theoretic methods: Every planar set of positive density does not avoid arbitrary large distances. This is joint work with Fernando M. de Oliveira Filho (http://arxiv.org/abs/0808.1822).
  • Fields of norms and p-adic dynamical systems
    Ghassan Sarkis (Pomona College)
    A continuation of an ANTC seminar I gave last year, this talk will be self contained. The natural multiplicative structure of the norm group of local field extensions can sometimes be supplemented with an unexpected additive one, transforming the norm group into a local field of characteristic $p$. This so-called field-of-norms construction induces an equivalence of categories between certain local field extensions and local fields of characteristic $p$. In this talk, I will present a simple example of the power of the field of norms to answer questions from $p$-adic dynamical systems.
  • The Typical Structure of Graphs without Given Excluded Subgraphs
    Jozsef Balogh (University of Illinois at Urbana-Champaign)
    Let $\cal L$ be a finite family of graphs. We describe the typical structure of $\cal L$-free graphs, improving our earlier results on the Erd\H{o}s-Frankl-R\"odl theorem, by proving our conjecture from our earlier paper. Let $$p=p({\cal L})=\min_{L\in {\cal L}}\chi(L)-1.$$ We shall prove that the structure of almost all $\LL$-free graphs are very similar to the Tur\'an graph $T_{n,p}$, where ``similarity'' is measured in terms of graph theoretical parameters of $\LL$. Some more recent developments, including extensions for induced containment, bipartite graphs, hypergraphs, will be discussed as well. Partially joint work with: Alon, Bollobas, Butterfield, Morris, Mubayi, Samotij, and Simonovits.
  • Neighborhood complexes and rational generating functions
    Kevin Woods (Oberlin College)
    One approach to integer programming (maximizing an objective function across all "feasible" integer points satisfying a set of linear inequalities) is to start at some feasible integer point and continue stepping to a "nearby" feasible integer point that is better according to our objective function. If the set of possible nearby points is chosen correctly, using Herbert Scarf's definition of neighbors, we will eventually arrive at the desired optimum integer point. Consider the integer points in a polytope and connect with an edge every pair who are neighbors. This gives the set of edges of a useful simplicial complex called the neighborhood complex. Using the fact that the neighborhood complex is contractible, we can compute generating functions for the following types of sets: those defined as the projection of the set of integer points of a polyhedron. As a concrete example of this sort of set, suppose we are given relatively prime positive integers a_1, ..., a_d, and define S to be the set of integers that can be written as a nonnegative integer combination of these a_i. We'd like to answer questions like "What is the largest integer not in S?" and "How many integers are not in S?" These questions can be attacked via generating functions. This talk builds on joint work with Herbert Scarf.
  • Ranks of polynomials
    Zach Teitler (Texas A&M)
    The Waring rank of a polynomial of degree d is the least number of terms in an expression for the polynomial as a sum of d-th powers. The problem of finding the rank of a given polynomial and studying rank in general has been a central problem of classical algebraic geometry, related to secant varieties; in addition, there are applications to statistics, signal processing, and computational complexity. Other than a well-known lower bound for rank in terms of catalecticant matrices, there has been relatively little progress on the problem of determining or bounding rank for a given polynomial (although related questions have proved very fruitful). I will describe new upper and lower bounds. The improved lower bound is especially interesting, dealing with the geometry of catalecticants. The talk should be accessible to all. This is joint work with J.M. Landsberg.
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