| Sept. 11, Organizational
Meeting |
| |
| Sept. 16, Sept. 23, Glenn Hurlbert, Pebbling in
Highly Connected Graphs |
| |
| Abstract: We describe a pebbling
game on a graph whereby a distributor places a configuration of pebbles
on the vertices of a graph and specifies a particular root vertex. The
pebbler then moves pebbles along edges, paying a toll on each edge, with
the purpose of placing a pebble on the root. The minimum number of pebbles
for which the pebbler succeeds, regardless of the distributor's original
configuration, is called the pebbling number of the graph. A graph
with pebbling number equal to its number of vertices is called Class
0. We prove that every graph with large connectivity in terms of its
diameter (specifically $\kappa\ge 2^{2d+3}$) is Class 0 (joint work
with Czygrinow, Kierstead and Trotter). This result has seen several
applications in the world of pebbling, including questions on random
graphs, questions about girth, and Graham's conjecture on products
of graphs. Over the course of two talks we will prove the result. As
time permits we may discuss some of the applications. |
| |
| Sept. 30, Goran Konjevod, On Directed Steiner
trees |
| |
| Abstract: In the directed Steiner
problem, a directed (weighted) graph is given with one of its vertices
designated as the root, and a subset of vertices designated as terminals.
The problem consists in finding a minimum-weight subgraph that contains
a path from the root to each of the terminals. This problem generalizes
the undirected Steiner tree problem as well as set cover, and thus it
is not only NP-hard to find an optimum Steiner tree, but also to find one
that is closer than factor $\log n$ away from the optimum tree. I will
describe the background and earlier work on this problem and then talk
about some recent progress in finding approximation algorithms with a
polylogarithmic performance guarantee. |
| |
|
Oct. 07, Oct. 14, Hal Kierstead, Judging Figure Skaters: On
the Minimum Dimension of Tournaments Having Property S_k |
| |
| Abstract: Suppose a Russian judge,
a French Judge and a Canadian judge are judging a figure skating event,
in which a set V of seven skaters compete. Each judge ranks each skater
from 1 to 7. They consider A to be better than B iff at least two
judges prefer A to B. This is denoted by A -> B. Let E = {(A,B):
A -> B}. Such a pair T = (V,E) is called [a result of] a tournament.
Since this tournament is formed from the rankings of three judges, but
no fewer, we say that it has dimension 3. It is possible (maybe due
to differences in national objectives, taste and morality or collusion)
that the tournament T has the following curious property: for every
pair of skaters {A,B} there exists a skater C such that (C,A) and
(C,B) are both in E. Then regardless of who the judges pick for first
and second place, there is a third skater who is preferred to both. In
this case we say that T has property S_2. More generally, the dimension
of a tournament T = (V, E) is the least number t such that there exist
t rankings such that for all A, B in V, (A,B) is in E iff A is
preferred to B in a majority of the rankings. It is not hard to show
that every tournament (V, E) has dimension at most 2|V|-1. We say that
T = (V,E) has property S_k if for every k-subset S of V there exists
x in V such that for all y in S, (x,y) in E. It is known that for every
positive integer k there exists a tournament T = (V,E) with property
S_k and |V| < 2 k2 2^|V|. Let f(k) be the least integ
|
| |
Oct.
21, A. Czygrinow, Ramsey counting number of graphs
with constant maximum degree
|
|
|
|
| |
| Nov.
4, Charles Colbourn,Ordering Disks and Double Erasure Codes |
| |
Abstract: In
the design of RAID disk subsystems, care must be taken
to ensure that failures of individual disks
do not result in loss of
data. Erasure codes to handle the loss
of two disks simultaneously are
double erasure codes. The overhead
in maintaining sufficient redundant
information to cope with the loss of one
or two disks can be prohibitive.
In this talk, we show one technique to reduce
this overhead in practice
by ordering the columns of the code in a
certain manner. Using this
approach, we encounter a challenging (and
still mostly unresolved) problem
on ordering the edges of the complete graph.
The motivation will be
described in some detail. While the
talk is elementary, the problems
discussed do not seem to be!
|
| |
| Nov. 25, Ya-Chen Chen, Decomposition
of complete graphs into factors with certain properties. |
| |
| Abstract: The decomposition
problem for complete graphs into factors with given diameters was originally
introduced by J. Bosak, A. Rosa and S. Znam. They proved that if the complete
graph K_n on n vertices has a decomposition into k factors of diameter
d, then so has K_m for all m > n. Define f_{d}(k) to be the minimum order
of a complete graph having such a decomposition. Palumbiny proved that
if d > 2, then f_{d}(k) = 2k. Stacho and Urland proved that f(3) = 13.
It is known that 16 < f(4) < 25, that 21 < f(5) < 31, and that
27 < f(6) < 37. Bosak, Erdos, and Rosa proved that f(k) \leq 4.9^2
k^2 \log k for large k. Sauer proved that f(k) \leq 7k, and Bosak showed
later that f(k) \leq 6k. As for lower bounds, Bollobas proved that f(k)
> 6k-9 for k \geq 6. Finally, S. Znam proved that f(k) = 6k for k >
10^{17}. We (joint work with Z. Furedi) improve this to f(k) = 6k when k \geq
70. A graph G has the t-star property if every set of t vertices of G belongs
to a subgraph which is a star. For t = 2, a graph with the 2-star property
is a graph with diameter at most 2. Erdos, Sauer, Schaer, and Spencer defined
f(t,k) to be the smallest number n such that K_n can be decomposed into k
factors each with the t-star property. They proved that 1.5^t k /2 \leq f(t,k)
\leq ct^2 2^t k for some constant c. We (joint work with Z. Furedi) will
show that if t \geq 3 and k \geq 68+t, then f(t,k) \geq 1.5\cdot2^t k + (25-10t)2^{t-2}
- 3. |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
|
If you want to be added to or deleted from the seminar mailing
list please write to andrzej@math.la.asu.edu
|
