## Functions that Never Agree

Publication ,  Journal Article
Calderbank, AR; Fishburn, PC; Spencer, JH
Published in: European Journal of Combinatorics
January 1, 1986

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/kk, and that in the limit as n → ∞, the ratio ρk (n)/n → 1/kk. 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 = 2l2+l we prove that ρ2(n) = (l2+l)/2. © 1986, Academic Press Inc. (London) Limited. All rights reserved.

## Published In

European Journal of Combinatorics

0195-6698

January 1, 1986

7

3

## Start / End Page

207 / 210

• Computation Theory & Mathematics
• 0101 Pure Mathematics

### Citation

APA
Chicago
ICMJE
MLA
NLM
Calderbank, A. R., Fishburn, P. C., & Spencer, J. H. (1986). Functions that Never Agree. European Journal of Combinatorics, 7(3), 207–210. https://doi.org/10.1016/S0195-6698(86)80023-3
Calderbank, A. R., P. C. Fishburn, and J. H. Spencer. “Functions that Never Agree.” European Journal of Combinatorics 7, no. 3 (January 1, 1986): 207–10. https://doi.org/10.1016/S0195-6698(86)80023-3.
Calderbank AR, Fishburn PC, Spencer JH. Functions that Never Agree. European Journal of Combinatorics. 1986 Jan 1;7(3):207–10.
Calderbank, A. R., et al. “Functions that Never Agree.” European Journal of Combinatorics, vol. 7, no. 3, Jan. 1986, pp. 207–10. Scopus, doi:10.1016/S0195-6698(86)80023-3.
Calderbank AR, Fishburn PC, Spencer JH. Functions that Never Agree. European Journal of Combinatorics. 1986 Jan 1;7(3):207–210.

## Published In

European Journal of Combinatorics

0195-6698

January 1, 1986

7

3

207 / 210