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.
Concept
Sunflower (mathematics)
Summary
In the mathematical fields of set theory and extremal combinatorics, a sunflower or -system is a collection of sets whose pairwise intersection is constant. This constant intersection is called the kernel of the sunflower.
The main research question arising in relation to sunflowers is: under what conditions does there exist a large sunflower (a sunflower with many sets) in a given collection of sets? The -lemma, sunflower lemma, and the Erdős-Rado sunflower conjecture give successively weaker conditions which would imply the existence of a large sunflower in a given collection, with the latter being one of the most famous open problems of extremal combinatorics.
Suppose is a set system over , that is, a collection of subsets of a set . The collection is a sunflower (or -system) if there is a subset of such that for each distinct and in , we have . In other words, a set system or collection of sets is a sunflower if the pairwise intersection of each set in is identical.
Note that this intersection, , may be empty; a collection of pairwise disjoint subsets is also a sunflower. Similarly, a collection of sets each containing the same elements is also trivially a sunflower.
The study of sunflowers generally focuses on when set systems contain sunflowers, in particular, when a set system is sufficiently large to necessarily contain a sunflower.
Specifically, researchers analyze the function for nonnegative integers , which is defined to be the smallest nonnegative integer such that, for any set system such that every set has cardinality at most , if has more than sets, then contains a sunflower of sets. Though it is not clear that such an must exist, a basic and simple result of Erdős and Rado, the Delta System Theorem, indicates that it does.
Erdos-Rado Delta System Theorem:
For each , is an integer such that a set system of -sets is of cardinality greater than , then contains a sunflower of size .
In the literature, is often assumed to be a set rather than a collection, so any set can appear in at most once.
Official source
About this result
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.