Humberto Montalvan Gamez, Rutgers University
Title: Arrangements of Lines in the Plane
Interesting results on the arrangement of lines in the plane
will be proved, notably a 1990 proof of the Szemeredi-Trotter 1983 bound
on the maximum number of incidences between m points and n lines. Time
permitting, applications will follow.
Dan Cranston, Rutgers University
Beth Kupin, Rutgers University
Title: Matorids and the Greedy Algorithm
While greedy algorithms are straightforward to think about and
easy to program, they usually don't give optimal solutions. It would be
nice to know when exactly we can get away with a greedy algorithm, and
when we need a more sophisticated tool. Conveniently enough, we can
completely characterize which problems will be solvable with a greedy
algorithm, based on the underlying structure of the problem. The
underlying structure we need is a matroid, a pre-existing algebraic
structure worth studying in their own right.
Rebecka Jornsten, Rutgers University
Title: Clustering - some statistical approaches
Clustering is an exploratory technique used to discover structure
in high-dimensional data. With the data deluge in the biological
sciences (so-called high-throughput biology), clustering has become
an ever-increasingly popular approach to summarize data.
Clustering can be used to detect problems in the data: do experimental
batches group together? do experimental data collected on certain days
group together? Such clustering results indicate that the experimental
design is flawed and systematic biases are present.
clustering can also be used to discover biologically relevant groups in
the data: do experimental data collected from a subset of patients group
together? If so, perhaps these patients share some traits that can provide
insight into a disease state or suggest a new path to treatment.
In this talk, I will review some statistical methods and concepts for
clustering and illustrate the results on a particular type of high-throughput biological
data: microarray data.
Dan Kral, Charles University
Title: Number of perfect matchings in cubic bridgeless graphs
A graph is a combinatorial object comprised of vertices and edges
where each edge joins two vertices. A perfect matching is a set of
edges such that each vertex is incident with one of the edges.
A graph is cubic if every vertex is incident with three edges and
it is bridgeless if it stays connected after removal of any edge.
In this talk, we focus on lower bounds on the number of perfect matchings
in general cubic bridgeless graphs and a special type of cubic bridgeless
graphs called fullerenes. In the general case, a conjecture of Lovasz and
Plummer from 1970s asserts that every cubic bridgeless graph has
an exponential number of perfect matchings. The conjecture has been
recently verified for planar cubic bridgeless graphs by Chudnovsky and
Seymour (2008). We improve the general lower bound of n/4+2 by Edmonds,
Lovasz and Pulleyblank (1982) and Naddef (1982) to n/2 using the brick and
brace decomposition of graphs.
In chemistry, fullerenes are carbon-cage molecules comprised of carbon
atoms that are arranged on a sphere with twelve pentagon-faces and
other hexagon-faces. Fullerenes can be viewed as plane cubic graphs
with faces of size five and six. The stability of a fullerene molecule
is closely related to the number of perfect matchings in the corresponding
graph. The best known general lower bound on the number of perfect matching
in a p-atom fullerene molecule was 3(p+2)/4 which was established
by Zhang et al. [J. Math. Chem. 30 (2001), 343--347]. We show that
every fullerene molecule has at least 2^((p-380)/61) perfect matchings.
Simon Thomas, Rutgers University
Title: The Finite Basis Problem
Click to see abstract
Fred Roberts, Rutgers University
Title: Algorithms for Port of Entry Inspection
As a stream of containers arrives at a port, a decision maker has to decide how to inspect them, which to subject to further inspection, which to allow to pass through with only minimal levels of inspection, etc. We look at this as a complex sequential decision making problem. Sequential decision problems arise in many areas, including communication networks, manufacturing, artificial intelligence and computer science, and medicine. The problem we investigate is to find algorithms for sequential diagnosis that minimize the total "cost" of the inspection procedure, including the cost of false positives and false negatives. To make the problem precise, we imagine a stream of containers arriving at the port with the goal of classifying each of them into one of several categories. There are several possible tests that can be performed and an inspection scheme specifies which test to perform next based on outcomes of previous tests. Stroud and Saeger at Los Alamos have formulated this problem, in an important special case, as a problem of finding an optimal binary decision tree for an appropriate binary decision function. We describe the basic idea of the Stroud-Saeger method and the results of new algorithms that improve significantly on the size of the decision problems for which it is applicable.
Title: What to expect in Prague
Phil Matchett Wood, Rutgers University
Title: The Mathematics of the Rubik's Cube
In the past 30 years, the Rubik's Cube has been one of the worlds best
selling toys and most engaging puzzles, and this talk will aim to
cover some of the mathematics that has been inspired by the Rubik's
Cube. There are many questions one might ask, for example:
* How many different configurations are there for a Rubik's Cube?
* What is the hardest configuration to solve?
* How difficult are generalizations of the Rubik's Cube?
Using the idea of a mathematical group along with algorithms and
optimized computing, the goal of this talk will be a hands-on
demonstration of how the mathematics of the Rubik's Cube can be
applied to something that everyone is interested in: having fun!
Aaron Jaggard, Rutgers University
Title: M\"obius Functions on Partially Ordered Sets
A result from number theory says that if f and g are two functions
such that f(n) is always the sum of g(d) over the
divisors d of n, then g(n) may be expressed as a (slightly more
complicated sum) involving f(d), where d again
ranges over the divisors of n; this is called ``M\"obius inversion.''
In discrete math., the ``Principle of
Inclusion-Exclusion'' tells us that the size of the union of two
finite sets equals the sum of their sizes minus the
size of their intersection, and it also gives us a general formula for
the size of the union of k finite sets.
It turns out that these results are related to each other through a
more general theory of functions defined on
certain classes of posets. Here we present a self-contained survey of
these elegant connections.