Skip to main content
MathOverflow

Return to Question

added 72 characters in body
Source Link
Dominic van der Zypen
Dominic van der Zypen
  • 48.9k
  • 8
  • 47
  • 161

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\subseteq V$$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.

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$ 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 $S\subseteq V$, and whenever $T\subseteq V$ with $J\subseteq H(T)$ then $J=H(T)$.

Question. If $S\subseteq 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.

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.

Source Link
Dominic van der Zypen
Dominic van der Zypen
  • 48.9k
  • 8
  • 47
  • 161

Maximizing "happy" vertices in splitting an infinite graph

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$ 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 $S\subseteq V$, and whenever $T\subseteq V$ with $J\subseteq H(T)$ then $J=H(T)$.

Question. If $S\subseteq 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.