| Texto completo | |
| Autor(es): |
Aurichi, Leandro Fiorini
;
Real, Lucas Silva Sinzato
Número total de Autores: 2
|
| Tipo de documento: | Artigo Científico |
| Fonte: | JOURNAL OF LOGIC AND COMPUTATION; v. N/A, p. 8-pg., 2023-11-21. |
| Resumo | |
An unfriendly partition of a graph $G = (V,E)$ is a function $c: V \to 2$ such that $|\{x\in N(v): c(x)\neq c(v)\}|\geq |\{x\in N(v): c(x)=c(v)\}|$ for every vertex $v\in V$, where $N(v)$ denotes its neighborhood. It was conjectured by Cowan and Emerson [] that every graph has an unfriendly partition, but Milner and Shelah in [] found counterexamples for that statement by analysing graphs with uncountably many vertices. Curiously, none of their graphs have vertices with finite degree. Therefore, as a natural direction to approach, in this paper we search for the least cardinality of a graph with this property and that admits no unfriendly partitions. Actually, among some other independence results, we conclude that this value cannot be precisely determined within $\textrm {ZFC}$, in the sense that it may vary from model to model of set theory. (AU) | |
| Processo FAPESP: | 19/22344-0 - Combinatória infinita e jogos combinatórios |
| Beneficiário: | Leandro Fiorini Aurichi |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |
| Processo FAPESP: | 23/00595-6 - Grafos infinitos e aplicações de teoria dos conjuntos |
| Beneficiário: | Leandro Fiorini Aurichi |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |
| Processo FAPESP: | 21/13373-6 - Um estudo de grafos infinitos por meio do problema de determinar Unfriendly Partitions |
| Beneficiário: | Lucas Silva Sinzato Real |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |