Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
104 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

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

Envoyé par lesmathspointclaires 
antithèse d'un X-set clos par union
il y a quatre années
pour des renseignement sur mes reflexions précédentes à propos de la conjecture de Frankl et la stabilité par union voir le lien :
[www.les-mathematiques.net] (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 (*) )



Edité 9 fois. La derni&egrave;re correction date de il y a quatre ann&eacute;es et a &eacute;t&eacute; effectu&eacute;e par lesmathspointclaires.
cas particulier interessant
il y a quatre années
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



Edité 3 fois. La derni&egrave;re correction date de il y a quatre ann&eacute;es et a &eacute;t&eacute; effectu&eacute;e par lesmathspointclaires.
terminlogie/lemme de remplissage
il y a quatre années
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||$



Edité 5 fois. La derni&egrave;re correction date de il y a quatre ann&eacute;es et a &eacute;t&eacute; effectu&eacute;e par lesmathspointclaires.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 140 706, Messages: 1 376 281, Utilisateurs: 25 644.
Notre dernier utilisateur inscrit EPFL.


Ce forum
Discussions: 785, Messages: 6 304.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page