|
|
Next Seminar: Monday
12/08, 11:00 -12:00, LSA L1-94
Speaker:
Prof. W. T. Trotter, Georgia Institute of Technology
Title:
TBA.
|
|
|
|
|
|
|
Discrete
Math Party Picture |
| |
| 10/02
Prof. Andrea Richa, Dynamic Coverage and Related Problems in Ad-Hoc
Sensor Networks |
|
|
10/09
Prof. Glenn Hurlbert, The Cover Pebbling Number of Graphs
COAUTHORS:
Zsuzsanna Szaniszlo, Tammy Cundiff, Betsy Crull,
Paul Feltman, Lara Pudwell, Zsolt Tuza
ABSTRACT:
A pebbling move on a graph consists of taking two pebbles off of one
vertex and placing one pebble on an adjacent vertex. In the traditional
pebbling problem we try to reach a specified vertex of the graph by a
sequence of pebbling moves. In this paper we investigate the case when
every vertex of the graph must end up with at least one pebble after a
series of pebbling moves. The {\it cover pebbling number} of a graph is
the minimum number of pebbles such that however the pebbles are
initially placed on the vertices of the graph we can eventually put a
pebble on every vertex simultaneously. We find the cover pebbling
numbers of trees and some other graphs. We also consider the more
general problem where (possibly different) given numbers of pebbles are
required for the vertices.
|
|
|
10/16
Prof. Charles Colbourn, The Kangaroux Construction
ABSTRACT:
In testing interactions among n qualitatively independent factors,
covering arrays are used. An N x n covering array consists of n-tuples
of elements in which the i'th element is chosen from a specified finite
set S(i) for i=1...n. A covering array has strength t if, when one
selects any t positions in the tuples, every t-tuple of allowed choices
appears in at least one row of the array. In 1987, Roux gave an elegant
"doubling construction" that doubles the number of factors, for
covering
arrays of strength three in which every factor has two elements from
which to choose. Chateauneuf and Kreher extended this construction to
the case when every factor has some number v of elements. In this talk
we describe a generalization that appends k rather than two arrays,
giving a k-ary Roux-type construction (kangaRoux for short). While this
construction may not bring peace in our time, it is nonetheless quite
useful. |
|
|
10/23
Prof. Goran Konjevod, Mathematics of Origami
ABSTRACT:
In this talk I will give an introduction to the mathematical
foundations
of origami----the art of paperfolding. Some of the topics will be
interesting and surprising facts about the geometry of origami,
including proofs that the perimeter of a sheet of paper can be made
arbitrarily large by folding without cutting and that under similar
constraints (no cutting) any arbitrary shape can be folded. The topic I
will cover in some detail is the question of folding a chessboard (from
a single sheet of paper colored white on one side and black on the
other, it is possible to fold an 8x8 black and white grid of squares).
|
|
|
10/30
Prof. Hal Kierstead, First-Fit Coloring of Interval graphs
ABSTRACT:
|
|
|
11/06
Ashwini Kelkar, A review of the paper by J. Robert Johnson on: Finding
a long cycle in the middle two layers of the standard cube.
ABSTRACT:
|
|
|
11/13
Prof. Ya-Chen Chen, Five-cycle-saturated graphs of minimum size
ABSTRACT:
Given a graph F, the graph G is said to be F-saturated if G does not
contain any subgraph isomorphic to F, and F is a subgraph in the graph
obtained by adding any edge not in G to G. sat(n,F) is defined to be
the
minimum number of edges in F-saturated graphs on n vertices. Erdos, A.
Hajnal and J. W. Moon proved that the only K_r-saturated graphs with
minimum size is obtained by joining every vertex of a complete graph
K_(r-2) to each of the remaining n-(r-2) vertices in 1964. Kaszonyi and
Tuza determined sat(n, K_{1, r}), sat(n, rK_2) and sat(n,P_r), and
proved that sat(n,F)=O(n) for fixed F in 1986. L. T. Ollmann determined
sat(n, C_4) and all extremal graphs. Zs. Tuza gave a shorter proof in
1989. C. A. Barefoot, L.H. Clark, R. C. Entringer, T. D. Porter, L. A.
Szkely and Zs. Tuza proved bounds for sat(n, C_k) in 1996. We determine
sat(n, C_5) and extremal graphs. |
|
|
11/20
Shelly Smith, Discrete Homotopy for Graphs: New Results
ABSTRACT:
The $k$-equal arrangement has been widely studied, particularly in
connection with complexity problems in computer science. The
collection of subspaces of $\mathbb{R}^n$ of the form $\{\mathbf{x}\in
\mathbb{R}^n \mid x_{i_1} = x_{i_2} = x_{i_3}\}$ for all 3-subsets of
$[n]$ is the (real) 3-equal arrangement, denoted by
$\mathcal{A}^{\mathbb{R}}_{n,3}$. In 2002, Barcelo et al.
introduced
$A$-theory, a discrete homotopy theory for graphs and simplicial
complexes. Using $A$-theory and purely combinatorial techniques,
we
compute the Betti numbers of the complement of
$\mathcal{A}^{\mathbb{R}}_{n,3}$. |
|
|
12/08 Prof. W. T. Trotter.
|
|
If you want to be added to or deleted from the seminar
mailing list please write to andrzej@math.la.asu.edu
|
