Combinatorics Seminar in 2005
- December 1. Stephen Fenner, USC CSE, "Bounds on the optimal solution to
some instances of the Channel Assignment Problem"
Abstract:
We give upper and lower bounds on a particular family of instances of
the channel assignment problem in cellular networks. We consider vertex
labelings of the complete triangular lattice on the plane such that any two
vertices within distance k of each other must have labels that
differ by at least k+1-d, where k is a large fixed integer and $d$
is the distance (in the graph) between the two vertices. We show that
any labeling satisfying these constraints must have a span of at least
k^3/4 + O(k^2), but that there is such a labeling with span k^3/3 +
O(k^2), that is, within a ratio of 4/3 from optimal.
- November 17. Jerrold Griggs, USC, "Channel Assignments for Infinite Graphs"
(continued)
- November 10. Jerrold Griggs, USC, "Channel Assignments for Infinite Graphs"
Abstract:
Generalized graph coloring problems arise in connection with efficient
channel assignments for networks of radio transmitters, when conditions
are imposed due to different levels of interference. Such a network
is represented by a simple graph G, which may be infinite. Avoiding
interference leads to minimum separation requirements for channels at
nearby vertices. We consider vertex labellings of G by real numbers that
minimize the span of the labels used.
The optimal span is now completely determined for conditions at
distance two for the square lattice. For another important network
in applications, the triangular lattice, we have determined the optimal
span for conditions at distance two, provided the required separation
at distance one is larger than at distance two.
We report on recent progress developing the general theory for infinite
graphs of bounded maximum degree, where we believe the optimal
span should be a piecewise linear function of the separations.
This is joint work with Teresa Jin.
- November 3. 3:30, Department Colloquium: Gyula Katona, Renyi Institute, Budapest, "Improved YBLM for Sperner families" Coffee will be served at 3:00
- October 27. Lincoln Lu, USC, "Hexagon-free subgraphs in the hypercube" (continued)
- October 20. Lincoln Lu, USC, "Hexagon-free subgraphs in the hypercube"
Abstract:
Let the hypercube $Q_n$ be the graph with a vertex set of all binary
strings of length $n$. Two binary strings are adjacent in $Q_n$ if
and only if they differ exactly at one coordinate. For any integer
$k$, let $f(n,2k)$ be the maximum number of edges, which a subgraph
of $Q_n$ can have without containing an even cycle $C_{2k}$. It can
be shown that the limit of the maximum edge-density
$\lim_{n\to\infty}\frac{f(n,2k)}{ n2^{n-1}}$
always exists. We denote this limit by $\sigma_{2k}$.
The problem of determining $\sigma_{2k}$ is proposed by Erd\H{o}s.
In 1992, Chung proved
$$ \frac{1}{4} \leq \sigma_6 \leq \sqrt{2}-1.$$
The low bound is then improved by Conder in 1993 to $\frac{1}{3}$.
Here we improve the upper bound to $$\sigma_6 \leq 0.3941.$$
- September 29. Jijun Tang, USC CSE, "Algorithmic problems for permutations"
Abstract: In the post-genomic era, plenty of new information is available
for phylogeny reconstruction from the changes in gene order. There are
several obstacles at making use of this information. One of them is the
complexity of computing relevant distances between permutations. Several
important open problems will be identified in this area .
- September 22. Rigoberto Florez, USC Sumter, "Harmonic matroid as a tool
to prove Lindstrom's conjecture"
- September 15. Rigoberto Florez, USC Sumter, "Introduction to matroids II"
- September 8. Rigoberto Florez, USC Sumter, "Introduction to matroids"
Abstract: A matroid is a generalization of the independence structure
of a finite set of vectors. There are no linear relations, only
dependent and independent sets. In this talk we discuss several
equivalents matroid cryptomorphism. We will give a brief introduction to
linear, affine and algebraic representation of matroids.
- September 1. Lincoln Lu, "On large deviation inequalities"
Abstract:
Motivated by studying random graphs with general degree distributions,
we examine a number of generalized and extended versions of concentration
equalities and martingale inequalities. If random variables
are unevenly distributed, these inequalities often provide better bounds
on large deviations than Chernoff's inequality and Azuma's inequality do.