summaryrefslogtreecommitdiff
path: root/42833-t/42833-t.tex
diff options
context:
space:
mode:
Diffstat (limited to '42833-t/42833-t.tex')
-rw-r--r--42833-t/42833-t.tex316
1 files changed, 159 insertions, 157 deletions
diff --git a/42833-t/42833-t.tex b/42833-t/42833-t.tex
index 146d406..002146a 100644
--- a/42833-t/42833-t.tex
+++ b/42833-t/42833-t.tex
@@ -15,10 +15,11 @@
% Author: John W. Moon %
% %
% Release Date: June 5, 2013 [EBook #42833] %
+% Most recently updated: June 11, 2021 %
% %
% Language: English %
% %
-% Character set encoding: ISO-8859-1 %
+% Character set encoding: UTF-8 %
% %
% *** START OF THIS PROJECT GUTENBERG EBOOK TOPICS ON TOURNAMENTS *** %
% %
@@ -116,7 +117,7 @@
\documentclass[12pt]{book}[2005/09/16]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%% PACKAGES %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\usepackage[latin1]{inputenc}[2006/05/05]
+\usepackage[utf8]{inputenc}[2006/05/05]
\usepackage{ifthen}[2001/05/26] %% Logical conditionals
@@ -172,7 +173,7 @@
Minor typographical corrections have been made relative to the 1968
edition, and the proof of Theorem~34 (\Pagerefs{Thm34start}{Thm34end})
has been revised to correct an error pointed out to the author by
- B.~Bollobás in a letter dated 12~June 1980.
+ B.~Bollobás in a letter dated 12~June 1980.
\bigskip
The camera-quality files for this ebook may be downloaded at
@@ -589,10 +590,11 @@ Title: Topics on Tournaments
Author: John W. Moon
Release Date: June 5, 2013 [EBook #42833]
+Most recently updated: June 11, 2021
Language: English
-Character set encoding: ISO-8859-1
+Character set encoding: UTF-8
*** START OF THIS PROJECT GUTENBERG EBOOK TOPICS ON TOURNAMENTS ***
\end{PGtext}
@@ -639,7 +641,7 @@ Dallas\ .\ Montreal\ .\ Toronto\ .\ London
\PageSep{vi}%
\null\vfill
\begin{flushright}
-Copyright © 1968 by Holt, Rinehart and Winston, Inc. \\
+Copyright © 1968 by Holt, Rinehart and Winston, Inc. \\
All Rights Reserved
\medskip
@@ -1093,8 +1095,8 @@ proof of the theorem by induction.
\Ex{1.} Examine the argument Foulkes (1960) gave to show that an irreducible
\index{Irreducible tournament}%
\index[xauthor]{Foulkes, J. D.}%
-tournament has a spanning cycle. [See also Fernández de~Trocóniz (1966).]
-\index[xauthor]{Fernández de Troconiz, A.}%
+tournament has a spanning cycle. [See also Fernández de~Trocóniz (1966).]
+\index[xauthor]{Fernández de Troconiz, A.}%
\Ex{2.} Let us say that a tournament has property~$P_{k}$ if every subset of $k$~nodes
determines at least one $k$-cycle. Show that $T_{n}$~has a spanning cycle if it
@@ -1366,7 +1368,7 @@ bipartite tournaments with the same score vectors that do not have the
same number of $4$-cycles.
\Ex{9.} Show that the maximum number of $4$-cycles an $m$~by~$n$ bipartite tournament
-can have is $[m^{2}/4] · [n^{2}/4]$. [Moon and Moser (1962a).]
+can have is $[m^{2}/4] · [n^{2}/4]$. [Moon and Moser (1962a).]
\index[xauthor]{Moon, J. W.}%
\index[xauthor]{Moser, L.}%
@@ -1422,10 +1424,10 @@ If $r(ijk) = t(ijk) - \nf{1}{4}$, then
where the sum is over the triples $i$,~$j$, and~$k$. The products in this expansion
are of the following types:
\[
-r(ijk) · r(ijk),\quad
-r(ijk) · r(ijw),\quad
-r(ijk) · r(ivw),\quad\text{and}\quad
-r(ijk) · r(uvw).
+r(ijk) · r(ijk),\quad
+r(ijk) · r(ijw),\quad
+r(ijk) · r(ivw),\quad\text{and}\quad
+r(ijk) · r(uvw).
\]
The variables appearing in each of the last two products are independent;
hence, the expectation of their product equals the product of their individual
@@ -1542,7 +1544,7 @@ tends to the normal distribution with zero mean and unit variance, where
\Ex{1.} The quantity
\[
h = \frac{12}{n^{3} - n}
- · \sum_{i=1}^{n} \left(s_{i} - \frac{1}{2}(n - 1)\right)^{2}
+ · \sum_{i=1}^{n} \left(s_{i} - \frac{1}{2}(n - 1)\right)^{2}
\]
is called the \emph{hierarchy index} of a tournament. Show that the mean and
\index{Hierarchy index}%
@@ -1618,8 +1620,8 @@ Every tournament~$T_{n}$ ($n \geq 4$) contains at least one transitive subtourna
\index{Subtournament}%
but not every tournament~$T_{n}$ is itself transitive. The following
question arises: What is the largest integer $v = v(n)$ such that every tournament~$T_{n}$
-contains a transitive subtournament~$T_{v}$? Erdös and Moser (\Erratum{1964}{1964a})
-\index[xauthor]{Erdös, P.}%
+contains a transitive subtournament~$T_{v}$? Erdös and Moser (\Erratum{1964}{1964a})
+\index[xauthor]{Erdös, P.}%
\index[xauthor]{Moser, L.}%
gave the following bounds for~$v(n)$. [The lower bound was first found by
Stearns (unpublished).]
@@ -1656,8 +1658,8 @@ and only if $j - i$ is a quadratic residue modulo~$7$ contains no transitive
subtournament~$T_{4}$. It follows that $v(7) = 3$. Bent (1964) examined other
\index[xauthor]{Bent, D. H.}%
similarly constructed tournaments and deduced the information about~$v(n)$
-given in \Table{2}. Erdös and Moser conjecture that $v(n) = [\log_{2} n] + 1$
-\index[xauthor]{Erdös, P.}%
+given in \Table{2}. Erdös and Moser conjecture that $v(n) = [\log_{2} n] + 1$
+\index[xauthor]{Erdös, P.}%
\index[xauthor]{Moser, L.}%
for all~$n$.
\begin{table}[hbt!]
@@ -1727,7 +1729,7 @@ proof of the theorem.
\begin{Corollary}
The maximum number of transitive subtournaments a
strong tournament~$T_{n}$ ($n \geq 3$) can contain, including the trivial tournaments
-$T_{1}$ and~$T_{2}$, is~$3 · 2^{n-2}$.
+$T_{1}$ and~$T_{2}$, is~$3 · 2^{n-2}$.
\end{Corollary}
Let $r(n, k)$ denote the minimum number of transitive subtournaments~$T_{k}$
@@ -1738,7 +1740,7 @@ if $k > [2\log_{2} n] + 1$ and that $r(n, k) > 0$ if $k \leq [\log_{2} n] + 1$.
Let
\[
\tau(n, k) = \begin{cases}
- n · \dfrac{(n - 1)}{2} · \dfrac{(n - 3)}{4} \dots \dfrac{(n - 2^{k-1} + 1)}{2^{k-1}} & \text{if $n > 2^{k-1} - 1$}, \\
+ n · \dfrac{(n - 1)}{2} · \dfrac{(n - 3)}{4} \dots \dfrac{(n - 2^{k-1} + 1)}{2^{k-1}} & \text{if $n > 2^{k-1} - 1$}, \\
0 & \text{if $n \leq 2^{k-1} - 1$}.
\end{cases}
\]
@@ -1829,8 +1831,8 @@ also consider subsets of arcs of a tournament~$T_{n}$ such that these arcs, by
themselves, define no intransitivities. More specifically, we shall call the
arcs in a set~$S$ \emph{consistent} if it is possible to relabel the nodes of~$T_{n}$ in such a
way that, if the arc~$\Arc{p_{j}p_{i}}$ is in~$S$, then $j > i$. (An equivalent definition is that
-$T_{n}$~contains no cycles all of whose arcs belong to~$S$.) Erdös and Moon (1965)
-\index[xauthor]{Erdös, P.}%
+$T_{n}$~contains no cycles all of whose arcs belong to~$S$.) Erdös and Moon (1965)
+\index[xauthor]{Erdös, P.}%
\index[xauthor]{Moon, J. W.}%
gave the following result.
@@ -1838,7 +1840,7 @@ gave the following result.
Let $w(n)$ denote the largest integer~$w$ such that every tournament~$T_{n}$
contains a set of $w$ consistent arcs. Then
\[
-w(n) \geq \left[\frac{n}{2}\right] · \left[\frac{n + 1}{2}\right]
+w(n) \geq \left[\frac{n}{2}\right] · \left[\frac{n + 1}{2}\right]
\quad\text{for all $n$ and }
w(n) \leq \frac{(1 + \eps)}{2} \binom{n}{2}
\]
@@ -1849,29 +1851,29 @@ for any positive~$\eps$ and all sufficiently large~$n$.
there exists at least one node, say~$p_{n}$, whose score is at least~$\left[\dfrac{n}{2}\right]$. We
\index{Score of a node}%
may suppose that the tournament defined by the remaining $n - 1$ nodes
-contains a set~$S$ of at least $\left[\dfrac{n - 1}{2}\right] · \left[\dfrac{n}{2}\right]$ consistent arcs. The arcs in~$S$ and
+contains a set~$S$ of at least $\left[\dfrac{n - 1}{2}\right] · \left[\dfrac{n}{2}\right]$ consistent arcs. The arcs in~$S$ and
the arcs oriented away from~$\Typo{P_{n}}{p_{n}}$ are clearly consistent. Therefore, $T_{n}$~contains
a set of at least
\[
\left[\frac{n}{2}\right]
- + \left[\frac{n - 1}{2}\right] · \left[\frac{n}{2}\right]
- = \left[\frac{n}{2}\right] · \left[\frac{n + 1}{2}\right]
+ + \left[\frac{n - 1}{2}\right] · \left[\frac{n}{2}\right]
+ = \left[\frac{n}{2}\right] · \left[\frac{n + 1}{2}\right]
\]
consistent arcs. The lower bound follows by induction.
We now prove the upper bound. Let $\eps$ be chosen satisfying the inequality
$0 < \eps < 1$. The tournament~$T_{n}$ has $N = \dbinom{n}{2}$ pairs of distinct nodes and
\PageSep{20}
-the nodes can be labeled in $n!$~ways. Hence, there are at most $n! · \dbinom{N}{k}$
+the nodes can be labeled in $n!$~ways. Hence, there are at most $n! · \dbinom{N}{k}$
tournaments~$T_{n}$, whose largest set of consistent arcs contains $k$~arcs. So, an
upper bound for the number of tournaments~$T_{n}$ that contain a set of more
than $\dfrac{(1 + \eps)}{2} N$ consistent arcs is given by
%[** TN: Added line break at second inequality]
\begin{align*}
-n! · \sum_{k > (1 + \eps) N/2} \binom{N}{k}
+n! · \sum_{k > (1 + \eps) N/2} \binom{N}{k}
&< n! N \binom{N}{\bigl[(1 + \eps) N/2\bigr]} \\
&\leq n! N 2^{N} \binom{N}{\bigl[(1 + \eps) N/2\bigr]}
- · \binom{N}{\left[\dfrac{1}{2} N\right]}^{-1}\displaybreak[0] \\
+ · \binom{N}{\left[\dfrac{1}{2} N\right]}^{-1}\displaybreak[0] \\
&= n! N 2^{N}
\frac{\left(N - \left[\dfrac{1}{2}N\right]\right)_{\bigl[(1 + \eps) N/2\bigr] - \left[\dfrac{1}{2}N\right]}}
{\bigl[(1 + \eps) N/2\bigr]_{\bigl[(1 + \eps) N/2\bigr] - \left[\dfrac{1}{2}N\right]}}\displaybreak[0] \\
@@ -1915,8 +1917,8 @@ tournaments. Prove that $z(n) = \left(\dfrac{1}{2} + o(1)\right) \dbinom{n}{2}$.
$m$~pairs of which are joined by a single arc. Let $w = w(n, m)$ denote
the largest integer such that every oriented graph $T(n, m)$ contains a set of $w$
consistent arcs. Prove that $\lim_{n \to \infty} w(n, m)/m = 1/2$, under suitable assumptions
-on the relative rates of growth of $m$~and~$n$. [Erdös and Moon (1965).]
-\index[xauthor]{Erdös, P.}%
+on the relative rates of growth of $m$~and~$n$. [Erdös and Moon (1965).]
+\index[xauthor]{Erdös, P.}%
\index[xauthor]{Moon, J. W.}%
\Ex{5.} Let $u(T_{n})$ denote the least number of arcs possible in a subset~$U$ of the
@@ -1965,8 +1967,8 @@ that every node of~$T^{(j)}$ dominates every node of~$T^{(i)}$ if $1 \leq i < j
Each of these strong subtournaments has a spanning path and these
spanning paths can be combined to yield a path spanning~$T_{n}$.
-The following theorem is a special case of a result proved by Rédei (1934)
-\index[xauthor]{Redei@Rédei, L.}%
+The following theorem is a special case of a result proved by Rédei (1934)
+\index[xauthor]{Redei@Rédei, L.}%
and generalized by Szele (1943).
\index[xauthor]{Szele, T.}%
@@ -1995,7 +1997,7 @@ The determinant of~$M$ will be denoted by~$|M|$.
Let $A_{k}$ denote the matrix obtained from~$A$ by replacing the $k$th~column
by a column of~$1$'s. Set
\[
-S_{k} = \sum_{1 \in e} e(A_{k}) · e'(A_{k}),
+S_{k} = \sum_{1 \in e} e(A_{k}) · e'(A_{k}),
\]
where the sum is over all subsets~$e$ of~$N$ that contain~$1$. (The restriction that
$1 \in e$ merely serves to distinguish between $e$ and~$e'$.) We now show that
@@ -2045,9 +2047,9 @@ subsets~$e$ of~$N$.)
Let $\sum_{k}^{*} e(A_{k})$ denote the sum of~$e(A_{k})$ over all~$k$ such that $k \in e$ with the
convention that an empty sum equals zero. Then,
\begin{align*}
-h &\equiv \sum_{k=1}^{n} \left\{\sum_{1 \in e} e(A_{k}) · e'(A_{k})\right\} \\
- &\equiv \sum_{1 \in e} \left\{\sum_{k \in e} e(A_{k}) \Chg{}{·} e'(A_{k})
- + \sum_{k \not\in e} e(A_{k}) · e'(A_{k})\right\} \\
+h &\equiv \sum_{k=1}^{n} \left\{\sum_{1 \in e} e(A_{k}) · e'(A_{k})\right\} \\
+ &\equiv \sum_{1 \in e} \left\{\sum_{k \in e} e(A_{k}) \Chg{}{·} e'(A_{k})
+ + \sum_{k \not\in e} e(A_{k}) · e'(A_{k})\right\} \\
&\equiv \sum_{1 \in e} \left\{e'(A) {\sum_{k}}^{*} e(A_{k})
+ e(A) {\sum_{k}}^{*} e'(A_{k})\right\}
\Tag{(4)} \\
@@ -2063,7 +2065,7 @@ where the second summation is over all proper subsets $e_{1}$ of~$e$. (If $e$~is
empty set, then both sides equal zero.) If we substitute \Eq{(5)} into~\Eq{(4)}, we find
that
\[
-h \equiv \sum_{e} \sum_{e_{1} \subset e_{1}} e'(A) · e_{1}(A) \pmod{2}.
+h \equiv \sum_{e} \sum_{e_{1} \subset e_{1}} e'(A) · e_{1}(A) \pmod{2}.
\Tag{(6)}
\]
@@ -2252,9 +2254,9 @@ It follows that
\[
t(n) \leq \left\{
\begin{aligned}
-&\dfrac{n^{2}(n - 1)(n - 3)}{8} · \dfrac{(n - 4)^{2}(n - 5)(n - 7)}{8}\dots
+&\dfrac{n^{2}(n - 1)(n - 3)}{8} · \dfrac{(n - 4)^{2}(n - 5)(n - 7)}{8}\dots
\quad\text{if $n$~is odd,} \\
-&\dfrac{(n + 1)n(n - 2)(n - 3)}{8} · \dfrac{(n - 3)(n - 4)(n - 6)(n - 7)}{8}\dots \\
+&\dfrac{(n + 1)n(n - 2)(n - 3)}{8} · \dfrac{(n - 3)(n - 4)(n - 6)(n - 7)}{8}\dots \\
% [** TN: Width-dependent spacing]
&\rule{3in}{0pt}\text{if $n$~is even.}
\end{aligned}
@@ -2309,8 +2311,8 @@ In forming a spanning path of a tournament~$T_{n}$, we may choose the first
$k$ nodes of this path, form a path spanning these $k$~nodes, and then join
this path to a path spanning the remaining $n - k$ nodes. Consequently,
\[
-t(n) \leq \binom{n}{k} t(k) · t(n - k)\quad\text{or}\quad
-\frac{t(n)}{n!} \leq \frac{t(k)}{k!} · \frac{t(n - k)}{(n - k)!}
+t(n) \leq \binom{n}{k} t(k) · t(n - k)\quad\text{or}\quad
+\frac{t(n)}{n!} \leq \frac{t(k)}{k!} · \frac{t(n - k)}{(n - k)!}
\]
for all positive integers $k$ and $n$ with $k < n$. If we let $h(n) = \dfrac{t(n)}{n}$, then
\[
@@ -2369,11 +2371,11 @@ tournament having at least $\left(\dfrac{n}{3e}\right)^{n}$ spanning cycles for
A tournament $T_{n}$ has \emph{property $S(k, m)$}, where $k \leq n$, if for every subset~$A$
\index{Property $S(k, m)$}%
of $k$~nodes there exist at least $m$~nodes~$p$ such that $p$~dominates every node
-of~$A$. In 1962, K.~Schütte raised the question of determining the least
-\index[xauthor]{Schutte@Schütte, K.}%
+of~$A$. In 1962, K.~Schütte raised the question of determining the least
+\index[xauthor]{Schutte@Schütte, K.}%
integer~$n$ such that there exist tournaments~$T_{n}$ with property~$S(k, 1)$, if
-such tournaments exist at all. Erdös (1962) showed that such tournaments
-\index[xauthor]{Erdös, P.}%
+such tournaments exist at all. Erdös (1962) showed that such tournaments
+\index[xauthor]{Erdös, P.}%
do indeed exist and that if the tournament~$T_{n}$ has property~$S(k, 1)$ then
\[
n \geq 2^{k+1} - 1,\quad\text{for $k = 1, 2, \dots$.}
@@ -2441,8 +2443,8 @@ The corollary now follows from \ThmRef{16}.
This corollary is best possible when $k = 2, 3$ (see Exercises 1~and~2) but
it is not known if it is best possible when $k > 3$.
-Erdös (1962) showed that there exist tournaments~$T_{n}$ with property $S(k, 1)$
-\index[xauthor]{Erdös, P.}%
+Erdös (1962) showed that there exist tournaments~$T_{n}$ with property $S(k, 1)$
+\index[xauthor]{Erdös, P.}%
whenever
\[
n > 2^{k} k^{2} \log(2 + \eps)
@@ -2451,8 +2453,8 @@ n > 2^{k} k^{2} \log(2 + \eps)
\PageSep{30}
for any positive~$\eps$, provided that $k$~is sufficiently large. The ideas used in
establishing this and an analogous result for tournaments with property
-$S(k, m)$ are similar to those used in proving the following result due to Erdös
-\index[xauthor]{Erdös, P.}%
+$S(k, m)$ are similar to those used in proving the following result due to Erdös
+\index[xauthor]{Erdös, P.}%
and Moser (1964b).
\index[xauthor]{Moser, L.}%
@@ -2477,7 +2479,7 @@ depend on~$\eps$, such that if $k > K$ and $n > ck^{2}2^{k}$, then
\Proof. Suppose $0 < \eps < 1$. For a particular choice of $A$~and~$B$, there are
\[
-\binom{n - k}{t} (2^{k} - 1)^{n - k - t} · 2^{\ebinom{n}{2}-k(n-k)}
+\binom{n - k}{t} (2^{k} - 1)^{n - k - t} · 2^{\ebinom{n}{2}-k(n-k)}
= 2^{\ebinom{n}{2}} \binom{n - k}{t}
\left(\frac{1}{2^{k}}\right)^{t}
\left(1 - \frac{1}{2^{k}}\right)^{n-k-t}
@@ -2555,8 +2557,8 @@ it turns out that the constant~$c$ may be any quantity greater than~$\log 2$.
\Exercises
\Ex{1.} Let $T_{7}$ denote the tournament in which $p_{i} \to p_{j}$ if and only if $j - i$ is a
-quadratic residue modulo~$7$. Prove that $T_{7}$~has property $S(2, 1)$. [Erdös
-\index[xauthor]{Erdös, P.}%
+quadratic residue modulo~$7$. Prove that $T_{7}$~has property $S(2, 1)$. [Erdös
+\index[xauthor]{Erdös, P.}%
(1962).]
\PageSep{32}
@@ -2567,8 +2569,8 @@ G.~Szekeres (1965).]
\Ex{3.} Prove that if a tournament~$T_{n}$ with property $S(k, 1)$ exists, then a tournament~$T_{r}$
with property $S(k, 1)$ exists whenever $r > n$. [See the remark at the
-end of the second paragraph of Erdös and Moser (1964b).]
-\index[xauthor]{Erdös, P.}%
+end of the second paragraph of Erdös and Moser (1964b).]
+\index[xauthor]{Erdös, P.}%
\index[xauthor]{Moser, L.}%
\Ex{4.} Let $A$ and $B$ denote two disjoint subsets of nodes of a tournament~$T_{n}$
@@ -2674,7 +2676,7 @@ nodes $p_{i}$ and~$p_{j}$. Then
\begin{align*}
0 &\leq \frac{2^{\ebinom{n}{2}} - N(0)}{2^{\ebinom{n}{2}}}
= \frac{N(1) + N(2) + \dots + N\bigl(n(n - 1)\bigr)}{2^{\ebinom{n}{2}}} \\
- &\leq \frac{0 · N(0) + 1 · N(1) + \dots + n(n - 1) · N\bigl(n(n - 1)\bigr)}{2^{\ebinom{n}{2}}}
+ &\leq \frac{0 · N(0) + 1 · N(1) + \dots + n(n - 1) · N\bigl(n(n - 1)\bigr)}{2^{\ebinom{n}{2}}}
= E(n, \lambda).
\end{align*}
\PageSep{34}
@@ -2689,7 +2691,7 @@ and
\]
Therefore,
\[
-\lim_{n \to \infty} \left(1 - N(0) · 2^{-\ebinom{n}{2}}\right) = 0,
+\lim_{n \to \infty} \left(1 - N(0) · 2^{-\ebinom{n}{2}}\right) = 0,
\]
and the corollary is proved.
@@ -3087,9 +3089,9 @@ and it matches players $k$~and~$n$ in round~$r$ if
\]
for $r = 1, 2, \dots, n - 1$. If the $r + 2$ in these congruences is replaced by~$r$,
the only effect on the schedule is that the rounds are numbered differently.
-König (1936, p.~157) gave this construction [see also Freund (1959) and
+König (1936, p.~157) gave this construction [see also Freund (1959) and
\index[xauthor]{Freund, J.}%
-\index[xauthor]{Konig@König, D.}%
+\index[xauthor]{Konig@König, D.}%
Lockwood (1962)]. Slightly different schemes for generating similar schedules
\index[xauthor]{Lockwood, E. H.}%
have also been given by Lockwood (1936), Kraitchik (1950, p.~230),
@@ -3629,8 +3631,8 @@ disjoint copies of all the different tournaments~$T_{n}$ is $n$-universal.)
\[
2^{(1/2)(n-1)} \leq \lambda(n)
\leq \begin{cases}
- n · 2^{(1/2)(n-1)} & \text{if $n$~is odd,} \\
- \dfrac{3}{2\sqrt{2}} n · 2^{(1/2)(n-1)} & \text{if $n$~is even.}
+ n · 2^{(1/2)(n-1)} & \text{if $n$~is odd,} \\
+ \dfrac{3}{2\sqrt{2}} n · 2^{(1/2)(n-1)} & \text{if $n$~is even.}
\end{cases}
\]
\end{Theorem}
@@ -3692,12 +3694,12 @@ for which
\end{align*}
Hence,
\[
-\lambda(n) \leq n · 2^{\Chg{1/2}{(1/2)}(n-1)}\quad\text{if $n$ is odd,}
+\lambda(n) \leq n · 2^{\Chg{1/2}{(1/2)}(n-1)}\quad\text{if $n$ is odd,}
\]
and
\[
-\lambda(n) \leq \nf{1}{2} n · 2^{(1/2)n} + \nf{1}{2} n · 2^{(1/2)(n-2)}
- = \frac{3}{2\sqrt{2}} n · 2^{(1/2)(n-1)},\quad\text{if $n$~is even.}
+\lambda(n) \leq \nf{1}{2} n · 2^{(1/2)n} + \nf{1}{2} n · 2^{(1/2)(n-2)}
+ = \frac{3}{2\sqrt{2}} n · 2^{(1/2)(n-1)},\quad\text{if $n$~is even.}
\]
This completes the proof of the theorem.
@@ -3849,17 +3851,17 @@ arcs. We now apply Lemma~1 again to obtain a special subgraph~$H_{2}$.
(The arcs in~$H_{i}$ need not all be oriented from nodes in~$A_{i}$ to nodes in~$B_{i}$; it
may be that they are all oriented from nodes in~$B_{i}$ to nodes in~$A_{i}$.) We now
disregard the arcs incident with the nodes of~$H_{2}$ and apply Lemma~1 again.
-When we have repeated this procedure $\bigl[\sqrt{n}/(17 · 2^{r+5})\bigr]$ times, we are left with
+When we have repeated this procedure $\bigl[\sqrt{n}/(17 · 2^{r+5})\bigr]$ times, we are left with
a graph that still has more than
\[
-\frac{n^{2}}{2^{2r+13/4}} - \frac{17 n^{3/2}}{2^{r}} \left[\frac{\sqrt{n}}{17 · 2^{r+5}}\right]
+\frac{n^{2}}{2^{2r+13/4}} - \frac{17 n^{3/2}}{2^{r}} \left[\frac{\sqrt{n}}{17 · 2^{r+5}}\right]
> \frac{n^{2}}{2^{2r+4}}
\]
-arcs. If we apply Lemma~1 once more, then the bilevel graph with components~$H_{i}$, $i = 1, 2, \dots, \bigl[\sqrt{n}/(17·2^{r+5})\bigr] + 1$, has at least
+arcs. If we apply Lemma~1 once more, then the bilevel graph with components~$H_{i}$, $i = 1, 2, \dots, \bigl[\sqrt{n}/(17·2^{r+5})\bigr] + 1$, has at least
\[
-\left(\left[\frac{\sqrt{n}}{17 · 2^{r+5}}\right] + 1\right)
- · [\sqrt{n}] · \left[\frac{\log n}{3(r + 3)}\right]
- > \frac{n \log n}{(r + 3) · 2^{r+11}}
+\left(\left[\frac{\sqrt{n}}{17 · 2^{r+5}}\right] + 1\right)
+ · [\sqrt{n}] · \left[\frac{\log n}{3(r + 3)}\right]
+ > \frac{n \log n}{(r + 3) · 2^{r+11}}
\]
arcs. This proves the lemma.
\PageSep{54}
@@ -3906,8 +3908,8 @@ e = e_{1} + e_{2} + \dots + e_{i}
\]
or $t < 4\sqrt{e}$.
-We can now prove the following theorem due to Erdös and Moser (1964a).
-\index[xauthor]{Erdös, P.}%
+We can now prove the following theorem due to Erdös and Moser (1964a).
+\index[xauthor]{Erdös, P.}%
\index[xauthor]{Moser, L.}%
\begin{Theorem}{26.}
@@ -3935,7 +3937,7 @@ e_{i_{r}} \leq \frac{n^{2}}{2^{2r+1}},
then we shall show that
\[
i_{r+1} - i_{r}
- \leq 2^{11} · \frac{r + 3}{2^{r+1}} · \frac{n}{\log n}.
+ \leq 2^{11} · \frac{r + 3}{2^{r+1}} · \frac{n}{\log n}.
\Tag{(3)}
\]
We may suppose that
@@ -3958,7 +3960,7 @@ If we sum this inequality over all~$j$ such that $i_{r} \leq j < i_{r+1}$, we fi
\[
\frac{n^{2}}{2^{2r+1}} \geq e_{i_{r}} - e_{i_{r+1}}
= \sum (e_{j} - e_{j+1})
- \geq (i_{r+1} - i_{r}) · \frac{n \log n}{(r + 3) 2^{r+11}}.
+ \geq (i_{r+1} - i_{r}) · \frac{n \log n}{(r + 3) 2^{r+11}}.
\]
This implies inequality~\Eq{(3)}.
@@ -4024,8 +4026,8 @@ Stearns (1959) showed, by a more complicated construction, that at most
\index[xauthor]{Stearns, R.}%
$n + 2$ voters are necessary to induce any oriented graph~$H_{n}$; he also showed
that at least $\nf{1}{2} \log 3(n/\log n)$ voters are necessary in some cases. This lower
-bound is combined with an upper bound due to Erdös and Moser (1964a)
-\index[xauthor]{Erdös, P.}%
+bound is combined with an upper bound due to Erdös and Moser (1964a)
+\index[xauthor]{Erdös, P.}%
\index[xauthor]{Moser, L.}%
in the following result.
@@ -4769,9 +4771,9 @@ support to this conjecture.
\]
\end{table}
-The following bounds for~$s(n)$ are due to Erdös and Moser.\footnote
+The following bounds for~$s(n)$ are due to Erdös and Moser.\footnote
{Unpublished work.}
-\index[xauthor]{Erdös, P.}%
+\index[xauthor]{Erdös, P.}%
\index[xauthor]{Moser, L.}%
\begin{Theorem}{33.}
@@ -4904,8 +4906,8 @@ U(x) = \frac{1 - \sqrt{1 - 4x}}{2x}
\binom{m}{2} \leq s_{1} + s_{2} + \dots + s_{m}
\leq \binom{m}{2} + m^{3/2}.
\]
-Deduce from this that [Erdös and Moser]:
-\index[xauthor]{Erdös, P.}%
+Deduce from this that [Erdös and Moser]:
+\index[xauthor]{Erdös, P.}%
\index[xauthor]{Moser, L.}%
\[
s(n) > \frac{c_{4} 4^{n}}{n^{9/2}}.
@@ -4953,16 +4955,16 @@ tends to one as $n$~tends to infinity for any positive~$\eps$.
\Proof. If $0 < \eps < 1$, let
\[
-x_{n}^{±} = (1 ± \eps) \sqrt{2\log (n - 1)};
+x_{n}^{±} = (1 ± \eps) \sqrt{2\log (n - 1)};
\]
it follows from~\Eq{(1)} that
\[
-\Erratum{p}{P}\{w_{i} > x_{n}^{±}\}
- \sim \frac{1}{\sqrt{4\pi} (1 ± \eps) \sqrt{\log (n - 1)}}
- · (n - 1)^{-(1 ± \eps)^{2}}.
+\Erratum{p}{P}\{w_{i} > x_{n}^{±}\}
+ \sim \frac{1}{\sqrt{4\pi} (1 ± \eps) \sqrt{\log (n - 1)}}
+ · (n - 1)^{-(1 ± \eps)^{2}}.
\Tag{(2)}
\]
-Let $c_{1}$ and $c_{2}$ be positive constants such that $c_{1} < 1/\sqrt{4\pi} (1 ± \eps) < c_{2}$; if
+Let $c_{1}$ and $c_{2}$ be positive constants such that $c_{1} < 1/\sqrt{4\pi} (1 ± \eps) < c_{2}$; if
the constant factor in~\Eq{(2)} is replaced by $c_{1}$~or~$c_{2}$, strict inequality will hold
for all sufficiently large values of~$n$. Using Boole's inequality, $P \{\cup E_{i}\} \leq \sum P\{E_{i}\}$, we find that
\[
@@ -4973,13 +4975,13 @@ for all sufficiently large values of~$n$.
\PageSep{72}
\iffalse
-% [** Author's note: "B. Bollobás pointed out to me, in a letter dated
+% [** Author's note: "B. Bollobás pointed out to me, in a letter dated
% 12 June, 1980, that this paragraph is incorrect. It may be replaced
% by the succeeding text."]
We now show that
\[
P\{s_{1} < k_{1}, \dots, s_{n} < k_{n}\}
- \leq P\{s_{1} < k_{1}\} · \dotsm · P\{s_{n} < k_{n}\}
+ \leq P\{s_{1} < k_{1}\} · \dotsm · P\{s_{n} < k_{n}\}
\Tag{(4)}
\]
for any positive numbers $k_{1}, \dots, k_{n}$. Observe that
@@ -4999,8 +5001,8 @@ Therefore,
\begin{multline*}
P\{s_{1} < k_{1}, \dots, s_{n} < k_{n}\} \\
\leq \sum_{t<k_{1}} \binom{n - 1}{t} \left(\frac{1}{2}\right)^{t}
- \left(\frac{1}{2}\right)^{n-1-t} · P\{\Typo{s_{1}}{s_{2}} < k_{2}, \dots, s_{n} < k_{n}\} \\
- = P\{s_{1} < k_{1}\} · P\{s_{2} < k_{2}, \dots, s_{n} < k_{n}\}.
+ \left(\frac{1}{2}\right)^{n-1-t} · P\{\Typo{s_{1}}{s_{2}} < k_{2}, \dots, s_{n} < k_{n}\} \\
+ = P\{s_{1} < k_{1}\} · P\{s_{2} < k_{2}, \dots, s_{n} < k_{n}\}.
\end{multline*}
This argument can be repeated to yield inequality~\Eq{(4)}.
\fi
@@ -5009,7 +5011,7 @@ This argument can be repeated to yield inequality~\Eq{(4)}.
We now show that
\[
P\{s_{1} < k_{1}, \dots, s_{n} < k_{n}\}
- \leq P\{s_{1} < k_{1}\} · \dotsm · P\{s_{n} < k_{n}\}
+ \leq P\{s_{1} < k_{1}\} · \dotsm · P\{s_{n} < k_{n}\}
\Tag{(4)}
\]
for any positive integers $k_{1}, \dots, k_{n}$, where $s_{i} = \sum_{j \neq i} a_{ij}$,
@@ -5042,10 +5044,10 @@ P\{s_{1h} < k_{1} - c_{12}, s_{2h} < k_{2} - c_{21}, s_{3}^{(h)} < k_{3}, \dots\
\]
and
\[
-P\{b_{12} = c_{12}\} · P\{b_{21} = c_{21}\} - P\{a_{12} = c_{12}, a_{21} = c_{21}\}
+P\{b_{12} = c_{12}\} · P\{b_{21} = c_{21}\} - P\{a_{12} = c_{12}, a_{21} = c_{21}\}
\]
over all integers $c_{12}$ and $c_{21}$ such that $0 \leq c_{12}, c_{21} \leq 1$. Now
-$P\{b_{12} = c_{12}\} · P\{b_{21}=c_{21}\} = 1/4$ for all such $c_{12}$ and~$c_{21}$; and
+$P\{b_{12} = c_{12}\} · P\{b_{21}=c_{21}\} = 1/4$ for all such $c_{12}$ and~$c_{21}$; and
$P\{a_{12} = c_{12}, a_{21} = c_{21}\}$ equals $\nf{1}{2}$~or $0$ according as $c_{12} + c_{21}$
does or does not equal~$1$. Therefore
\begin{align*}
@@ -5290,7 +5292,7 @@ hold for the scores of the nodes of~$T$:
\begin{align*}
s(g) &= (1 + 2 + \dots + h)h
+ \nf{1}{2} (n - 2h - 1) \bigl[(1 + 2 + \dots + h) + 1\bigr] \\
- &= \nf{1}{2} (n - 1) · \binom{h + 1}{2} + \nf{1}{2} (n - 2h - 1)
+ &= \nf{1}{2} (n - 1) · \binom{h + 1}{2} + \nf{1}{2} (n - 2h - 1)
\end{align*}
for each node~$g$ associated with an element of~$G$;
\[
@@ -5401,8 +5403,8 @@ Prove that $t(G) \leq n$ if $G$~is abelian.
tournament~$T_{n}$ such that $G(T_{n})$~is the identity group?
\Ex{8.} Construct a nontransitive infinite tournament~$T$ such that $G(T)$~is the
-identity group. [See Chvátal (1965).]
-\index[xauthor]{Chvátal, V.}%
+identity group. [See Chvátal (1965).]
+\index[xauthor]{Chvátal, V.}%
\Section[Group of the Composition of Two Tournaments]
@@ -5420,9 +5422,9 @@ if and only if $r_{i} \to r_{j}$, or $i = j$ and $t_{k} \to t_{l}$. The composit
illustrated in \Figure{13}.
Let $F$ and~$H$ denote two permutation groups with object sets $U$ and~$V$.
-The \emph{composition} [see Pólya (1937)] of $F$ with~$H$ is the group $F \circ H$ of all
-\index[xauthor]{Polya@Pólya, G.}%
-permutations~$\alpha$ of $U × V = \{(x, y) : x \in U, y \in V\}$ of the type
+The \emph{composition} [see Pólya (1937)] of $F$ with~$H$ is the group $F \circ H$ of all
+\index[xauthor]{Polya@Pólya, G.}%
+permutations~$\alpha$ of $U × V = \{(x, y) : x \in U, y \in V\}$ of the type
\[
\alpha(x, y) = \bigl(f(x), h_{x}(y)\bigr),
\]
@@ -5433,7 +5435,7 @@ permutations~$\alpha$ of $U × V = \{(x, y) : x \in U, y \in V\}$ of the type
\FCaption{Figure 13}
\end{figure}
where $f$~is any element of~$F$ and $h_{x}$, for each~$x$, is any element of~$H$. If
-the objects of $U × V$ are arranged in a matrix so that the rows and columns
+the objects of $U × V$ are arranged in a matrix so that the rows and columns
correspond to the objects of $U$~and $V$, respectively, then $F \circ H$ is the
group of permutations obtained by permuting the objects in each row
according to some element of~$H$ (not necessarily the same element for
@@ -5488,12 +5490,12 @@ We next suppose that alternatives (1a) and (2b) hold. The score of any
\index{Score of a node}%
node~$p(i, k)$ in~$R \circ T$ is given by the formula
\[
-s\bigl(p(i, k)\bigr) = s(t_{k}) + b · s(r_{i}),
+s\bigl(p(i, k)\bigr) = s(t_{k}) + b · s(r_{i}),
\]
where $s(t_{k})$ and~$s(r_{i})$ denote the scores of $t_{k}$ and~$r_{i}$ in $T$~and~$R$. It follows
that if $\alpha\bigl(p(i, k)\bigr) - p(j, l)$ then $s(t_{k}) = s(t_{l})$, since
\[
-s(t_{k}) + b · s(r_{i}) = s(t_{l}) + b · s(r_{j})
+s(t_{k}) + b · s(r_{i}) = s(t_{l}) + b · s(r_{j})
\]
and $0 \leq s(t_{k}), s(t_{l}) < b$. Consequently,
\[
@@ -5607,7 +5609,7 @@ into classes of equivalent elements.
\begin{Theorem}{38.}
If $x \in X$, let $E(x) = \{\alpha(x) : \alpha \in G\}$ and $F(x) = \{\gamma : \gamma \in G \text{ and } \gamma(x) = x\}$. Then
\[
-|G| = |E(x)| · |F(x)|.
+|G| = |E(x)| · |F(x)|.
\]
\end{Theorem}
\PageSep{82}
@@ -5637,7 +5639,7 @@ for all elements~$y$ in $E = E(x)$. Therefore,
|G| = \sum_{y \in E} g(x, y)
= \sum_{y \in E} g(y, y)
= g(x, x) \sum_{y \in E} 1
- = |F(x)| · |E(x)|,
+ = |F(x)| · |E(x)|,
\]
since each element of~$G$ is counted once and only once in the first sum.
@@ -5663,25 +5665,25 @@ If $T_{e}$ and $T_{n-e}$ denote the subtournaments determined by the nodes that
\index{Subtournament}%
in~$E$ and by the nodes that are not in~$E$, then it is clear that
\[
-g(T_{n}) \leq g(T_{e}) · g(T_{n-e}) \leq g(e) · g(n - e).
+g(T_{n}) \leq g(T_{e}) · g(T_{n-e}) \leq g(e) · g(n - e).
\Tag{(3)}
\]
If $3 < e < n - 3$, then it follows from the induction hypothesis that
\[
-g(T_{n}) \leq \frac{(2.5)^{e}}{2e} · \frac{(2.5)^{n-e}}{2(n - e)}
- \leq \frac{n}{8(n - 4)} · \frac{(2.5)^{n}}{2n}
+g(T_{n}) \leq \frac{(2.5)^{e}}{2e} · \frac{(2.5)^{n-e}}{2(n - e)}
+ \leq \frac{n}{8(n - 4)} · \frac{(2.5)^{n}}{2n}
< \frac{(2.5)^{n}}{2n}.
\]
If $e = 3$ or $n - 3$, then
\[
-g(T_{n}) \leq 3 · \frac{(2.5)^{n-3}}{2(n - 3)}
+g(T_{n}) \leq 3 · \frac{(2.5)^{n-3}}{2(n - 3)}
< \frac{(2.5)^{n}}{2n},
\]
\PageSep{83}
and if $e = 1$, $2$, $n - 2$, or~$n - 1$, then
\[
-g(T_{n}) \leq 1 · \frac{2n}{5(n - 2)} · \frac{(2.5)^{n}}{2n}
+g(T_{n}) \leq 1 · \frac{2n}{5(n - 2)} · \frac{(2.5)^{n}}{2n}
< \frac{(2.5)^{n}}{2n}.
\]
A different argument must be used when $e = n$.
@@ -5704,7 +5706,7 @@ into one of the $\nf{1}{2}(n - 1)$ nodes dominated by~$p$, since $p$~is fixed. H
Therefore, if $e = n$, then
\[
g(T_{n}) \leq n\left(\frac{(2.5)^{(1/2)(n-1)}}{n - 1}\right)^{2}
- = \frac{4}{5} \left(\frac{n}{n - 1}\right)^{2} · \frac{(2.5)^{n}}{2n}
+ = \frac{4}{5} \left(\frac{n}{n - 1}\right)^{2} · \frac{(2.5)^{n}}{2n}
< \frac{(2.5)^{n}}{2n}.
\]
(Notice that $\nf{1}{2} (n - 1) \geq 5$ if $n \geq 11$, so we are certainly entitled to apply
@@ -5774,7 +5776,7 @@ limit is~$\sqrt{3}$; see Exercise~5.)
\Exercises
-\Ex{1.} Prove that $g(n) = \max \{g(d) · g(n - d)\}$, $d = 1, 3, 5, \dots, n - 1$, if $n$~is
+\Ex{1.} Prove that $g(n) = \max \{g(d) · g(n - d)\}$, $d = 1, 3, 5, \dots, n - 1$, if $n$~is
even.
\Ex{2.} Verify the entries in \Table{6} when $7 \leq n \leq 11$.
@@ -5785,7 +5787,7 @@ even.
nodes that are equivalent with respect to~$G(T_{n})$. Under what circumstances
is it true that
\[
-g(T_{n}) = g(T_{a}) · g(T_{b}) \dots?
+g(T_{n}) = g(T_{a}) · g(T_{b}) \dots?
\]
\Ex{4.} Let $h(n)$ denote the order of any largest subgroup~$H$ of odd order of the
@@ -5804,10 +5806,10 @@ derive a result due to Burnside (1911, p.~191) that is used in dealing with a
\index[xauthor]{Burnside, W.}%
\PageSep{85}
general class of enumeration problems. A theory of enumeration has been
-developed by Pólya (1937) and de~Bruijn (1964); Harary (1964) has given a
+developed by Pólya (1937) and de~Bruijn (1964); Harary (1964) has given a
\index[xauthor]{Debruijn@de Bruijn, N. G.}%
\index[xauthor]{Harary, F.}%
-\index[xauthor]{Polya@Pólya, G.}%
+\index[xauthor]{Polya@Pólya, G.}%
summary of results on the enumeration of graphs.
\begin{Theorem}{40.}
@@ -5856,7 +5858,7 @@ of~$\pi$ contains $d_{k}$~cycles of length~$k$, for $k = 1, 2, \dots, n$, then $
\]
is of type $(2, 1, 1, 0, 0, 0, 0)$. Notice that
\[
-1 · d_{1} + 2 · d_{2} + \dots + n · d_{n} = n.
+1 · d_{1} + 2 · d_{2} + \dots + n · d_{n} = n.
\]
In the present context, we think of the permutations~$\pi$ as acting on the
@@ -5929,7 +5931,7 @@ T(n) = \sum_{(d)} \frac{2^{D}}{N},
where $D$ and~$N$ are as defined in \Eq{(1)} and~\Eq{(2)} and where the sum is over all
solutions~$(d)$ in nonnegative integers of the equation
\[
-1 · d_{1} + 3 · d_{3} + 5 · d_{5} + \dots = n.
+1 · d_{1} + 3 · d_{3} + 5 · d_{5} + \dots = n.
\]
\end{Theorem}
@@ -5941,13 +5943,13 @@ calculations may be summarized as follows.
\hline\Strut
d_{1} = 6 & 6! & 15 \\
\hline\Strut
-d_{1} = 3,\ d_{3} = 1 & 3 · 3! & 7 \\
+d_{1} = 3,\ d_{3} = 1 & 3 · 3! & 7 \\
\hline\Strut
d_{1} = 1,\ d_{5} = 1 & 5 & 3 \\
\hline\Strut
-d_{3} = 2 & 2 · 3^{2} & 5
+d_{3} = 2 & 2 · 3^{2} & 5
\end{array}\displaybreak[0] \\
-T(6) = \frac{2^{15}}{6!} + \frac{2^{7}}{3 · 3!} + \frac{2^{3}}{5} + \frac{2^{5}}{2 · 3!} = 56.
+T(6) = \frac{2^{15}}{6!} + \frac{2^{7}}{3 · 3!} + \frac{2^{3}}{5} + \frac{2^{5}}{2 · 3!} = 56.
\end{gather*}
The values of~$T(n)$ for $n = 1, 2, \dots, 12$ are given in \Table{7}; the first eight
@@ -5983,16 +5985,16 @@ $T(n) \sim \dfrac{2^{\ebinom{n}{2}}}{n!}$ as $n$~tends to infinity.
\Proof. The two largest terms in the formula for~$T(n)$ are
\[
\frac{2^{\ebinom{n}{2}}}{n!}\quad\text{and}\quad
-\frac{2^{\ebinom{n}{2} - 2(n-2)}}{3 · (n - 3)!};
+\frac{2^{\ebinom{n}{2} - 2(n-2)}}{3 · (n - 3)!};
\]
they arise from permutations of type $(n, 0, \dots, 0)$ and $(n - 3, 1, 0, \dots, 0)$.
(See Exercise~3.) The number of terms in the formula is equal to the number
-of partitions of~$n$ into odd integers. Erdös (1942)\index[xauthor]{Erdös, P.} has shown that the total
+of partitions of~$n$ into odd integers. Erdös (1942)\index[xauthor]{Erdös, P.} has shown that the total
number of partitions of~$n$ is less than $2^{cn^{1/2}}$, where $c = \pi(\nf{2}{3})^{1/2} \log_{2} e$. Hence,
\[
\frac{2^{\ebinom{n}{2}}}{n!} \leq T(n)
\leq \frac{2^{\ebinom{n}{2}}}{n!}
- + 2^{cn^{1/2}} · \frac{2^{\ebinom{n}{2} - 2(n-2)}}{3 · (n - 3)!}
+ + 2^{cn^{1/2}} · \frac{2^{\ebinom{n}{2} - 2(n-2)}}{3 · (n - 3)!}
= \frac{2^{\ebinom{n}{2}}}{n!} \bigl(1 + o(1)\bigr).
\]
@@ -6008,7 +6010,7 @@ number of partitions of~$n$ is less than $2^{cn^{1/2}}$, where $c = \pi(\nf{2}{3
\Ex{4.} Prove that
\[
T(n) = \frac{\Erratum{2^{\ebinom{2}{n}}}{2^{\ebinom{n}{2}}}}{n!}
- + \frac{2^{(1/2)(n^{2} - 5n + 8)}}{3 · (n - 3)!} \bigl(1 + o(1)\bigr).
+ + \frac{2^{(1/2)(n^{2} - 5n + 8)}}{3 · (n - 3)!} \bigl(1 + o(1)\bigr).
\]
\Ex{5.} Let $t(n)$ denote the number of nonisomorphic strong tournaments~$T_{n}$.
@@ -6036,14 +6038,14 @@ graphs with $n$~nodes is given by the formula
\PageSep{89}
the sum is over all solutions~$(d)$ in nonnegative integers to the equation
\[
-1 · d_{1} + 2 · d_{2} + \dots + n · d_{n} = n,
+1 · d_{1} + 2 · d_{2} + \dots + n · d_{n} = n,
\]
and
\[
F = \frac{1}{2} \left\{
\sum_{k,l=1}^{n} d_{k}d_{l}(k, l)
- \sum_{k \text{ odd}} d_{k}
- - 2 · \sum_{k \text{ even}} d_{k}\right\}.
+ - 2 · \sum_{k \text{ even}} d_{k}\right\}.
\]
[See Harary (1957).]
\index[xauthor]{Harary, F.}%
@@ -6118,7 +6120,7 @@ understood that the arc is oriented from the higher node to the lower node.
\AppFig{app_033333}{(0, 3, 3, 3, 3, 3)}{144}{C_{5}} \\
%
\AppFig{app_111345}{(1, 1, 1, 3, 4, 5)}{240}{C_{3}}
-\AppFig{app_111444}{(1, 1, 1, 4, 4, 4)}{80}{C_{3} × C_{3}}
+\AppFig{app_111444}{(1, 1, 1, 4, 4, 4)}{80}{C_{3} × C_{3}}
\AppFig{app_112245}{(1, 1, 2, 2, 4, 5)}{720}{I}
\AppFig{app_112335a}{(1, 1, 2, 3, 3, 5)}{720}{I} \\
%
@@ -6248,8 +6250,8 @@ Acad.\ Sci.}\ Paris \Vol{249}, 2151--2152.
\Bibitem J.~S.~R. Chisholm (1948). A tennis problem. \Title{Eureka} \Vol{10},~18.
\index[xauthor]{Chisholm, J. S. R.}%
-\Bibitem V.~Chvátal, (1965). On finite and countable rigid graphs and tournaments. \Title{Comment.\
-\index[xauthor]{Chvátal, V.}%
+\Bibitem V.~Chvátal, (1965). On finite and countable rigid graphs and tournaments. \Title{Comment.\
+\index[xauthor]{Chvátal, V.}%
Math.\ Univ.\ Carolinae} \Vol{6}, 429--438.
\Bibitem J.~S. Coleman (1960). The mathematical study of small groups. In \Title{Mathematical
@@ -6295,8 +6297,8 @@ Math.\ Bull.}\ \Vol{10}, 503--505.
of Alberta Preprint Series, Edmonton. In \Title{Graph Theory and Theoretical Physics}
(F.~Harary, ed.). London: Academic Press, 1967, 167--227.
-\Bibitem \index[xauthor]{Erdös, P.|(}%
-P.~Erdös (1942). On an elementary proof of some asymptotic formulas in the theory
+\Bibitem \index[xauthor]{Erdös, P.|(}%
+P.~Erdös (1942). On an elementary proof of some asymptotic formulas in the theory
of partitions. \Title{Ann.\ of Math.}\ \Vol{43}, 437--450.
\Bibitem \Same\ (1963). On a problem in graph theory. \Title{Math.\ Gazette} \Vol{47}, 220--223.
@@ -6312,9 +6314,9 @@ of orderings. \Title{Publ.\ Math.\ Inst.\ Hung.\ Acad.\ Sci.}\ \Vol{9}, 125--132
\Bibitem \Same, and J.~W. Moon (1965). On sets of consistent arcs in a tournament,
\index[xauthor]{Moon, J. W.}%
\Title{Canad.\ Math.\ Bull.}\ \Vol{8}, 269--271.
-\index[xauthor]{Erdös, P.|)}%
+\index[xauthor]{Erdös, P.|)}%
-\Bibitem M.~Fekete (1923). Über die Verteilung der Wurzeln bei gewissen algebraischen
+\Bibitem M.~Fekete (1923). Ãœber die Verteilung der Wurzeln bei gewissen algebraischen
\index[xauthor]{Fekete, M.}%
Gleichungen mit ganzzahligen Koeffizienten. \Title{Math.\ Zeit.}\ \Vol{17}, 228--249.
@@ -6322,8 +6324,8 @@ Gleichungen mit ganzzahligen Koeffizienten. \Title{Math.\ Zeit.}\ \Vol{17}, 228-
\index[xauthor]{Feller, W.}%
York: Wiley.
-\Bibitem A.~Fernández De~Trocóniz (1966). Caminos y circuitos halmitonianos en gráfos
-\index[xauthor]{Fernández de Troconiz, A.}%
+\Bibitem A.~Fernández De~Trocóniz (1966). Caminos y circuitos halmitonianos en gráfos
+\index[xauthor]{Fernández de Troconiz, A.}%
fuertemente conexos. \Title{Trabajos Estadist.}\ \Vol{17}, 17--32.
\Bibitem L.~R. Ford,~Jr. (1957). Solution of a ranking problem from binary comparisons.
@@ -6345,7 +6347,7 @@ Math.\ Providence, Amer.\ Math.\ Soc.}\ \Vol{10}, 231--289.
\Bibitem J.~Freund (1959). Round robin mathematics. \Title{Amer.\ Math.\ Monthly} \Vol{63}, 112--114.
\index[xauthor]{Freund, J.}%
-\Bibitem G.~Frobenius (1912). Über Matrizen aus nicht negativen Elementen. \Title{S.~B. Preuss.\
+\Bibitem G.~Frobenius (1912). Ãœber Matrizen aus nicht negativen Elementen. \Title{S.~B. Preuss.\
\index[xauthor]{Frobenius, G.}%
Akad.\ Wiss., Berlin} \Vol{23}, 456--477.
@@ -6366,7 +6368,7 @@ with multiple edges. \Title{Canad.\ J. Math.}\ \Vol{17}, 166--177.
\Bibitem T.~Gallai, and A.~N. Milgram (1960). Verallgemeinerung eines graphentheoretischen
\index[xauthor]{Gallai, T.}%
\index[xauthor]{Milgram, A. N.}%
-Satzes von Rédei. \Title{Acta Sci.\ Math \(Szeged\)} \Vol{21}, 181--186.
+Satzes von Rédei. \Title{Acta Sci.\ Math \(Szeged\)} \Vol{21}, 181--186.
\PageSep{98}
\Bibitem E.~N. Gilbert (1961). Design of mixed doubles tournaments. \Title{Amer.\ Math.\ Monthly}
@@ -6415,7 +6417,7 @@ from subtournaments. \Title{Monatsh.\ Math.}\ \Vol{71}, 14--23.
\index[xauthor]{Hartigan, J. A.}%
Math.\ Statist.}\ \Vol{37}, 495--503.
-\Bibitem M.~Hasse (1961). Über die Behandlung graphentheoretischer Probleme unter
+\Bibitem M.~Hasse (1961). Ãœber die Behandlung graphentheoretischer Probleme unter
\index[xauthor]{Hasse, M.}%
Verwendung der Matrizenrechnung. \Title{Wiss.\ Z.~Tech.\ Univ.\ Dresden.}\ \Vol{10}, 1313--1316.
@@ -6461,11 +6463,11 @@ Mat.\ Meh.\ Astronom.}\ \Vol{18}, 143--145.
comparison. \Title{Sibirsk.\ Mat.\ \v{Z}.} \Vol{5}, 557--564.
\PageSep{99}
-\Bibitem D.~König (1936). \Title{Theorie der endlichen und unendlichen Graphen.} New York:
-\index[xauthor]{Konig@König, D.}%
+\Bibitem D.~König (1936). \Title{Theorie der endlichen und unendlichen Graphen.} New York:
+\index[xauthor]{Konig@König, D.}%
Chelsea.
-\Bibitem G.~Korvin (1966). On a theorem of L.~Rédei about complete oriented graphs. \Title{Acta.\
+\Bibitem G.~Korvin (1966). On a theorem of L.~Rédei about complete oriented graphs. \Title{Acta.\
\index[xauthor]{Korvin, G.}%
Sci.\ Math.}\ \Vol{27}, 99--103.
@@ -6476,7 +6478,7 @@ York: Academic Press,~162.
\Bibitem \Same\ (1966). Cycles in a complete graph oriented in equilibrium. \Title{Mat.-Fyz.\
\v{C}asopis.}\ \Vol{16}, 175--182.
-\Bibitem \Same\ (1966). O $\delta$-transformáciách antisymetrických grafov. \Title{Mat.-Fyz.\ \v{C}asopis.}\
+\Bibitem \Same\ (1966). O $\delta$-transformáciách antisymetrických grafov. \Title{Mat.-Fyz.\ \v{C}asopis.}\
\Vol{16}, 353--356.
\Bibitem M.~Kraitchik (1954). \Title{Mathematical Recreations.} New York, Dover.
@@ -6558,8 +6560,8 @@ comparisons. \Title{Pac.~J. Math.}\ \Vol{21}, 531--535.
\Bibitem O.~Ore (1963). \Title{Graphs and Their Uses.} New York: Random House.
\index[xauthor]{Ore, O.}%
-\Bibitem G.~Pólya (1937). Kombinatorische Anzahlbestimmungen für Gruppen, Graphen
-\index[xauthor]{Polya@Pólya, G.}%
+\Bibitem G.~Pólya (1937). Kombinatorische Anzahlbestimmungen für Gruppen, Graphen
+\index[xauthor]{Polya@Pólya, G.}%
und chemische Verbindungen. \Title{Acta.\ Math.}\ \Vol{68}, 145--254.
\Bibitem R.~Rado (1943). Theorems on linear combinatorial topology and general measure.
@@ -6572,10 +6574,10 @@ und chemische Verbindungen. \Title{Acta.\ Math.}\ \Vol{68}, 145--254.
\index[xauthor]{Ramanujacharyula, C.}%
\Vol{29}, 257--261.
-\Bibitem L.~Rédei (1934). Ein kombinatorischer Satz. \Title{Acta.\ Litt.\ Szeged.}\ \Vol{7}, 39--43.
-\index[xauthor]{Redei@Rédei, L.}%
+\Bibitem L.~Rédei (1934). Ein kombinatorischer Satz. \Title{Acta.\ Litt.\ Szeged.}\ \Vol{7}, 39--43.
+\index[xauthor]{Redei@Rédei, L.}%
-\Bibitem M.~Reisz (1859). Über eine Steinersche kombinatorische Aufgabe welche in 45sten
+\Bibitem M.~Reisz (1859). Ãœber eine Steinersche kombinatorische Aufgabe welche in 45sten
\index[xauthor]{Reisz, M.}%
Bande dieses Journals, Seite~181, gestellt worden ist. \Title{J.~Reine.\ Angew.\ Math.}\
\Vol{56}, 326--344.
@@ -6588,11 +6590,11 @@ Bande dieses Journals, Seite~181, gestellt worden ist. \Title{J.~Reine.\ Angew.\
\Bibitem \Same, and \Same\ (1966). Maximum likelihood paired comparison rankings.
\Title{Biometrika} \Vol{53}, 143--149.
-\Bibitem B.~Roy (1958). Sur quelques propriétes des graphes fortement connexes. C. R.
+\Bibitem B.~Roy (1958). Sur quelques propriétes des graphes fortement connexes. C. R.
\index[xauthor]{Roy, B.}%
\Title{Acad.\ Sci.\ Paris} \Vol{247}, 399--401.
-\Bibitem \Same\ (1959). Transitivité et connexité. \Title{C.~R. Acad.\ Sci.\ Paris} \Vol{249}, 216--218.
+\Bibitem \Same\ (1959). Transitivité et connexité. \Title{C.~R. Acad.\ Sci.\ Paris} \Vol{249}, 216--218.
\Bibitem H.~J. Ryser (1957). Combinatorial properties of matrices of zeros and ones. \Title{Canad.~J.
\index[xauthor]{Ryser, H. J.}%
@@ -6641,22 +6643,22 @@ Vol.\ (1958/1959), Calcutta: \Title{Calcutta Math.\ Soc.}\ 323--327.
\index[xauthor]{Trybula, S.}%
Acad.\ Polon.\ Sci.}\ \Vol{7}, 67--69.
-\Bibitem E.~and G.~Szekeres (1965). On a problem of Schütte and Erdös. \Title{Math.\ Gazette} \Vol{49},
+\Bibitem E.~and G.~Szekeres (1965). On a problem of Schütte and Erdös. \Title{Math.\ Gazette} \Vol{49},
\index[xauthor]{Szekeres, E. and G.}%
290--293,
-\Bibitem T.~Szele (1943). Kombinatorikai vizsgálatok az irányított teljes gráffal kapcsolatban.
+\Bibitem T.~Szele (1943). Kombinatorikai vizsgálatok az irányított teljes gráffal kapcsolatban.
\index[xauthor]{Szele, T.}%
\Title{Mat.\ Fiz.\ Lapok.}\ \Vol{50}, 223--256. For a German translation, see Kombinatorische
\PageSep{101}
-Untersuchungen über gerichtete vollständige graphen. \Title{Publ.\ Math.\ Debrecen.}\
+Untersuchungen über gerichtete vollständige graphen. \Title{Publ.\ Math.\ Debrecen.}\
\Vol{13} (1966) 145--168.
\Bibitem G.~L. Thompson (1958). Lectures on game theory, Markov chains and related
\index[xauthor]{Thompson, G. L.}%
topics. \Title{Sandia Corporation Monograph} SCR-11.
-\Bibitem H.~Tietze (1957). Über Schachturnier-Tabellen. \Title{Math.\ Zeit.}\ \Vol{67}, 188--202.
+\Bibitem H.~Tietze (1957). Ãœber Schachturnier-Tabellen. \Title{Math.\ Zeit.}\ \Vol{67}, 188--202.
\index[xauthor]{Tietze, H.}%
\Bibitem S.~Trybula (1961). On the paradox of three random variables. \Title{Zastos.\ Mat.}\ \Vol{5},
@@ -6732,7 +6734,7 @@ Cayley, A.#Cayley 75, 96
Chisholm, J. S. R.#Chisholm 49, 96
-Chvátal, V.#Chvátal 78, 96
+Chvátal, V.#Chvátal 78, 96
Clark, A. H.#Clark 9
@@ -6752,13 +6754,13 @@ Dixon, J. D.#Dixon 84, 97
Dulmage, A. L.#Dulmage 35, 97
-Erdös, P.#Erdös 15, 16, 19, 21, 28, 29, 30, 31, 32, 54, 56, 68, 70, 88, 97
+Erdös, P.#Erdös 15, 16, 19, 21, 28, 29, 30, 31, 32, 54, 56, 68, 70, 88, 97
Fekete, M.#Fekete 27, 97
Feller, W.#Feller 33, 71, 97
-Fernández de Troconiz, A.#Fernández 7, 97
+Fernández de Troconiz, A.#Fernández 7, 97
Ford, L. R., Jr.#Ford 43, 44, 47, 48, 64, 97
@@ -6806,7 +6808,7 @@ Kendall, M. G.#Kendall 1, 9, 11, 12, 40, 44, 45, 46, 98
Kislicyn, S. S.#Kislicyn 48, 98
-Konig@König, D.#König 40, 99
+Konig@König, D.#König 40, 99
Korvin, G.#Korvin 24, 28, 99
@@ -6849,7 +6851,7 @@ Palmer, E. M.#Palmer 4, 98
Plott, C. R.#Plott 57, 97
-Polya@Pólya, G.#Pólya 78, 85, 100
+Polya@Pólya, G.#Pólya 78, 85, 100
Pullman, N. J.#Pullman 35, 65, 99
@@ -6857,7 +6859,7 @@ Rado, R.#Rado 5, 51, 100
Ramanujacharyula, C.#Ramanujacharyula 46, 100
-Redei@Rédei, L.#Rédei 21, 100
+Redei@Rédei, L.#Rédei 21, 100
Reisz, M.#Reisz 39, 40, 41, 100
@@ -6877,7 +6879,7 @@ Scheid, F.#Scheid 40, 42, 100
Schreier, J.#Schreier 48, 100
-Schutte@Schütte, K.#Schütte 28
+Schutte@Schütte, K.#Schütte 28
Silverman, D. L.#Silverman 63, 100
generated by cgit v1.2.3 (git 2.25.1) at 2026-03-26 10:02:26 +0000