Discrete Mathematics Day
Saturday, November 11, 2006
College of the Holy Cross
Worcester, MA
Titles and Abstracts
Ira Gessel
Title: Symmetric Inclusion-Exclusion
Abstract
Ruth Haas
Title: The Combinatorics of Involutions and Twisted Involutions
in Weyl groups.
Abstract:
Weyl groups generalize permutation groups and are useful in many
branches of mathematics. The set of involutions is the set of elements
of order 2. For a given Weyl group, all involutions can be generated
starting from the identity giving a poset. This poset is similar
to the weak order poset for the whole Weyl group, whose combinatorics is
important in representation theory and has been studied extensively by
many mathematicians. The combinatorics of the involution poset is
also of fundamental significance in the study of symmetric spaces and
their representations. This talk will focus on the combinatorics of this
poset. Additionally, we will look at the advantages of using the
combinatorial structure for computation rather than generators and
relations. No knowledge of symmetric spaces or Weyl Groups will be
assumed.
John Little
Title: Toric Codes
Abstract:
Toric codes are a class of m-dimensional cyclic
error-correcting codes introduced recently by J. Hansen.
They may be defined as evaluation codes obtained from monomials
corresponding to integer lattice points in an integral convex polytope
P in Rm.
They are a rather natural extension of the commonly-used
Reed-Solomon codes, and in some cases this construction can be used
to find codes better than any other known examples. In this talk,
we will discuss some combinatorial aspects of toric codes, including
methods for bounding their minimum distance based on a sort of
multivariate version of Vandermonde determinants.
Alin Popescu
Title: Statistical Tools for Digital Image Forensics
Abstract:
In this talk I will present a set of statistical techniques for
detecting tampering in digital images. Empirical evidence shows that
tampering of digital images, while often imperceptible, alters some of
their underlying statistical properties. These alterations can be
exploited to design algorithms that can detect traces of tampering.
I will present five techniques that quantify and detect tampering: (1)
detection of traces of re-sampling (e.g., scaling or rotations) in any
portion of an image; (2) detection of tampering in color filter array
interpolated images; (3) detection of double JPEG compression; (4)
detection of duplicated image regions; and (5) blind detection of
inconsistencies in local signal-to-noise ratios across an image.
This is joint work with Hany Farid.
Seth Sullivant
Title: Combinatorial secant varieties and symbolic powers
Abstract: I will discuss the construction of joins, secant varieties, and symbolic powers in the combinatorial context of monomial ideals. For ideals generated by squarefree quadratic monomials, the generators of the secant ideals and symbolic powers are obstructions to graph coloring and graph covering, respectively. As a consequence, perfect graphs play a central role in the theory, and this leads to two commutative algebra versions of the celebrated Strong Perfect Graph Theorem. For general ideals, we use Gröbner degeneration as a tool to reduces questions about secants and symbolic powers to the monomial case. This yields a new approach to the study of determinantal and Pfaffian ideals, and their symbolic powers. I will try to emphasize the combinatorial aspects of all of this, including connections to graph theory, posets, triangulations, and tilings.