| Full text | |
| Author(s): |
Aurichi, Leandro Fiorini
;
Real, Lucas Silva Sinzato
Total Authors: 2
|
| Document type: | Journal article |
| Source: | JOURNAL OF LOGIC AND COMPUTATION; v. N/A, p. 8-pg., 2023-11-21. |
| Abstract | |
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) | |
| FAPESP's process: | 19/22344-0 - Infinite combinatorics and combinatorical games |
| Grantee: | Leandro Fiorini Aurichi |
| Support Opportunities: | Regular Research Grants |
| FAPESP's process: | 23/00595-6 - Infinite graphs and applications of set-theory |
| Grantee: | Leandro Fiorini Aurichi |
| Support Opportunities: | Regular Research Grants |
| FAPESP's process: | 21/13373-6 - A study of infinite graphs through the problem of describing Unfriendly Partitions |
| Grantee: | Lucas Silva Sinzato Real |
| Support Opportunities: | Scholarships in Brazil - Master |