jkpachl@watdaisy.UUCP (Jan Pachl) (11/09/86)
:: I would appreciate any reference for the following (unsolved, as far as I know) combinatorial problem: Let n > 0 be an integer, and let A be a collection of 2n sets. Let A be closed under union (i.e. if two sets belong to A then their union belongs to A as well). Is it always true (i.e. for any n and any such A ) that some n sets in A intersect? Apparently Erdos proposed the problem during one of his problem talks, several years ago. Is the problem recorded anywhere? (If there is a solution, I'll take that, too). Jan Pachl, University of Waterloo
riddle@emory.UUCP (Larry Riddle) (11/18/86)
Jan Pachl asked: >> Let n be an integer, and let A be a collection >> of 2n sets. Let A be closed under union (i.e. if two >> sets belong to A then their union belongs to A as well). >> Is it always true (i.e. for any n and any such A ) that >> some n sets in A intersect? >> >> Apparently Erdos proposed the problem during one of his problem >> talks, several years ago. Is the problem recorded anywhere? >> (If there is a solution, I'll take that, too). I am passing on some information from a colleague. Apparently Erdos insists the problem did not originate with him. Most people now credit Peter Frankl, University of Paris. The problem is still unsolved. Ron Graham at one point thought he had a counterexample but it turned out not to work. My colleague says there are some partial results known but did not know the details or references. -- Larry Riddle | {akgua,sb1,gatech}!emory!riddle USENET Emory University | riddle@emory CSNET,BITNET Dept of Math and CS | riddle.emory@csnet-relay ARPANET Atlanta, Ga 30322