|
02/04, Charles Colbourn, Permutation Codes for Powerline
Communications |
|
Abstract: Communication over
ordinary electric power lines can be effected by using permutation
codes, i.e. sets of permutations with specified minimum (Hamming)
distance d. Construction of permutation codes is closely
related to numerous combinatorial objects, such as mutually
orthogonal latin squares, sharply 3-transitive groups, and doubly
resolvable designs. Current research on permutation codes
by Peter Dukes, Wensong Chu, Alan Ling, and the speaker concerns
these connections, in addition to recursive and computational
methods. This talk will introduce some of the application and
develop the combinatorial formulation. No background in
communications is assumed: The talk is eclectic, not electric.
|
| |
02/13,
Ed Ihrig, Lattices corresponding to 1-factorizations and Steiner
Triple Systems
|
|
Abstract: A 1-factor of a
graph is a collection of edges of the graph such that each vertex is
contained in exactly one edge of the 1-factor. A 1-factorization of
a graph is a partition of the edge set into 1-factors. I will
discuss a way in which a lattice can be constructed from a
1-factorization. This lattice can be used to classify 1-factorizations
as well as to help resolve the question of when two 1-factorizations
are isomorphic. I will discuss the classification problem specially
in the context of 1-factorizations constructed from Steiner triple
systems, and I will also discuss the isomorphism question for special
1-factorizations, GK(G), which, according to Alex Rosa, where
discovered by the Slovaks sometime prior to the expansion of the Roman
empire.
|
| |
02/27,
Brendan Nagle, Regularity of set systems
|
|
Abstract: Szemeredi's
regularity lemma for graphs proved to be a powerful tool in extremal
graph theory. A regularity lemma for 3-uniform hypergraphs was
recently given by P. Frankl and V. Rodl (RSA, 2002) which has
proven to extend to 3-graphs some of the Szemeredi regularity lemma
applications to graphs. In this talk, we survey recent progress made
on developing the applicability of Frankl and Rodl's lemma. In
particular, we discuss a few recent applications of their lemma. We
also discuss structural and algorithmic results concerning this
lemma. Finally, we discuss the potential development of extending
current 3-graph regularity theory to k-graphs and an interesting
connection this development would have in combinatorial number theory.
Most of the work discussed in this talk surveys works and works in
progress of principal authors Rodl, Skokan and the speaker (although,
works of other authors will be discussed).
Slides
|
|
03/04,
Hai Huang, Connected Dominating Set and Its
Applications to Mobile Ad-hoc Networks
|
|
Abstract: Dominating set is a subset of vertices of a
graph such that for any vertex in the graph, it is either in the subset
or it is adjacnet to (dominated by) a vertex in the subset. A Minimum
Dominating Set (MDS) is a dominating set with minimum cardinality.
MDS problem is a well known NPC problem. A Connected Dominating Set
is a dominating set such that the subgraph induced by the vertices
in the dominating set is connected (provided the original graph is
connected). Similarly, Minimum Connected Dominating Set (MCDS)
problem asks for the CDS of the minimum cardinality. In this talk,
we'll try to establish the concept of MCDS problem, its computational
complexity, the relationship between it and MDS problem, a
restricted case of the problem and its applications to mobile ad-hoc
netorks and some approximate algorithms. Some current progress on this
problem will also be addressed if time permits.
|
|
03/11,
Glenn Hurlbert, On Finding the Pebbling Threshold of Squared Cliques
|
|
Abstract: Graham's Conjecture, that
the pebbling number of a product of graphs is at most the product of
the pebbling numbers of the graphs, has a probabilistic version for
pebbling thresholds of graph sequences. The simplest instance
involves products of complete graphs, for which the best known upper
bound on its threshold was O(n^{3/4}). In joint work with
Bekmetjev, we prove that its threshold is Theta(n^{1/2}), which
satisfies the probabilistic version of Graham's Conjecture. The
proof winds its way through various models of random sparse bipartite
graphs and large connected components found therein.
|
|
03/25,
Rama Chidambaram, Introduction to genetic algorithm and its application
to supply chain modeling
|
|
Abstract: Genetic Algorithm (GA) is
a probabilistic algorithm, which maintains a population of individuals,
P(t) = {x(1,t), x(2,t),..., x(n,t)} for iteration t. Each individual
represents a potential solution to the problem at hand. Each
solution x(i,t),is evaluated to give some measure of its fitness.
Then a new population (iteration t+1) is formed, by selecting the
more fit individuals from iteration t. Some members of the new
population undergo transformations by means of genetic operators to
form a new solution. This procedure is repeated until we obtain a
desired solution.
Supply chain management offers a large potential for organizations to
reduce costs and improve customer service. Managing a supply chain can
be very challenging due to many different factors. An algorithmic
solution using GA is presented for the better management of supply
chain with non-deterministic demand and non-linear throughput time
(TPT)
|
|
04/10,
Violet Syrotiuk, Algorithmic Problems in Power-Controlled
Ad Hoc Networks
|
|
Abstract: Conserving energy is
a critical issue in ad hoc wireless networks since the nodes are
battery powered. Measurements show that receive power is the same order
of magnitude as transmit power. Hence reducing packet overhearing
through power-control, where each node controls its transmit power
level, can help reduce energy consumption. In this talk, we analyze
some algorithmic problems in power-controlled ad hoc networks.
|
|
04/22,
Shelly Smith, A Homotopy Theory for Graphs
|
|
Abstract: Some concepts are
transferred from algebraic topology to graph theory and put in a
discrete setting. We will examine discrete analogues to
continuity, homotopy, contraction, and fundamental group. We will
prove that the discrete fundamental group of a product of graphs
$\Gamma$ and $\Gamma'$ is isomorphic to the direct product of the
discrete fundamental groups of the individual graphs.
|
|
| 04/29, Ya-Chen Chen, Hamiltonian cycles and chromatic
number of the Kneser Graphs. |
|
Abstract: The Kneser
graph K(n,k) is the graph whose vertices are the k-subsets of an n-set,
with vertices adjacent when the corresponding sets are disjoint. The
Petersen graph is K(5,2) and is not Hamiltonian. It is conjectured that
K(n,k) is Hamiltonian for all other Kneser graphs with n at least 2k+1.
Heinrich and Wallis proved this for K(n,2) and K(n,3). A theorem of
Bor-Liang Chen and Ko-Wei Lih implies the conjecture for n exceeding k2/log k.
Suppose n >= 2k+1. The bipartite Kneser graph H(n,k) has as
its partite sets the k- and n-k-subsets of [n]. Two vertices A and B
from different partite sets are adjacent if the k-subset A is contained
in the n-k-subset B. Erdos' revolving door conjecture states that
H(2k+1,k) is Hamiltonian. It is also known as the middle levels problem.
Simpson proved that H(n,k) is
Hamiltonian for n >= (3k2+k+2)/2.
Hurlbert showed that H(n,k) is Hamiltonian for n > ck2 + k, with c < 1.5 when k is large.
Ya-Chen Chen showed that $K(n,k)$ and $H(n,k)$ are Hamiltonian when $n$
is at least 2.62k earlier. Now we present our approach to prove these
two conjectures when n > 2k + c, for some constant c. Note that this
is an ongoing project, and we haven't had a complete proof yet.
As an introduction to the Kneser graphs, we also present Greene's proof
(using the Lyusternik-Shnirelman theorem which is equivalent to the
Borsuk-Ulam Theorem) of the Lovasz-Kneser's Theorem: the chromatic
number of K(n,k) is n-2k+2. |
|
If you want to be added to or deleted from the
seminar mailing list please write to andrzej@math.la.asu.edu
|
