Sunday, September 23 | |
15:00 - 18:00 | transfer from Prague to Sadek |
18:30 - 19:30 | problem session |
19:30 | welcome party |
Monday, September 24 | |
8:00 - 9:00 | breakfast |
9:00 - 11:00 | Jerrold Griggs: Minimum Span Real Number Graph Labellings with Separation Conditions |
11:00 - 11:30 | coffee break |
11:30 - 13:00 | problem solving |
13:00 - 14:00 | lunch |
14:00 - 15:00 | a little hike |
15:00 - 18:00 | problem solving |
16:00 -16:30 | coffee break |
16:30 - 18:00 | problem solving |
18:30 | dinner |
Tuesday, September 25 | |
8:00 - 9:00 | breakfast |
9:00 - 11:00 | Andreas Eisenblatter: Automatic Frequency Planning in GSM networks: How to replenish the spectrum |
11:00 - 11:30 | coffee break |
11:30 - 13:00 | problem solving |
13:00 - 14:00 | lunch |
14:00 | departure for the conference trip to Telc |
15:00 - 16:00 | excursion in Telc castle |
17:00 | dinner in Telc |
19:30 | excursion in Louka monastery |
Wednesday, September 26 | |
8:00 - 9:00 | breakfast |
9:00 - 11:00 | Jean-Sebastien Sereni: Griggs and Yeh's Conjecture and the Probabilistic Method |
11:00 - 11:30 | coffee break |
11:30 - 13:00 | problem solving |
13:00 - 14:00 | lunch |
14:00 - 18:00 | problem solving |
16:00 - 16:30 | coffee break |
16:30 - 18:00 | problem solving |
18:30 | wine tasting and dinner |
Thursday, September 27 | |
8:00 - 9:00 | breakfast |
9:00 - 11:00 | problem solving |
11:00 - 11:30 | coffee break |
11:30 - 13:00 | problem solving & progress reports |
13:00 - 14:00 | lunch |
14:30 - 16:30 | transfer to Prague |
In 1988 Roberts described a problem posed to him by Lanfear concerning
the efficient assignment of channels to a
network of transmitters in the plane.
To understand this problem, Griggs and Yeh introduced
the theory of integer vertex -labellings of a graph
.
To prevent interference, labels for nearby vertices
must be separated by specified amounts
depending on the
distance
,
.
One seeks the minimum span of such a labelling.
The
case with
and
has attracted the most attention,
particularly the tantalizing conjecture that if
has maximum degree
, then the minimum span is at most
.
In order to gain more insights for general , it is natural
to expand the model to allow real number labels and separations,
as well as infinite graphs with
.
Griggs and Jin showed that in this case there is a labelling of
minimum span in which all of the labels have the form
, where the
's are integers
.
Moreover, they conjectured that the minimum span as a function of the
separations
is piecewise linear with finitely many pieces.
Babilon et al. introduced -graphs, in which
every edge has weight
for some
, where reals
are fixed. This is a more general model, which better describes the
interference restrictions for an irregular transmitter network in the plane.
Král' proved the Piecewise
Linearity Conjecture in this more general setting.
Networks used in practice often correspond to regular infinite lattices
in the plane, and with two levels of interference, the
-labelling
model with
is appropriate.
Griggs and Jin determined the minimum span of such labellings for general
for the square and hexagonal lattices.
They also solved the triangular lattice for
,
and Král' and Skoda recently completed the remaining cases when
.
Our lecture is intended as an overview of this labelling project, with an emphasis on directions for future research.
The traditional model of (extended) graph coloring or graph k-partitioning for GSM frequency assignment uses a rather coarse notion of interference. Potential interference is given for pairs of cells (i.e., the transmitters emitting the cells' signals), and interference occurs in case transmitters from two cells receive the same or directly adjacent frequencies. Depending on the interference threshold used in the computation of potential interference, this approach systematically under- or over-estimates interference. In the live network, however, harmful interference occurs in case the ratio between the strenght of the serving cell's signal (carrier) and the sum of all interferencing signals (carrier-to-interference ratio) falls below a certain threshold. Relevant interference may originate from the use of the same frequency as well as from adjacent frequencies up to a distance of three.
This talk addresses the difference between interference accounting using the traditional and using a more realistic system model. The more refined accounting model is used as the basis of an alterantive mathematical optimization model that aims at minimizing interference in cases of a significant shortage of available frequencies (by the standards of the traditional model). The refined model is also suited to optimize frequency allocation in the presence of (slow) frequency hopping. Computational results illustrate the difference in the complexity as well as in the capabilities of the two approaches.
In 1992, Griggs and Yeh introduced the definition of an
-labelling of a graph to model a channel assignment problem.
Formally, given a graph
, an
-labelling is a mapping
such that
(i)
whenever
; and
(ii)
whenever
where
is the distance in the graph
.
The
-number
of
is the
smallest
such that
admits an
-labelling into
.
The case where and
attracted the most attention, due to
the following conjecture of Griggs and Yeh: if
has maximum degree
, then
.
We will see that the following approximate version of this conjecture
is true: There exists a constant
such that
for every graph
of maximum degree
. To this end, we will use the probabilistic method
to prove that Griggs and Yeh's conjecture
holds for
large enough. We will actually consider a slightly
more general setting, which is a bit more flexible regarding the channel
assignment problem.
This result generalises to the
-number for every positive
integer
(with
depending on
).
This talk is not an introduction to the probabilistic method. However, its goal -- more than proving the result -- is to show how to create the right environment to be able to use the probabilistic method in our setting, with the hope that some may find it useful for other problems. Some related open questions will be given. This is joint work with Frédéric Havet and Bruce Reed.