The span $\lambda$ (G) of a graph G is the smallest k for which G's vertices can be L(2,1)-colored, i.e., colored with integers in $\{0,1, \ldots, k \}$ so that adjacent vertices' colors differ by at least 2, and colors of vertices at distance two differ. G is full-colorable if some such coloring uses all colors in $\{0,1, \ldots, \lambda (G) \}$ and no others. We prove that all trees except stars are full-colorable. The connected graph G with the smallest number of vertices exceeding $\lambda$ (G) which is not full-colorable is C6. We describe an array of other connected graphs that are not full-colorable and go into detail on full-colorability of graphs of maximum degree four or less.

Let ${\cal G}_d (n)$ be the set of d-regular simple graphs with n vertices, and for $G = (V,E)$ in ${\cal G}_d (n)$ let $f: V \to \{1,2, \ldots, n \}$ be a bijective coloring of the vertices of G. Also let $\alpha$ denote an interference parameter in $\{0,1, \ldots, n-1 \}$, and define the interference number of f with respect to G and $\alpha$ as the number of edges $\{u,v\}$ in E for which $\min \{ | f(u) - f(v) |$, $n- | f(u) - f(v) | \} \le \alpha$. We consider two interference number problems for feasible $(n, \alpha, d)$. The first is to specify a $G \in {\cal G}_d (n)$ and an f for which the interference number is as small as possible. The second is to determine a $G \in {\cal G}_d (n)$ whose minimum interference number over all f is as large as possible. A previous paper completely solves both problems for d = 2. The present paper solves the first problem for all $d \ge 3$ and obtains partial results for the second problem for $d \ge 3$ that focus on interference-minimizing f's when G consists of disjoint copies of $K_{d+1}$.

This paper investigates how closely randomly generated binary source sequences can be matched by convolutional code codewords. What distinguishes it from prior work is that a randomly chosen subsequence with density /spl lambda/ is to be matched as closely as possible. The so-called marked bits of the subsequence could indicate overload quantization points for a source sample generated from the tails of a probability distribution. They might also indicate bits where the initial estimate is considered reliable, as might happen in iterated decoding. The capacity of a convolutional code to interpolate the marked subsequence might be viewed as a measure of its ability to handle overload distortion. We analyze this capacity using a Markov chain whose states are sets of subsets of trellis vertices of the convolutional code. We investigate the effect of memory on the probability of perfect interpolation and calculate the residual rate on the unmarked bits of the binary source sequence. We relate our interpolation methodology to sequence-based methods of quantization and use it to analyze the performance of convolutional codes on the pure erasure channel.

Communications problems that involve frequency interference, such as the channel assignment problem in the design of cellular telephone networks, can be cast as graph coloring problems in which the frequencies (colors) assigned to an edge's vertices interfere if they are too similar. The paper considers situations modeled by vertex-coloring d-regular graphs with n vertices using a color set 1, 2,..., n, where colors i and j are said to interfere if their circular distance $\min \{ | i-j | , n- | i-j | \}$ does not exceed a given threshold value $\alpha$. Given a d-regular graph G and threshold $\alpha$, an interference-minimizing coloring is a coloring of vertices that minimizes the number of edges that interfere. Let $I_\alpha (G)$ denote the minimum number of interfering edges in such a coloring of G. For most triples $(n, \alpha ,d),$ we determine the minimum value of $I_\alpha (G)$ over all d-regular graphs and find graphs that attain it. In determining when this minimum value is 0, we prove that for $r \geq 3$ there exists a d-regular graph G on n vertices that is r-colorable whenever $d \leq (1- \frac{1}{r}) n-1$ and nd is even. We also study the maximum value of $I_\alpha (G)$ over all d-regular graphs and find graphs that attain this maximum in many cases.

Given $m \geq 3$ alternatives and $n \geq 2$ voters, let $\sigma(m, n)$ be the least integer k for which there is a set of k strict preference profiles for the voters on the alternatives with the following property: Arrow's impossibility theorem holds for this profile set and for each of its strict preference profile supersets. We show that $\sigma(3, 2) = 6$ and that for each m, $\sigma(m, n)/4^n$ approaches 0 monotonically as n gets large. In addition, for each n and $\epsilon > 0$, $\sigma(m, n)/(\log_2 m)^{2+\epsilon}$ approaches 0 as m gets large. Hence for many alternatives or many voters, a robust version of Arrow's theorem is induced by a very small fraction of the set of all $(m!)^n$ strict preference profiles.

We answer a question of Golumbic, Monma and Trotter by constructing proper tolerance graphs that are not unit tolerance graphs. An infinite family of graphs that are minimal in this respect is specified.

A Markovian technique is described to calculate the exact performance of the Viterbi algorithm used as either a channel decoder or a source encoder for a convolutional code. The probability of information bit error and the expected Hamming distortion are computed for codes of various rates and constraint lengths. The concept of tie-breaking rules is introduced and its influence on decoder performance is examined. Computer simulation is used to verify the accuracy of the results. Finally, we discuss the issue of when a coded system outperforms an uncoded system in light of the new results.>

The paper describes Markov methods for analyzing the expected and worst case performance of sequence-based methods of quantization. We suppose that the quantization algorithm is dynamic programming, where the current step depends on a vector of path metrics, which we call a metric function. Our principal objective is a concise representation of these metric functions and the possible trajectories of the dynamic programming algorithm. We shall consider quantization of equiprobable binary data using a convolutional code. Here the additive group of the code splits the set of metric functions into a finite collection of subsets. The subsets form the vertices of a directed graph, where edges are labeled by aggregate incremental increases in mean squared error (MSE). Paths in this graph correspond both to trajectories of the Viterbi algorithm and to cosets of the code. For the rate 1/2 convolutional code [1+D/sup 2/, 1+D+D/sup 2/], this graph has only nine vertices. In this case it is particularly simple to calculate per dimension expected and worst case MSE, and performance is slightly better than the binary [24, 12] Golay code. Our methods also apply to quantization of arbitrary symmetric probability distributions on [0, 1] using convolutional codes. For the uniform distribution on [0, 1], the expected MSE is the second moment of the "Voronoi region" of an infinite-dimensional lattice determined by the convolutional code. It may also be interpreted as an increase in the reliability of a transmission scheme obtained by nonequiprobable signaling. For certain convolutional codes we obtain a formula for expected MSE that depends only on the distribution of differences for a single pair of path metrics.>

B. S. Tsirelson showed that comparisons between probabilities in “classical” physics and probabilities in quantum mechanics yield discrepancy measures $K_n $ for finite $n \times n$ real matrices that approach Grothendieck’s constant $K_G $ as n gets large. It is known that $K_2 = K_3 = \sqrt{2} $ and that $K_G \geq \pi /2 = 1.57 \cdots $, but examples of $n \times n$ matrices for specified n that demonstrate $K_n > \sqrt{2} $ have eluded researchers. A series of elementary examples are provided, which yield lower bounds on $K_{k ( k - 1 )} $ that approach 3/2 as k gets large. A uniform change along the main diagonal of our basic example shows that $K_{20} \geqq = 10/7 = 1.42 \cdots $.

Calculates the per-dimension mean squared error /spl mu/(S) of the two-state convolutional code C with generator matrix /spl lsqb/1,1+D/spl rsqb/, for the symmetric binary source S=(0,1), and for the uniform source S=/spl lcub/0,1/spl rcub/. When S=(0,1), the quantity /spl mu/(S) is the second moment of the coset weight distribution, which gives the expected Hamming distance of a random binary sequence from the code. When S=/spl lcub/0,1/spl rcub/, the quantity /spl mu/(S) is the second moment of the Voronoi region of the module 2 binary lattice determined by C. The key observation is that a convolutional code with 2/sup /spl upsi// states gives 2/sup /spl upsi// approximations to a given source sequence, and these approximations do not differ very much. It is possible to calculate the steady state distribution for the differences in these path metrics, and hence, the second moment. The authors only give details for the convolutional code /spl lsqb/1,1+D/spl rsqb/, but the method applies to arbitrary codes. They also define the covering radius of a convolutional code, and calculate this quantity for the code /spl lsqb/1,1+D/spl rsqb/.>

