[Théorie des graphes dans la théorie generale des fonctions]
On considère deux applications f et g d'un ensemble E dans un ensemble F telles que f(x)≠g(x) pour tout x dans E. Quel est le cardinal maximal d'un sous-ensemble A de E tel que les images des restrictions de f et g à A soient disjointes ? Dans le cas où E est infini, la réponse est card(E), comme l'ont montré Mekler, Pelletier et Taylor ; dans le cas fini, nous avons prouvé que le cardinal en question est plus grand ou égale à card(E)/4. Dans cet article, en utilisant les outils de la théorie des graphes, nous retrouvons ces resultats comme application directe d'un lemme d'Erdös. Nous démontrons de plus que si , alors il existe une partition dénombrable {En}n⩾1 de telle que f(En)∩g(En)=φ, pour tout n⩾1.
Consider two maps f and g from a set E into a set F such that f(x)≠g(x) for every x in E. What is the maximal cardinal of a subset A of E such that the images of the restriction of f and g to A are disjoint? Mekler, Pelletier and Taylor have shown that it is card(E) when the set E is infinite; in the finite case, we have proved that it is greater than or equal to card(E)/4. In this paper, using graph theoretical technics, we find these results as a direct application of a lemma of Erdös. Moreover, we show that if , then there exists a countable partition {En}n⩾1 of such that f(En)∩g(En)=φ, for every n⩾1.
Révisé le :
Publié le :
Amine El Sahili 1, 2
@article{CRMATH_2002__335_11_859_0, author = {Amine El Sahili}, title = {Graph-theoretical methods in general function theory}, journal = {Comptes Rendus. Math\'ematique}, pages = {859--861}, publisher = {Elsevier}, volume = {335}, number = {11}, year = {2002}, doi = {10.1016/S1631-073X(02)02585-2}, language = {en}, }
Amine El Sahili. Graph-theoretical methods in general function theory. Comptes Rendus. Mathématique, Volume 335 (2002) no. 11, pp. 859-861. doi : 10.1016/S1631-073X(02)02585-2. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/S1631-073X(02)02585-2/
[1] Functions with disjoint graphs, C. R. Acad. Sci. Paris, Série I, Volume 319 (1994), pp. 519-521
[2] On some extremal problems in graph theory, Israel J. Math. (1965), pp. 113-116
[3] On chromatic number of infinite graphs, Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, 1968, pp. 83-98
[4] A separation theorem, Abstracts Amer. Math. Soc. (1982), p. 593
Cité par Sources :
Commentaires - Politique