antithèse d'un X-set clos par union

pour des renseignement sur mes reflexions précédentes à propos de la conjecture de Frankl et la stabilité par union voir le lien :
http://www.les-mathematiques.net/phorum/read.php?3,1097923,1097923#msg-1097923 (merci AD :) )

Soit $X$ un ensemble fini.
Un $X$-set est par définition un ensemble $F$ de partie de $X$ tel que $X\in F$

Notations et définition

Soit $x\in X$ et $F$ $X$-set, on note $F_x=\left\{f\in E,\space x\in f\right\}$ et $F^x=F-F_x$, on dira que $x\in X$ est rare dans $F$ ou $F$-rare si $|F_x|<|F^x| $

On définit l'antithèse de $F$ et l'on note $Anti(F)\subset X$
$x\in Anti(F) \Leftrightarrow |E_x|<|E^x| $ (en d'autre terme $x$ est dans $Anti(F)$ si et seulement si c'est un point rare dans $F$ )

On dit que $F$ est clos (par réunion) sur $X$ si $F$ est un $X$-set et si $\forall a\in F \space \forall b\in F, \space a\cup b\in F$

Conjectures(**)

Si $F$ est Clos sur $X$ et si $Anti(F)\in F$ alors $Anti(F)=\emptyset$

(en particulier $Anti(F)\ne X$ (*) ce cas particulier étant une paraphrase de la conjecture de Frankl)



Conjecture de minimalité de l’antithèse (***)
$\forall f\in F, \space f\subset Anti(F)\Rightarrow f=\emptyset$

On obtient alors si je n'ai pas fait d'erreur (***) implique (**) (et évidemment (*) )

