For any finite discrete source, the competitive advantage of prefix code$C_{1}$over prefix code$C_{2}$is the probability$C_{1}$produces a shorter codeword than$C_{2}$, minus the probability$C_{2}$produces a shorter codeword than$C_{1}$. For any source, a prefix code is competitively optimal if it has a nonnegative competitive advantage over all other prefix codes. In 1991, Cover proved that Huffman codes are competitively optimal for all dyadic sources, namely sources whose symbol probabilities are negative integer powers of 2. We prove the following asymptotic converse: As the source size grows, the probability a Huffman code for a randomly chosen non-dyadic source is competitively optimal converges to zero. We also prove: (i) For any non-dyadic source, a Huffman code has a positive competitive advantage over a Shannon-Fano code; (ii) For any source, the competitive advantage of any prefix code over a Huffman code is strictly less than$\frac {1}{3}$; (iii) For each integer$n\gt 3$, there exists a source of size n and some prefix code whose competitive advantage over a Huffman code is arbitrarily close to$\frac {1}{3}$; and (iv) For each positive integer n, there exists a source of size n and some prefix code whose competitive advantage over a Shannon-Fano code becomes arbitrarily close to 1 as$n\to \infty $.

The 3/4 conjecture was posed 25 years ago by Ahlswede, Balkenhol, and Khachatrian, and states that if a multiset of positive integers has Kraft sum at most 3/4, then there exists a code that is both a prefix code and a suffix code with these integers as codeword lengths. We prove that the 3/4 conjecture is true whenever the given multiset of positive integers contains at most three distinct values.

The zero capacity region for hexagonal$(d,k)$run-length constraints is known for many, but not all,$d$and$k$. The pairs$(d,k)$for which it has been unproven whether the capacity is zero or positive consist of: (i)$k=d+2$when$d\ge 2$; (ii)$k=d+3$when$d \ge 1$; (iii)$k=d+4$when either$d=4$or$d$is odd and$d \ge 3$; and (iv)$k=d+5$when$d=4$. Here, we prove that the capacity is zero for all of case (i), and for case (ii) whenever$d \ge 7$. The method used in this paper is to reduce an infinite search space of valid labelings to a finite set of configurations that we exhaustively examine using backtracking. In Part II of this two-part series, we use automated procedures to prove that the capacity is zero in case (i) when$2 \le d \le 9$, in case (ii) when$3 \le d \le 11$, and in case (iii) when$d \in \{ 4,5,7,9 \}$, and that the capacity is positive in case (ii) when$d \in \{1,2\}$, in case (iii) when$d = 3$, and in case (iv). Thus, the only remaining unknown cases are now when$k=d+4$, for any odd$d \ge 11$.

The zero capacity region for hexagonal$(d,k)$run-length constraints is known for many, but not all,$d$and$k$. The pairs$(d,k)$for which it has been unproven whether the capacity is zero or positive consist of: (i)$k=d+2$when$d\ge 2$; (ii)$k=d+3$when$d \ge 1$; (iii)$k=d+4$when either$d=4$or$d$is odd and$d \ge 3$; and (iv)$k=d+5$when$d=4$. Here, we prove the capacity is zero in case (i) when$2 \le d \le 9$, in case (ii) when$3 \le d \le 11$, and in case (iii) when$d \in \{ 4,5,7,9 \}$. We also prove the capacity is positive in case (ii) when$d \in \{1,2\}$, in case (iii) when$d = 3$, and in case (iv). The zero capacities for$k=d+4$are the first and only known cases equal to zero when$k-d > 3$. All of our results are obtained by developing three algorithms that automatically and rigorously assist in proving either the zero or positive capacity results by efficiently searching large numbers of configurations. The proofs involve either upper bounding the number of paths through certain large directed graphs, finding forbidden strings, or building distinct tileable square labelings. Some of the proofs examine over 20 billion cases using a supercomputer. In Part I of this two-part series, it is proven that the capacity is zero for all of case (i), and for case (ii) whenever$d \ge 7$. Thus, the only remaining unknown cases are now when$k=d+4$, for any odd$d \ge 11$.

Short range vehicle to vehicle and device to device communications are of growing interest due to their utility for vehicular safety and infotainment applications as well as for improving the capacity of cellular networks. These mobile systems are characterized by ephemeral, stochastic links. We consider a fundamental problem in this domain -- how to maximize the amount of useful content downloaded by a client from a server over an encounter that lasts a random amount of time. We assume that the distribution of link duration is known or estimated \emph{a priori} based on historical as well as real-time measurements. We present MERLIN (Maximum Expected download over Random LINks), a single-phase file request protocol that is provably optimal. We evaluate MERLIN comprehensively via simulations based on both ideal link duration distributions as well as empirical distributions obtained from real vehicular mobility traces (from Taxis in Shanghai and Buses in Chicago). We also present two Contiki OS-based implementations of MERLIN (with local and remote calculations) evaluated on the Tmote Sky wireless embedded platform.