Cubiertas de camarilla inmejorables

Question

Sea $G=(V,E)$ sea un grafo simple no dirigido. A cubierta de camarilla es un conjunto ${\cal C}\subseteq {\cal P}(V)$ tal que

1. cada elemento de ${\cal C}$ es una camarilla, y
2. $\bigcup {\cal C} = V$ .

Llamamos cubierta de camarilla ${\cal C}$ batible si existe una cubierta de camarilla ${\cal C}_1$ tal que $$|{\cal C}_1 - {\cal C}| < |{\cal C} - {\cal C}_1|.$$ Las cubiertas de camarilla no batibles se denominan inmejorable .

Es fácil demostrar que todo grafo finito tiene una cubierta de camarilla imbatible. Pero, ¿qué ocurre con los grafos infinitos?

Answer 1

Creo que es una conjetura conocida. El caso especial de que siempre existe una cubierta de camarillas tal que la unión de dos cualesquiera de esas camarillas no es una camarilla, puede demostrarse a partir del lema de Zorn (o sin él), cf. mi libro con Totik: Problems and Theorems in Classical Set Theory, Problema 14.6.(m). Este caso especial es en realidad equivalente al axioma de elección: F. Galvin, P. Komjáth: Graph colorings and the axiom of choice, Periodica Math. Hung. 22 (1991), 71-75.