Extensions du théorème de Ramsey: monochromatique mais diversifié

9

Dans le prolongement de ma question précédente , qui a été résolue par Hsien-Chih Chang, voici une autre tentative pour trouver une généralisation appropriée du théorème de Ramsey. (Vous n'avez pas besoin de lire la question précédente; ce message est autonome.)


Paramètres: les entiers 1dkn sont donnés, puis N est choisi suffisamment grand. Terminologie: un sous-ensemble m est un sous-ensemble de taille m .

Soit . Pour chaque k-sous- ensemble S B , affectez une couleur f ( S ) { 0 , 1 } .B={1,2,...,N}kSBf(S){0,1}

Définitions:

  • estmonochromatiquesi f ( S ) = f ( S ' ) pour tous les k -subsets S X et S 'X .XBf(S)=f(S)kSXSX
  • XBX={x1,x2,...,xn}xi<xi+1xixi+1 mod di

Par exemple, si , alors est différent mais ne l'est pas. Notez qu'un sous-ensemble d'un ensemble diversifié n'est pas nécessairement diversifié.d=10{12,15,23,32,39}{12,15,25,32,39}

Maintenant , le théorème de Ramsey dit que peu importe la façon dont nous choisissons , il y a un monochrome -subset . Et , évidemment , il est trivial de trouver une diversité -subset .fnXBnXB

Question: est - il toujours diverse et monochrome -subset ?nXB


Edit: Hsien-Chih Chang montre que l'affirmation est fausse pour un premier , mais qu'en est-il du composite ? Dans mes applications, j'aurai beaucoup de liberté pour choisir les valeurs exactes de , tant que je pourrai les rendre arbitrairement grandes. Ils peuvent être des puissances de nombres premiers, des produits de nombres premiers, ou tout ce qui est nécessaire pour que la revendication soit vraie.dddkn

Jukka Suomela
la source

Réponses:

7

Je dois d'abord dire: ce problème est vraiment intéressant !! Et ici, je décris brièvement pourquoi mes approches précédentes ont échoué, comme suggéré dans ce meta post sur les réponses incorrectes.

  • Ma première tentative a été d'essayer de construire une coloration liée à la somme du k-sous-ensemble qui rend tout n-sous-ensemble non monochromatique. Le lemme 1 est toujours disponible; mais le lemme 2 était faux, en observant que si k et d sont premiers liés, alors un n-sous-ensemble dans le module d suggéré par @Jukka est un contre-exemple.{1,3,1,3,}

  • Le deuxième essai était une preuve du théorème; en comptant le rapport des sous-ensembles divers et monochromatiques , nous espérons que le nombre de sous-ensembles monochromatiques dépassera celui des non-divers. Mais c'est une erreur dans mes calculs, observée par @domotorp: le ratio de non-diversité ne s'approche pas de zéro; il converge vers environ , ce qui est clairement plus grand que .nn/dR(n,n;k)n

  • La troisième revient à la première méthode, et elle montre que pour un ensemble de paramètres ultra-faibles ( et ), le théorème est faux. Nous avons utilisé un lemme célèbre en combinatoire additive: le théorème EGZ.n>k+d1dk


Le quatrième essai est dû à la réponse de @domotorp; c'est à la fois intelligent et inspirant, et je vais essayer de modifier sa preuve pour traiter tous les paramètres. Mais sa méthode est toujours élégante et j'apprécie totalement cette approche simple.

Un ensemble n diversifié contient au moins un sous-ensemble k avec au moins "commutateurs entre classes de mod"; précisément, soit un ensemble n diversifié, et soit , un commutateur est défini si et sont dans différents mod-d Des classes. Nous avons k-1 commutateurs pour .k1X=x1,,xnS=x1,,xkxixi+1S

Soit un k-sous - ensemble est rouge si a au plus k-2 commutateurs; sinon c'est bleu . Par le paragraphe précédent , nous avions déjà un bleu, maintenant nous prouver que pour , il y a un rouge dans une n-ensemble . Puisque , il y a deux nombres dans la même classe mod-d et ; et puisque , il y a au moins k-2 éléments dans avec ou . Et nous pouvons construire un k-sous-ensemble avecSSn>k+d+1SXn>dxi,xjjid1n>k+d+1xkXk<ik>jSxià côté de , qui ne commute que au plus k-2 fois. Ainsi est un sous-ensemble k rouge.xjS

Hsien-Chih Chang 張顯 之
la source
1
J'ai posé une question sur MO pour la demande de littératures en EHC généralisée sur les groupes cycliques.
Hsien-Chih Chang 張顯 之
Merci, c'était instructif, mais je ne sais pas si cela pourrait être étendu pour montrer que la réclamation est fausse pour un composite . Par exemple, si et est impair, alors un diversifié pourrait être composé d'éléments qui sont alternativement ou mod , et aucun sous-ensemble n'est nul mod ? dd=4kX13dkd
Jukka Suomela
Concernant le vrai problème: Tout cela est lié à la démonstration des déclarations de la forme «il n'y a pas d'algorithme distribué déterministe qui résout ce problème de graphe en moins de ce nombre de cycles de communication». La théorie de Ramsey a été appliquée avec succès dans de nombreux cas; voir par exemple la leçon 4 ici . Mais parfois, j'ai besoin de quelque chose de plus fort que de "simples" sous-ensembles monochromatiques. C'est une longue histoire, et tout est embarrassamment vague à ce stade, mais si cela mène à quelque chose de concret, je vais certainement écrire une explication détaillée ici!
Jukka Suomela
@Jukka: Merci de bien vouloir partager vos idées, j'espère que vous arriverez bientôt à quelque chose de vraiment sympa! Quant au cas où d est composite, j'ai eu quelques idées pour les gérer, mais c'est quand même un peu brouillon, je réfléchirai encore quelques heures avant de les écrire, au cas où les idées ne se défont pas. ..
Hsien-Chih Chang 張顯 之
@Jukka: J'ai trouvé une erreur bizarre dans ma preuve. Dans le lemme 3, ne devrait pas être supposé être inférieur à, donc plus petit que ? Sinon, il est impossible d'avoir tous les distincts. Je vais essayer de corriger l'erreur. Mais actuellement, la preuve est cassée ...k|X|dxi
Hsien-Chih Chang 張顯 之
6

J'ai peut-être mal compris votre question, mais sinon, je pense qu'elle est fausse. Colorez les k-sets dont les membres sont tous modulo d congruents en rouge, les autres k-sets en bleu. Si n> kd, alors tout n-set doit contenir un k-set dont les membres sont tous modulo d congrus et est donc rouge. D'un autre côté, si un ensemble k contient deux éléments consécutifs d'un ensemble n divers, alors il est bleu.

domotorp
la source
1
C'est intelligent! Et nous avons seulement besoin de en fait. Votre réponse exclut presque tous les cas ... Maintenant, les seules possibilités sont , qui ne sont pas trop. n>(k1)dn(k1)d
Hsien-Chih Chang 張顯 之