Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Sunflower (mathematics)
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.