**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# Families with no s pairwise disjoint sets

Abstract

For integers n >= s >= 2 let e (n, s) denote the maximum of vertical bar F vertical bar, where F is a family of subsets of an n- element set and F contains no s pairwise disjoint members. Half a century ago, solving a conjecture of Erd. os, Kleitman determined e(sm - 1, s) and e (sm, s) for all m, s >= 1. During the years very little progress in the general case was made. In the present paper we state a general conjecture concerning the value of e(sm - l, m) for 1 < l < s and prove its validity for s > s(0) (l, m). For l = 2 we determine the value of e(sm - 2, m) for all s >= 5. Some related results shedding light on the problem from a more general context are also proved.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (6)

Related concepts (16)

Disjoint sets

In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set. For example, {1, 2, 3} and {4, 5, 6} are disjoint sets, while {1, 2, 3} and {3, 4, 5} are not disjoint. A collection of two or more sets is called disjoint if any two distinct sets of the collection are disjoint. This definition of disjoint sets can be extended to families of sets and to indexed families of sets.

Sleep medicine

Sleep medicine is a medical specialty or subspecialty devoted to the diagnosis and therapy of sleep disturbances and disorders. From the middle of the 20th century, research has provided increasing knowledge of, and answered many questions about, sleep–wake functioning. The rapidly evolving field has become a recognized medical subspecialty in some countries. Dental sleep medicine also qualifies for board certification in some countries. Properly organized, minimum 12-month, postgraduate training programs are still being defined in the United States.

Sleep hygiene

Sleep hygiene is a behavioral and environmental practice developed in the late 1970s as a method to help people with mild to moderate insomnia. Clinicians assess the sleep hygiene of people with insomnia and other conditions, such as depression, and offer recommendations based on the assessment.

The valorisation of the plant biopolymer lignin is now recognised as essential to enabling the economic viability of the lignocellulosic biorefining industry. In this context, the "lignin-first" biorefining approach, in which lignin valorisation is conside ...

Endogenous rhythms of circalunar periodicity (similar to 29.5 days) and their underlying molecular and genetic basis have been demonstrated in a number of marine species [1, 2]. In contrast, there is a great deal of folklore but no consistent association o ...

Let P be a partially ordered set. The function La* (n, P) denotes the size of the largest family F subset of 2([n]) that does not contain an induced copy of P. It was proved by Methuku and Palvolgyi that there exists a constant C-P (depending only on P) su ...