Information Technology Reference
In-Depth Information
Fig. 10.1
The nodes in the Petersen graph represent all selections of your mother-in-law if
k
=
3
and
n
=
5
The example displays the combinatorial flavor of the conjecture and it is not
surprising that there exists related work in combinatorics. Recently Alon et al.
[
1
, Conjecture 1.4] have proposed a conjecture that is equivalent to the Kikuta-
Ruckle conjecture. This work of Alon et al. is motivated by an old but still unsolved
conjecture of Erdös on the matching number of hypergraphs [
6
].
=
=
5breaksupintotwoparts,
depending on the value of
h
.If
h
is small, then it is optimal to put a unit dose. If
h
is
large, then it is optimal to put smaller doses. This applies to all known solutions of
the Kikuta-Ruckle conjecture, such as the case of the odd graph that we settle in the
next section, or the case of cyclic graphs that has been solved in [
4
], also see [
2
].
The optimal
j
increases with
h
. Such monotonicity has also been encountered in
probabilistic allocation problems, see e.g. [
7
].
The solution of the conjecture for
k
3and
n
10.2 The Kikuta-Ruckle Conjecture for Odd Graphs
The odd graph
-
element set. Two vertices are connected by an edge if and only if the corresponding
subsets have one common element.
1
O
k
has one vertex for each of the
k
-element subsets of a
(
2
k
−
1
)
The Petersen graph is equal to the odd graph
for
k
3. Norman Biggs [
5
] already remarked that if one wants to understand a
graph theory problem, the odd graph is a good place to start. So we consider the
=
1
The original definition of the odd graph takes
(
k
−
1
)
-element subsets as its vertices. They are
connected by an edge if and only if they are disjoint. So for each edge there is one element that
is not contained in the two vertices: the odd one out. This is where the graph gets its name from.
Our definition is equivalent and more convenient for the poisoning problem. An edge represents
the odd one in.
Search WWH ::
Custom Search