We determine the exact value of the optimal symmetric rate point$(r, r)$in the Dueck zero-error capacity region of the binary adder channel with complete feedback. We proved that the average zero-error capacity$r = h(1/2-\delta) \approx 0.78974$, where$h(\cdot)$is the binary entropy function and$\delta = 1/(2\log _{2}(2 + \sqrt {3}))$. Our motivation is a problem in quantitative group testing. Given a set of$n$elements two of which are defective, the quantitative group testing problem asks for the identification of these two defectives through a series of tests. Each test gives the number of defectives contained in the tested subset, and the outcomes of previous tests are assumed known at the time of designing the current test. We establish that the minimum number of tests is asymptotic to$(\log _{2} n) / r$as$n \to \infty $.

We prove that every family of (not necessarily distinct) odd cycles $O_1, \dots, O_{2\lceil n/2 \rceil-1}$ in the complete graph $K_n$ on $n$ vertices has a rainbow odd cycle (that is, a set of edges from distinct $O_i$'s, forming an odd cycle). As part of the proof, we characterize those families of $n$ odd cycles in $K_{n+1}$ that do not have any rainbow odd cycle. We also characterize those families of $n$ cycles in $K_{n+1}$, as well as those of $n$ edge-disjoint nonempty subgraphs of $K_{n+1}$, without any rainbow cycle.

In a deductive game for two players, SF and PGOM, SF conceals an n-digit number x = x1, …, xn in base q, and PGOM, who knows n and q, tries to identify x by asking a number of questions, which are answered by SF. Each question is an n-digit number y = y1, …, yn in base q; each answer is the number of subscripts i such that xi = yi. Moreover, we require PGOM send all the questions at once. We show that the minimum number of questions required to determine x is (2+oq(1))n/ logq n. Our result closes the gap between the lower bound attributed to Erdős and Rényi and the upper bounds developed subsequently by Lindström, Chvátal, Kabatianski, Lebedev and Thorpe. A more general problem is to determine the asymptotic formula of the metric dimension of Cartesian powers of a graph. We state the class of graphs for which the formula can be determined, and the smallest graphs for which we did not manage to settle.

The exact values of the optimal symmetric rate point in the Cover--Leung capacity region of the two-user union channel with complete feedback were determined by Willems when the size of the input alphabet is 2, and by Vinck, Hoeks and Post when the size is at least 6. We complete this line of research when the size of the input alphabet is 3, 4 or 5. The proof hinges on the technical lemma that concerns the maximal joint entropy of two independent random variables in terms of their probability of equality. For the zero-error capacity region, using superposition coding, we provide a practical near-optimal communication scheme which improves all the previous explicit constructions.