Réponses

  • en vue d'essayer de démontrer (***) dans un cas particulier que je vais évoquer, je vais faire appel à un lemme d'hérédité amusant, je n'ai pas réussi à montrer le résultat voulu qui est :


    Si pour tout $F$ Clos sur $X$ et tout minimum non vide $m\in F$ il existe $x\in X$ tel que $m\cup\left\{x\right\}\in F$ alors aucun élément de $F$ n'est inclus dans $Anti(F)$.


    ....mais j'ai prouvé le lemme dont je croyais avoir besoin, ainsi je le laisse ici.



    D'abord une définition (de "creux singulier")
    A l'avenir $F$ désignera toujours un ensemble $X$-clos, ne contenant pas $\emptyset$
    et je noterai $a\cup\left\{b\right\}$ de la façon suivante $a+b$ ainsi que $a\setminus\left\{b\right\}$ sera noté $a-b$

    soit $x\in X$ et $f\in F$, on dit que $x$ est un creux singulier pour $f$ (ou alternativement $f$ a un creux singulier en $x$) si et seulement si $f+x\notin F$

    Si $x\in X$ n'a de creux singulier pour aucun $f\in F$ on dira que c'est un point $F$-plein (ou une "colonne pleine de $F$)
    Si $f\in F$ n'a de creux singulier en aucun point de $X$ on dira que c'est une partie $F$-pleine (ou une "ligne" pleine de $F$)
    Si $f\in F$ a au moins un creux non singulier on dira que c'est une ligne raisonnable dans $F$
    on notera $Sing(x,F)$ l'ensemble des $f\in F$ tels que $f$ est creux en $x$.
    On notera aussi $FULL(x,F)$ l'ensemble (clos sur $X$ !) $F\setminus Sing(x,F) \cup \left\{s+x|s\in Sing(x,F)\right\}$ obtenu en "remplissant" les creux singulier en $x$ (et seulement ceux là) : il est immédiat que l'on conserve le cardinal et le caractère clos sur $X$

    Lemme minimum raisonnable

    Si tout minimum pour l'inclusion de $F$ est raisonnable alors il en est de même pour $FULL(x,F)$ quelque soit $x\in F$

    nous démontrerons ce lemme à la fin, en attendant et en l'admettant,
    démontrons par récurrence sur le nombre de colonnes non pleines de $F$ clos sur $X$ que si tout minimum de $F$ est raisonnable alors $Anti(F)$ est un minorant de $F$.


    démonstration du lemme minimum raisonnable
    Supposons que tout minimum de $F$ soit raisonnable mais pas un minimum $m'\in F'=FULL(x,F)$
    Tous les élements de $F'$ qui ne contiennent pas $x$ sont raisonnables, ($x$ n'est pas un creux singulier)
    Donc $x\in m'$ (cas1)
    Les éléments de $F'$ qui s'ecrivent $d+x$ où $x\notin d\in F$ ne sont pas des minimums(cas 2)
    Si $m'\in F$ et $x\in m'$, alors $m'$ est aussi minimum dans $F$

    En effet supposons que $a\subset m'$, avec $m\ne a\in F$, par hypothèse de minimalité dans $F'$ de $m'$ on a $a+x$ non inclus dans $m'$, ce qui est absurde.
    $m'$ contient donc dans $F$ un creux non $F$-singulier en disons $y\ne x$ c'est à dire que $m'-y\in F$ et comme on $x\in m'-y$ on a encore $m'-y\in F'$ et $m'$ est raisonnable.(cas 3)

    Il reste a étudier le cas où $m=m'-x\in F$ (avec $m\notin F'$ car $m\in F'$ et $x\notin m$ est le cas 1)
    $m$ est un minimum dans $F$ (même raisonnement que pour le cas 3)
    Par hypothèse de raisonnabilité sur les minimum de $F$, il existe $y\in X$ tel que $m-y\in F$ et $y\ne x$. Pour tout $f\in F$ on a $f+x\in FULL(x,F)$ et donc $m'-y\in F'$ et $y$ n'est pas un creux singulier pour $m'$, qui est donc raisonnable.
    cqfd
  • Partie doubles/points pleins pour $x\in X$ et $F$ clos sur $X$

    $DOUBLE(x,F)=\left\{f\in F \space |\space \exists g\in F, g\triangle f=\left\{x\right\} \right\}$ ($\triangle$ désigne la différence symétrique)

    en d'autre terme c'est l'ensemble (clos) des éléments de $F$ qui ont un "double" qui ne diffèrent d'eux qu' "en $x$"

    et $FULL(x,F)=DOUBLE(x,F)\bigcup \left\{f\cup \left\{x \right\}\space |\space f\in F\setminus DOUBLE(x,F)\right\}$

    (autrement dit c'est l'ensemble obtenue en ajoutant un $x$ a tous ceux du complémentaire de la partie double qui ne contenait "pas encore" $x$)

    Si $F=FULL(x,F)$
    On dit alors que $x\in X$ est plein dans $F$ ou $F$-plein
    les seuls éléments de $FULL(x,F)$ qui ne contiennent pas $x$ sont dans la partie double de $x$

    autrement dit $x\notin f\in FULL(x,F) \Rightarrow f\in DOUBLE(x,F)$ (*****)

    Il est immédiat que
    $FULL(x,F)$ est clos sur $X$ de même cardinal que $F$

    exemples dans $E=a,b,ab,abc$ (en omettant les accolades (et les virgules) autour (et entre) les lettres $a$ $b$ et $c$)
    on a $DOUBLE(c,E)=ab,abc$ et $FULL(c,E)=ab,abc,bc,ac$
    et $FULL(a,E)=FULL(b,E)=E$ ($a$ est $b$ sont pleins dans $E$)

    Partie pleine
    Soit $F$ clos sur $X$, on dit que $a\subset X$ est partie pleine de $F$ si $\forall x\in a, FULL(x,F)=F$

    (dans notre exemples précédent (modulo l'oubli des accolades) $ab\subset abc$ est l'unique une partie pleine de $F$ qui ne soit pas un singleton)


    Lemme de remplissage

    Si $F$, clos sur $X$, et $f\subset X$, alors il existe $F'$ de même cardinal que $F$, tel que $x\notin f\Rightarrow |F_x|=|F'_x|$ et $x\in f\Rightarrow FULL(x,F')=F'$

    On dit que $F'$ est un $x$-remplissage maximal de $F$ et on écrit cela $F'<_f F$

    lemme

    pour tout $F$ clos sur $X$ et pour tout $f\in X$, il existe $G$ , $x$-remplissage maximal de $F$ et on a $\Delta (x,G)>\Delta (x,F)$ pour tout $x\in f$, avec la notation $\Delta(x,F)=||F_x|-|F^x||$
Connectez-vous ou Inscrivez-vous pour répondre.