Abstract | ||
---|---|---|
A pair (A, B) of families of subsets of an n-element set X is cancellative if, for all A,A' is an element of A and B, B' is an element of B, the following conditions hold: A\B = A'\B --> A = A' and B/A = B'\A --> B = B'. We prove that every such pair satisfies \A\ \B\ < theta(n), where theta approximate to 2.3264. This is related to a conjecture of Erdos and Katona on cancellative families and to a conjecture of Simonyi on recovering pairs. For the latter, our result gives the best known upper bound. |
Year | DOI | Venue |
---|---|---|
1995 | 10.1016/0195-6698(95)90031-4 | Eur. J. Comb. |
Keywords | Field | DocType |
cancellative pair | Discrete mathematics,Combinatorics,Cancellative semigroup,Upper and lower bounds,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
16 | 3 | 0195-6698 |
Citations | PageRank | References |
7 | 0.81 | 3 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ron Holzman | 1 | 287 | 43.78 |
János Körner | 2 | 53 | 8.25 |