Functions that Never Agree

Journal Article (Journal Article)

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

Full Text

Duke Authors

Cited Authors

  • Calderbank, AR; Fishburn, PC; Spencer, JH

Published Date

  • January 1, 1986

Published In

Volume / Issue

  • 7 / 3

Start / End Page

  • 207 - 210

International Standard Serial Number (ISSN)

  • 0195-6698

Digital Object Identifier (DOI)

  • 10.1016/S0195-6698(86)80023-3

Citation Source

  • Scopus