Thursday, June 5, 12 pm - 1:30 pm, CoRE 431.

Humberto Montalvan Gamez, Rutgers University
Title: Arrangements of Lines in the Plane

Abstract: 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.


Tuesday, June 10, 12 pm - 1:30 pm, CoRE 301.

Dan Cranston, Rutgers University
Title: TBA

Abstract: TBA


Thursday, June 12, 12 pm - 1:30 pm, CoRE 301.

Beth Kupin, Rutgers University
Title: Matorids and the Greedy Algorithm

Abstract: 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.


Thursday, June 19, 12 pm - 1:30 pm, CoRE 431.

Rebecka Jornsten, Rutgers University
Title: Clustering - some statistical approaches

Abstract: 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.


Tuesday, June 24, 12 pm - 1:30 pm, CoRE 431.

Dan Kral, Charles University
Title: Number of perfect matchings in cubic bridgeless graphs

Abstract: 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.


Thursday, June 26, 12 pm - 1:30 pm, CoRE 431.

Simon Thomas, Rutgers University
Title: The Finite Basis Problem

Abstract: Click to see abstract


Thursday, July 3, 12 pm - 1:30 pm, CoRE 431.

Fred Roberts, Rutgers University
Title: Algorithms for Port of Entry Inspection

Abstract: 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.


Wednesday, July 9, 12 pm - 1:30 pm, CoRE 431.

Czech students
Title: What to expect in Prague

Abstract: TBA


Thursday, July 10, 12 pm - 1:30 pm, CoRE 431.

Phil Matchett Wood, Rutgers University
Title: The Mathematics of the Rubik's Cube

Abstract: 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!


Thursday, July 24, 12 pm - 1:30 pm, CoRE 431.

Aaron Jaggard, Rutgers University
Title: M\"obius Functions on Partially Ordered Sets

Abstract: 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.