 |
|
|
Previous Seminars | Mailing list
|
Fall 2004
Wednesdays at 4:00 pm in PSA 102
|
|
|
| |
| 09/08 | Prof. C. Colbourn, Deaprtment of CSE, Products of strength two covering arrays
|
| |
| 09/22 | Prof. H. Kierstead, Department of Mathematics,
TBA
|
| |
| 09/29 | Prof. A. Czygrinow, Department of Mathematics, Uniformity of sub-hypergraphs
|
| |
| 10/06 | Prof. S. Kim, Department of Mathematics,
Homomorphisms from Sparse graph with large girth
|
| |
| 10/13 | Prof. S. Kim, Department of Mathematics,
On the chromatic number of intersection graphs of convex sets in the plane
|
| |
| 10/27 | Prof. H. Kierstead, Department of Mathematics,
The Stanley-Wilf Conjecture
|
| |
| 11/10 | Prof. V. Syrotiuk, Department of CSE,
Complete Directed Bipartite Graph Decompositions and
Energy Limited Sensor Networks
|
| |
| 11/19, Friday | Prof. Alon Efrat, University of Arizona,
Geometric Algorithms for Placement Problems in Sensor Networks
|
| |
|
|
09/08, Prof. C. Colbourn, Department of CSE,
Products of strength two covering arrays
Abstract: A simple recursive construction for covering arrays is presented. A careful examination of the construction leads to some variants in which more factors can be tested with fewer tests (i.e. fewer rows are needed to cover a larger number of columns).
|
|
09/22, Prof. H. Kierstead, Department of Mathematics, TBA
Abstract:
TBA |
|
09/29, Prof. A. Czygrinow, Department of Mathematics, Uniformity of sub-hypergraphs
Abstract:
One of the important properties of a uniform graph is that small subgraphs of it inherit uniformity. In this talk, I will outline an approach to proving a similar fact for uniform hypergraphs. This a joint work with B. Nagle. |
|
10/06, Prof. S. Kim, Department of Mathematics, Homomorphisms from Sparse graph with large girth
Abstract:
A relaxation of Jaeger's conjecture (1984) states that every planar graph of girth at least 4k has circular chromatic number at most 2+1/k. It is equivalent to the fact that for every planar graph G of girth at least 4k, there is a homomorphism from G into the odd cycle of length 2k+1. When k=1, the conjecture is reduced to Grotzsch's theorem: every triangle-free planar graph is 3-colorable. We will discuss the progresses on the conjecture. |
|
10/13, Prof. S. Kim, Department of Mathematics, On the chromatic number of intersection graphs of convex
sets in the plane
Abstract:
Let G be the intersection graph of a finite family of convex
sets obtained by translations of a fixed convex set in the plane.
We show that every such graph with clique number k
is (3k-3)-degenerate. This bound is sharp. As a consequence, we
derive that G is (3k-2)-colorable. We show also that the chromatic
number of every intersection graph H of a family of homothetic copies of
a fixed convex set in the plane with clique number $k$ is at most 6k-6.
(This is joint work with Alexandr Kostochka and Kittikorn Nakprasit.)
|
|
10/27, Prof. H. Kierstead, Department of Mathematics, The Stanley-Wilf Conjecture
Abstract:
A permutation t = t(1), t(2), ... , t(k) is contained in a permutation p = p(1), p(2), ... , p(n) if there exist indices x(1) < ... < x(k) such that t(i) < t(j) iff p(x(i)) < p(x(j)). Otherwise p avoids t. In 1992 Stanley and Wilf conjectured that for every permutation t there exists a constant c such that the number of n-permutations that avoid t is at most c^n. This conjecture was the topic of at least two MIT Ph.D. theses in the 90's. Very recently this conjecture has been proven by a first year graduate student Adam Marcus and his faculty advisor Gábor Tardos. I shall present their beautiful, but elementary proof. The only counting techniques that are needed for the argument are covered in MAT 243, so the talk should be accessible to a wide range of students. Marcus' success should provide motivation to all graduate students to start toying with open problems early in their career. |
|
11/10, Prof. V. Syrotiuk, Department of
CSE, Complete Directed Bipartite Graph Decompositions and
Energy Limited Sensor Networks
Abstract:
We examine decompositions of complete directed graphs into
complete bipartitle subgrahs, as a model for communication
in sensor or mobile ad hoc networks. In an ad hoc network,
each node can be in one of three states: asleep (powered down),
listening, or transmitting. Communication is effective only
when the sender is transmitting, the destination is receiving,
and no other node in proximity to the receiver is also
transmitting. In this talk, the tradeoff between energy
consumption and throughput is examined, under two strong
assumptions. Time is slotted, and nodes can perform frame
synchronization. The strategy requires no assumptions about
knowledge of neighbours or geographic position; it is topology
transparent. When each node has fewer than a designed limit of
active neighbours, the scheme ensures an upper bound on the
maximum delay per hop. Individually, minimizing energy
consumption and maximizing throughput in a topology-transparent
network have been studied, but the former is optimized when
nodes sleep often, the latter is optimized when there are
numerous transmission opportunities; hence the proposed
solutions do not coincide well. Therefore, the schemes for
topology transparency are generalized to treat energy
conservation. |
|
11/19,Prof. Alon Efrat, University of Arizona, Geometric Algorithms for Placement Problems in Sensor Networks
Abstract:
In the first part of the talk we mention several algorithms developed for
a few variants of the Art-Gallery Problem. This problem, in its most
generic terms, is described as follows: Given a geometric region (e.g. a
2D polygon), find a minimal cardinality set of points (called "guards") so
that each point in the polygon is seen by at least one guard. We also
discuss the dual problem, at which the number of guards is fixed, and we
need locate them to maximize the area that they see.
In the second part of the talk we present algorithms for determining
location of base station(s), in order to maximize the duration of a
systems of video sensors. Here all sensors needs to send their data (via
single or multi-hoop path) to the base station.
Joint work with Sariel Har-Peled, Thomas Hou and Joe Mitchell.
|
|
If you want to be added to or deleted from the seminar mailing list please write to andrzej@math.la.asu.edu
| |