Let $f( n )$ be the minimum over all convex planar n-gons of the number of different midpoints of the $\begin{pmatrix} n \\ 2 \end{pmatrix}$ line segments, or diagonals, between distinct vertices. It is proved that $f( n )$ is between approximately $0.8 \begin{pmatrix} n \\ 2 \end{pmatrix} $ and $0.9 \begin{pmatrix} n \\ 2 \\ \end{pmatrix} $. The upper bound uses the fact that the number of multiple midpoints, shared by two or more diagonals, can be as great as about $\begin{pmatrix} n \\ 2 \end{pmatrix}/10$. Cases for which the number of midpoints is at least $\lceil n( n - 2 )/2 \rceil + 1$, the number for a regular n-gon when n is even, are noted.

A system $[ p_{ij} : i, j \in \{ 1, 2, \cdots ,n \}, i \ne j,p_{ij} + p_{ji} = 1 ]$ of binary probabilities is said to be induced by rankings if there is a probability distribution P on the set of $n!$ linear orders of $\{ 1,2, \cdots ,n \}$ such that, for all distinct i and $j,p_{ij} $ is the sum of the P values over all linear orders in which i precedes j. It has been known for some time that the triangle inequality $p_{ij} + p_{jk} \geqq p_{ik} $ is necessary for $\{ p_{i j} \} $ to be induced by rankings and that it is also sufficient if $n\leqq 5$. The insufficiency of the triangle inequality when $n\geqq 6$ has been known since about 1970, and other necessary conditions for $n\geqq 6$ have been known since 1978. The present paper generates additional necessary conditions that pertain to $n\geqq 6$ and shows that they are independent of previous necessary conditions. It then observes that the set of conditions on the $p_{ij} $ that are sufficient for $\{ p_{ij} \} $ to be induced by rankings regardless of n must be infinite. As far as is known, identification of finite sets of necessary and sufficient conditions for each particular $n\geqq 6$ remains open.

The thickness of a finite poset (partially ordered set) is the cardinality of the smallest partition of the poset into induced subposets of dimension two or less. Thickness combines aspects of width and length. It never exceeds length, can equal length for any finite length, and never exceeds about half the width. There are dimension 3 posets with arbitrarily large thicknesses, and there are thickness 2 posets with arbitrarily large dimension. For $m\geqq 3$, the m-dimensional poset of the singletons and their complements of an m-set ordered by inclusion has thickness 2; the thickness of the m-dimensional poset of all subsets of an m-set ordered by inclusion goes to infinity as m gets large. Every semiorder has thickness 1 or 2, but an interval order can have arbitrarily large thickness. Ramsey theory is used to obtain some of the preceding results. Other methods are used to identify examples of posets with thickness 2 and to prove that the smallest poset with thickness 3 must have at least 15 points.

This paper considers a variety of combinatorial and number-theoretic questions that arise from considerations of uniqueness in the theory of measurement. Given $n + 1$ objects linearly ordered from worst (smallest) to best (largest), let $d_i $ stand for the difference between objects i and $i + 1$. Three types of assumptions that allow different inequality and equality comparisons between certain subsets of differences are considered. The three types of assumptions arise from problems concerning the uniqueness of finite algebraic difference measurement and finite subjective probability measurement. If the number of equality comparisons is sufficient to imply that the $d_i $ in $d = ( d_1 ,d_2 , \cdots ,d_n )$ are unique up to multiplication by a positive constant, then d is said to be unique. Results on the number of unique d’s and relationships among the components of such d’s are obtained for each of the three types.