Publications [#331064] of Robert Calderbank

Journal articles or Book chapters PUBLISHED

1. Calderbank, AR; Fishburn, PC; Spencer, JH, Functions that Never Agree, European Journal of Combinatorics, vol. 7 no. 3 (January, 1986), pp. 207-210, Elsevier BV [doi]
   (last updated on 2026/01/17)

   Abstract:
   Consider functions f1, . . . , fk defined on an n-element set I with the property that if x ∈ I then f1(x), . . . , fk(x) are all distinct. We shall say that the functions f1, . . . , fk never agree. Let ρ(f1, . . . , fk) be the size of the largest subset I* of I for which f1(I), . . . , fk (I*) are all disjoint, and let ρk (n) = min{ρ (f1, . . . , fk)} where the minimum is taken over all functions f1, . . . , fk that never agree. We prove that ρk(n) ⩾ n/k^k, and that in the limit as n → ∞, the ratio ρk (n)/n → 1/k^k. For k = 2 we describe how the function p (f1, f2) can be interpreted as a measure of the bipartiteness of a graph. When n = 2l²+l we prove that ρ2(n) = (l²+l)/2. © 1986, Academic Press Inc. (London) Limited. All rights reserved.