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

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 $1 \ll d \ll k \ll n$ 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\}$$k$$S \subset B$$f(S) \in \{0,1\}$

Définitions:

• estmonochromatiquesi f ( S ) = f ( S ' ) pour tous les k -subsets S ⊂ X et S ' ⊂ X .$X \subset B$$f(S) = f(S')$$k$$S \subset X$$S' \subset X$
• $X \subset B$$X = \{ x_1, x_2, ..., x_n \}$$x_i < x_{i+1}$$x_i\,\not\equiv x_{i+1} \text{ mod } d$$i$

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 .$f$$n$$X \subset B$$n$$X \subset B$

Question: est - il toujours diverse et monochrome -subset ?$n$$X \subset B$

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.$d$$d$$d \ll k \ll n$

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, \ldots\}$

• 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 .$n$$n/d$$R(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+d-1$$d \mid k$

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 .$k-1$$X = x_1,\ldots,x_n$$S^* = x_1,\ldots,x_k$$x_i$$x_{i+1}$$S^*$

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 avec$S$$S$$n > k+d+1$$S$$X$$n > d$$x_i,x_j$$j-i \leq d-1$$n > k+d+1$$x_k$$X$$k<i$$k>j$$S$$x_i$à côté de , qui ne commute que au plus k-2 fois. Ainsi est un sous-ensemble k rouge.$x_j$$S$

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.