Théorème de Ramsey pour les collections d'ensembles

13

En explorant différentes techniques pour prouver les limites inférieures des algorithmes distribués, il m'est venu à l'esprit que la variante suivante du théorème de Ramsey pourrait avoir des applications - s'il se trouve que c'est vrai.


Les paramètres: k , K , n sont donnés, puis N est choisi pour être suffisamment grand. Terminologie: un sous-ensemble m est un sous-ensemble de taille m .

  • Soit A={1,2,...,N} .
  • Laissez - B se composent de tous les k -subsets de A .
  • Soit C se composent de tous les K -subsets de B .
  • Assigner une coloration f:C{0,1} de C .

Maintenant, le théorème de Ramsey (la version hypergraphe) dit que peu importe la façon dont nous choisissons f , il existe un n-sous- ensemble monochromatique B de B : tous les K-sous- ensembles de B ont la même couleur.nBBKB

Je voudrais aller plus loin et trouver un n ensemble monochromatique A de A : si BB est composé de tous les k ensembles de A , alors tous les K ensembles de B ont la même couleur.


Est-ce vrai ou faux? At-il un nom? Connaissez-vous des références?

S'il est faux pour des raisons triviales, existe-t-il une variante plus faible qui ressemble à cette affirmation?

Jukka Suomela
la source
1
Pas une réponse, mais une référence rapide au cas où cela aiderait: cela semble légèrement lié au problème de conception de la couverture , où vous voulez (et pouvez obtenir) une petite collection de s-sous- ensembles de n qui contient tous les r-sous- ensembles de n , pour r < s < n . (r,s,n)snrnr<s<n
Lev Reyzin
Il y a maintenant une question de suivi: cstheory.stackexchange.com/questions/3795
Jukka Suomela

Réponses:

13

Observé que la question n'est non triviale que lorsque k, K sont tous deux supérieurs à 1; pour le cas k = 1 ou K = 1, c'est juste le théorème de Ramsey normal, qui est vrai pour tout n. De plus, nous n'avons qu'à traiter le cas où > K, sinon le théorème est vrai puisqu'il y en a au plus un ( n(nk) -sous-ensemble de B 'construit par un n-sous-ensemble A' de A.(nk)


Tout d'abord, nous prouvons que le théorème est faux pour tout k> 1, K> 1, et tout n satisfait > K>(n-1(nk).(n1k)

Afin de construire un contre-exemple, pour tout grand N et A = [N], nous devons construire une fonction de coloration f telle que pour tout n-sous-ensemble A 'de A, si B' se compose de tous les k-sous-ensembles de A ' , certains des sous-ensembles K de B 'ont des couleurs différentes. Ici, nous avons l'observation suivante:

Observation 1. Dans les conditions où k, K> 1 et > K>(n-1(nk), tout sous-ensemble K de B est un sous-ensemble d'au plus un B 'construit par un n sous-ensemble A' de A.(n1k)

L'observation peut être facilement ressentie en représentant des hypergraphes. Soit A les nœuds du graphe G, un n-sous-ensemble A 'de A est l'ensemble des nœuds d'un n-sous-graphe complet dans G. B' est l'ensemble des k-hyper-bords dans le sous-graphe complet (un 2-hyperedge est un bord normal), et les sous-ensembles K de B 'sont toutes les combinaisons (il y a au total, où | B '| = ( n(|B|K) ) de K k-hyperedges. L'observation déclare: tout K-tuple d'hyper-arêtes dans G appartient à au plus un sous-graphe n complet, ce qui est évident pour ( n(nk) > K>(n-1(nk), puisque deux n-sous-graphes complets se coupent au plus n-1 nœuds, avec au plus(n-1(n1k)hyperedges.(n1k)

Ensuite, nous pouvons attribuer différentes couleurs au sein des K-sous-ensembles C 'd'un B particulier construit par un n-sous-ensemble A', car aucun élément de C 'ne se produira comme un autre K-sous-ensemble de B' 'construit par un n-sous-ensemble UNE''. Pour tout sous-ensemble K de B non construit par un sous-ensemble n de A, nous lui attribuons une couleur aléatoire. Maintenant, nous avons une fonction de coloration f, avec la propriété qu'aucun B 'construit par n-sous-ensemble de A n'est monochromatique, c'est-à-dire que certains des K-sous-ensembles de B' ont des couleurs différentes.


Ensuite, nous montrons que le théorème est également faux pour tout k> 1, K> 1, et tout n satisfait > K. Ici, la seule différence est que n peut être choisi si grand que K>(n-1(nk)n'est pas vrai. Mais par une autre simple observation:(n1k)

Observation 2. Si certains B 'construits par un n-sous-ensemble A' de A sont monochromatiques, alors chaque B '' construit par un n'-sous-ensemble A '' de A 'pour n' <n est également monochromatique.

On peut donc supposer que le théorème tient sur le plus grand n, appliquer la seconde observation et conclure une contradiction par le premier cas, en posant n 'satisfait > K>( n -1(nk); un tel n 'doit exister par le fait que(n(n1k)> K et K>(k(nk), n 'doit se situer entre n et k + 1.(kk)

Hsien-Chih Chang 張顯 之
la source
Super, un contre-exemple si simple, merci beaucoup! Je me demande si votre idée peut être étendue à arbitraire . Par exemple, est-ce nécessairement faux également si 1 k K ou 1 K k ? k,K1kK1Kk
Jukka Suomela
Oui, c'est également faux dans presque tous les cas. Je vais modifier la réponse.
Hsien-Chih Chang 張顯 之