Repository logo
 

A New Upper Bound for Cancellative Pairs

Published version
Peer-reviewed

Repository DOI


Type

Article

Change log

Authors

Janzer, Barnabás 

Abstract

jats:pA pair (A,B) of families of subsets of an n-element set is called cancellative if whenever A,A′∈A and BB satisfy AB=A′∪B, then A=A, and whenever AA and B,B′∈B satisfy AB=AB, then B=B. It is known that there exist cancellative pairs with |A||B| about 2.25n, whereas the best known upper bound on this quantity is 2.3264n. In this paper we improve this upper bound to 2.2682n. Our result also improves the best known upper bound for Simonyi's sandglass conjecture for set systems.</jats:p>

Description

Keywords

4901 Applied Mathematics, 4904 Pure Mathematics, 49 Mathematical Sciences

Journal Title

The Electronic Journal of Combinatorics

Conference Name

Journal ISSN

1097-1440
1077-8926

Volume Title

25

Publisher

The Electronic Journal of Combinatorics