Invited Speakers

Keynote speaker:
Peter Winkler
Dartmouth College

Title: What is Probability?

Abstract: An exploration of the uses and misuses of probability in topics ranging from gambling and medicine to the likelihood of intelligent life elsewhere in the universe.

Invited speaker:
Walter Wallis
Southern Illinois University

Title: Generalized Kirkman Designs

Abstract: Kirkman's original "schoolgirl problem" was:

A schoolmistress has 15 girl pupils and she wishes to take them on a daily walk. The girls are to walk in five rows of three girls each. It is required that no two girls should walk in the same row more than once per week.

More generally, Kirkman asked the same question when the class size is an odd multiple of 3. Notice that this is actually a packing problem. But the numbers are such that it is simultaneously a covering problem.

What if the class size is not an odd multiple of 3? We could ask for a set of daily walks in which as many pairs walk together as is possible without repetitions (called a Kirkman packing design)or one where every pair must walk together at least once and the number of repetitions is minimized (a Kirkman covering design). And maybe one row of 2 or 4 girls must be allowed. These and other generalizations will be discussed.

Invited speaker:
Earl Glen Whitehead, Jr.
University of Pittsburgh

Title: Matching Covered Graphs

Abstract: A perfect matching of a graph G is a spanning subgraph of G consisting entirely of independent edges. G is said to be matching covered if for every edge e in G, there is a perfect matching of G that contains e. Various methods of determining which graphs are matching covered will be discussed. We will consider the following types of graphs -- complete tripartite graphs, mesh graphs, generalized theta graphs, cubic graphs, and cages. (This research is joint work with Kimberly Jordan Burch.)

Invited speaker:
Ruth Haas
Smith College

Title: Pebbles, Trees and Rigid Graphs

Abstract: The Pebble Game was developed as an algorithm for determining whether a graph is rigid. In this talk we give some new variations of the pebble game that can be used for deciding if a multi-graph is the union of k edge-disjoint spanning trees or satisifies rigidity type conditions. Along the way we discuss several old and new characterizations of arboricity and rigidity.

Invited speaker:
Ralph Grimaldi
Rose Hulman Institute of Technology

Title: Compositions of Integers

Abstract: A composition of a positive integer n is an ordered sum of positive summands whose total is n. When the summands are restricted to the odd integers one finds that the number of resulting compositions is counted by the Fibonacci numbers. This is also the case when the summands must all exceed 1. If the last summand is required to be odd the number of resulting compositions is counted by the Jacobstahl numbers. These results and related ideas will be examined in this talk.

Invited speaker:
Stanislaw Radziszowski
Rochester Institute of Technology

Title: On the Most Wanted Folkman Graph

Abstract: We discuss a branch of Ramsey theory concerning Folkman graphs and numbers. We write G → (a1,  ...   ,ak; p)e if for every edge k-coloring of an undirected simple graph G not containing Kp, a monochromatic Kai is forced in color i for some i ∈ {1, ... ,k}. The edge Folkman number is defined as

Fe(a1, ... ,ak; p) = min{|V(G)| :(a1,  ...   ,ak; p)e }.

Folkman showed in 1970 that this number exists for p > max(a1, ... ,ak). Fe(3,3;4) involves the smallest parameters for which the problem is open, namely the question, "What is the smallest order N of a K4-free graph, for which any edge 2-coloring must contain at least one monochromatic triangle?" It is known that 16 < N (an easy bound), and it is known through a probabilistic proof by Spencer that N < 3 ∗ 109. We suspect that N < 127.

This talk will present the background, overview some related problems, discuss the difficulties in obtaining better bounds on N, and give some computational evidence why it is very likely that N < 100.

Invited speaker:
Doug Stinson
University of Waterloo

Title: A combinatorial approach to key predistribution for distributed sensor networks

Abstract: In this talk, we discuss the use of certain combinatorial set systems in the design of deterministic key predistribution schemes for distributed sensor networks. We concentrate on analyzing the connectivity and resilience of the resulting distributed sensor networks. Motivated by this application, we introduce a class of combinatorial designs which we term "common intersection designs" (or, CIDs). Several characterizations of "optimal" CIDS are given, which relate to other combinatorial structures such as group-divisible designs, generalized quadrangles and strongly regular graphs. (This talk is based on joint work with Jooyoung Lee.)

Copyright © RIT Department of Mathematics and Statistics