 |
|
|
Previous Seminars | Mailing list
|
Spring 2004
|
|
|
| |
| 01/27 | Organizational Meeting
|
| |
| 02/03 | Prof. H. Barcelo, Department of Mathematics,
Graphs and Social Networks
|
| |
| 02/10 | Prof. H. Kierstead, Department of Mathematics,
On-Line Ramsey Theory
|
| |
| 02/17 | Prof. A. Czygrinow, Department of Mathematics, Distributed algorithms for matching problems
|
| |
| 03/02 | Prof. E. Lloyd,
University of Delaware, Fully Dynamic Bin Packing
|
| |
| 03/09 | Prof. D. Duffus, Emory University,
Order preserving maps and automorphisms of partially ordered sets
|
| |
| 03/23 | Gexin Yu, University of Illinois at Urbana-Champaign
, On H-linked graphs.
|
| |
| 04/06 | Melih Onus, Department of CSE, Broadcasting Algorithms in Ad Hoc Networks
|
| |
| 04/13 | Prof. G. Hurlbert, Department of Mathematics,
Whence graph pebbling?
|
| |
| 04/20 | Prof. H. Kierstead, Department of Mathematics,
Dominating Sets in k-Majority Tournament
|
| |
| 04/21 | Prof. B. Maggs, Carnegie Mellon University,
Designing Overlay Multicast Networks for Streaming
|
| |
| 04/27 | S. Smith, Department of Mathematics, A Discrete Homotopy Theory for Graphs, with Applications to Order Complexes
of Lattices
|
| |
|
| 01/27, Organizational meeting |
| |
02/03, Prof. H. Barcelo, Department of Mathematics,
Graphs and Social Networks
Abstract:
This will be a "working" seminar. Some of the sociologists
of the (ASU) Department of Family and Human Development
are studying the formation and dynamic of social networks of children.
I will first explain
how I am using graphs to represent the dynamic of
those social networks of preschool children.
The second part, where I will
need input from the audience, will be a discussion on
what could be "good" measures on these graphs that
would help in their classification and/or differentiation.
Ultimately, one wants to obtain
valuable information on the children's network that can help
the sociologists in their study. |
|
02/10, Prof. H. Kierstead, On-Line Ramsey Theory
Abstract:
We consider the following Ramsey game played by two players Builder and Painter. Let C be a hereditary class of graphs, G a target graph in C and V a finite set of independent vertices. Builder plays by adding edges between nonadjacent vertices of V. At any time in the game the graph that he has constructed so far must be in C. Each time Builder adds an edge, Painter must color it red or blue. At any time in the game the constructed graph may not contain a monochromatic copy of G. The first player that cannot make a legal play looses.
Among other results we will show:
Theorem. For every positive integer k, k-colorable graph G, and sufficiently large vertex set V, Builder has a winning strategy in the Ramsey game on the class C of k-colorable graphs.
|
|
02/17, Prof. A. Czygrinow, Distributed algorithms for matching problems
Abstract:
In this talk, we will discuss a distributed algorithm for approximating the maximum matching.
In particular, we will focus on graphs that do not have "short" odd cycles and present an algorithm
which in a poly-logarithmic number of rounds finds a matching of size which is approximately equal to the size of the maximum matching. The algorithm builds on the algorithmic approach to the maximal matching problem of Hanckowiak, Karonski, and Panconesi.
|
|
03/02,
Prof. E. Lloyd, Fully Dynamic Bin Packing
Abstract:
Bin packing is the problem of: Given a set of items of size between zero and
one, and a supply of bins, each of capacity one, pack the items into a minimum
number of bins. This NP-hard problem is a classic combinatorial optimization
problem and has numerous applications. The first portion of this talk will
review the problem and classic solutions. The second portion of the talk
describes our results on fully dynamic bin packing. In this variant, items may
be inserted into, or deleted from, a packing on a dynamimc basis, and the
packing may be arbitrarily rearranged to accommodate those insertions/deletions
of items. One main result is the Mostly Myopic Packing algorithm that runs in O
(log n) time per insert/delete, and always maintains a packing that is within
5/4 the size of an optimal packing.
|
|
03/09,
Prof. D. Duffus, Emory University,
Order preserving maps and automorphisms of partially ordered sets
Abstract:
There are several [now quite old] problems and conjectures
involving the set of all order preserving maps on a partial order.
For instance, does this set, together with the usual pointwise order,
determine the ordered set? It does in the connected case, or if the
maps are regarded as a semigroup, but the general problem is open.
Another, which is related, is whether the order preserving maps
vastly outnumber the automorphisms. Surprisingly, it is not known
if the minimum of the ratio of the number of automorphisms to
the number of order preserving maps of n-element orders tends to 0
as n tends to infinity.
Recent results on the latter question, obtained with Tomasz Luczak, will
be presented. |
|
03/23,Gexin Yu ,University of Illinois at Urbana-Champaign,
On H-linked graphs
Abstract:
We introduce the notion of $H$-linked graphs, where $H$ is a fixed multigraph with vertices $w_1,\ldots,w_m$. A graph $G$ is $H$-{\it linked} if for every choice of vertices $v_1,\ldots,v_m$ in $G$, there exists a subdivision of $H$ in $G$ such that $v_i$ is the branch vertex representing
$w_i$ (for all $i$). This generalizes the notions of $k$-linked, $k$-connected, and $k$-ordered graphs.
Given $k$ and $n$, we determine the least integer $d$ such that,for every graph $H$ with $k$ edges, every $n$-vertex graph with minimum degree at least $d$ is $H$-linked.
This value $D_1(k,n)$ appears to equal the least integer $d'$ such that every $n$-vertex graph with minimum degree at least $d'$ is $k$-connected. On the way to the proof, we extend a theorem by Kierstead et al on the least integer $d''$ such that every $n$-vertex graph with minimum degree at least $d''$ is $k$-ordered. We will also consider the connectivity conditions for a graph to be $k$-linked in the talk. This is a joint work with Prof. A. Kostochka.
|
|
04/06, Melih Onus, Department of CSE, Broadcasting Algorithms in Ad Hoc Networks
Abstract:
Ad hoc network is a collection of wireless mobile hosts forming a temporary
network without the aid of any fixed infrastructure. The time complexity of
deterministic and randomized protocols for achieving broadcast (distributing a
message from a source to all other nodes) is investigated. We assume
communication takes place in synchronous time-slots and a processor receives a
message at a certain time slot if exactly one of its neighbors transmits at
that time slot. We present a randomized protocol that achieves broadcast in
time which is optimal up to a logarithmic factor. And we present also a new
broadcasing algoritm for power controlled ad hoc networks.
|
|
04/13, Prof. G. Hurlbert, Department of Mathematics, Whence graph pebbling?
Abstract:
In the 1980s Erdos and Lemke made a conjecture in combinatorial number
theory that Lemke and Kleitman proved in a 1989 paper. In searching for
the "book proof" Lagarias and Saks invented graph pebbling as a possible
approach. Chung then used their approach to prove the result, which led
Graham to make his famous graph product conjecture. Lemke and Kleitman
made some generalized conjectures on groups, which is the focus of my
joint work with our undergraduate Jack Hawes Scholar Shawn Elledge. We
prove, for example, that for any sequence of n elements of an abelian
(multiplicatively written) group of order n, some subseqence satisfies the
following two properties: (1) the product of its elements is the identity;
and (2) the sum of the reciprocals of the orders of its elements is at
most 1.
|
|
04/20, Prof. H. Kierstead, Department of Mathematics, Dominating Sets in k-Majority Tournament
Abstract:
A k-majority tournament is a tournament T=(V,E) such
that there exist 2k-1 linear orders on V so that (x,y) is a
directed edge of T iff x is above y in at least k of the
orders. A dominating set is a set D of vertices such that
for all vertices v not in D there exists a vertex d in
D such that (d,v) is a directed edge. Let F(k) be the
least integer t such that every k-majority tournament has a
dominating set of size at most t. We shall show that there
exist constants c and C such that
c k / log(k) <= F(k) <= C k log(k).
|
|
04/21, Prof. B. Maggs, Carnegie Mellon University,Designing Overlay Multicast Networks for Streaming
Abstract:
This talk begins with an overview of the architecture that Akamai uses
to deliver video and audio streams to a world-wide audience. It then
tackles the problem of how to measure stream quality, and once metrics
are defined, it describes various mechanisms that are used to
improve quality. The talk then shifts to a combinatorial problem that
arises in optimizing the overlay network that Akamai uses for
delivering live streams. We describe a polynomial time approximation
algorithm for "designing" such a network. The algorithm finds a
solution that satisfies capacity and reliability constraints to within
a constant factor of optimal, and cost to within a logarithmic factor.
Joint work with Konstantin Andreev, Adam Meyerson, and Ramesh Sitaraman.
|
|
04/27, S. Smith, Deparment of Mathematics, A Discrete Homotopy Theory for Graphs, with Applications to Order Complexes
of Lattices
Abstract:
$A$-theory is a recently developed area of algebraic combinatorics that
takes concepts from algebraic topology and transfers them to a combinatorial
setting. $A$-theory contains discrete analogues to continuity, homotopy,
and fundamental group, defined on graphs and simplicial complexes. A graph
may arise in relation to the order complex of a lattice. Results are given
for the discrete fundamental group of a graph related to the order complex
of the direct sum, ordinal sum, or ordinal product of two finite graded
lattices. A construction is given of the graph related to the order complex
of the direct product of to finite graded lattices. This is explored
further in the case of the Boolean lattice, which may be viewed as the
direct product of smaller lattices. The abelianization of the discrete
fundamental group of the order complex of the Boolean lattice is a free
group on $2^{n-3}(n2-5n+8)-1$ generators, which recovers a formula from Bj
\"orner and Welker in their work on the computational complexity of the $k
$-equal problem, a computer science application.
|
|
If you want to be added to or deleted from the seminar mailing list please write to andrzej@math.la.asu.edu
| |