1
$\begingroup$

This question is motivated by a real life task (which is briefly described after the question.)

Let $G=(V,E)$ be an infinite graph. For $v\in V$ let $N(v) = \{x\in V: \{v,x\}\in E\}$. If $S\subseteq V$ with $\emptyset\neq S\neq V$ we say that $v\in V$ is happy with respect to $S$ if $$N(v)\cup \{v\}\subseteq S \text{ or }(N(v)\cup\{v\})\cap S =\emptyset.$$

We set $H(S)$ to be the collection of happy vertices with respect to $S$ and we say that $J\subseteq V$ is maximally happy if $J=H(S)$ for some proper nonempty subset $S\subseteq V$, and whenever $T\subseteq V$ is proper, nonempty with $J\subseteq H(T)$ then $J=H(T)$.

Question. If $S$ is a proper, nonempty subset of $V$, is $H(S)$ contained in some maximally happy subset of $V$?

Real life motivation. I was co-organizer of a children's birthday party recently. Some of the attendants were friends of each other, others not. I was given the task of splitting the attendants into 2 teams such that for as many attendants $a$ as possible, $a$'s friends were on the same team as $a$ -- a socially tricky task.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ if $S=V$, are all happy? $\endgroup$
    – Fedor Petrov
    Commented Mar 8, 2019 at 8:43
  • $\begingroup$ Right - I want to exclude $S \in \{\emptyset, V\}$ - thanks for your remark! $\endgroup$
    – Dominic van der Zypen
    Commented Mar 8, 2019 at 8:59
  • 1
    $\begingroup$ But your party surely didn't have an infinite number of kids :-) $\endgroup$
    – kodlu
    Commented Mar 9, 2019 at 0:04
  • $\begingroup$ @kodlu At times it felt as if it did ;-) $\endgroup$
    – Dominic van der Zypen
    Commented Mar 9, 2019 at 8:06
  • $\begingroup$ FWIW, if you search for "happy coloring", you'll come across the problem of completing the partial vertex-coloring of a graph so as to maximize the number of happy edges (an edge is happy if its endpoints have the same color). There is a vertex variant as well, where the goal is to maximize the number of vertices whose neighborhood has received the same color. These problems might be motivated by team-building applications. $\endgroup$
    – Juho
    Commented Mar 14, 2019 at 19:37

1 Answer 1

Reset to default
2
$\begingroup$

I think, no. Imagine that we have infinitely many boys $b_1,b_2,\dots$ and girls $g_1,g_2,\dots$ such that all boys are mutual friends, all girls are mutual friends and $b_i,g_j$ are friends if and only if $i\geqslant j$. If $b_1$ is happy, all boys and $g_1$ must be in the same part (without loss of generality not in $S$), therefore $S$ must contain some girl, let $m:=\min\{i:g_i\in S\}$. Then $H(S)=\{b_1,\dots,b_{m-1}\}$. So, clearly there is no maximal happy set containing $b_1$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .