13
$\begingroup$

Motivation. A while ago I attended a party and I only knew some, but not all, of the attendees. There were 2 kinds of drinks: beer and soda. I noticed that amongst my acquaintances, more than half drank beer. So in order to go against what I perceived as the mainstream ("drink a beer"), I picked a soda. Then I wondered whether a beer / soda mapping to all the guests is possible so that everyone has a drink such that at least half of his acquaintances have the other drink.

Let's formalize this.

Formal version. Let $G=(V,E)$ be a simple, undirected graph (not necessarily finite). For $v\in V$, let $N(v) = \{w\in V: \{v,w\}\in E\}.$

If $\kappa > 0$ is a cardinal, we call a map $d: V \to \kappa$ a "drinking map" if for all $v\in V$ with $N(v) \neq \emptyset$ we have $$|N(v)\cap d^{-1}(\{d(v)\})| \leq |N(v) \setminus d^{-1}(\{d(v)\})|.$$

(We imagine $d(v)$ to be the "drink" that $v$ is having, and $v$ does not want that more than half of her friends are having $d(v)$ as well.)

Let the "drinking number" of $G$ be the smallest cardinal $\kappa$ such that there is a "drinking map" $d: V\to \kappa$, and denote it by $\text{dr}(G)$.

Question. Can $\text{dr}(G)$ become arbitrarily large for finite graphs? How about infinite graphs?

$\endgroup$
5
  • 6
    $\begingroup$ What's an example where $\mathrm{dr}(G)\ge 3$? $\endgroup$ Apr 22, 2021 at 15:55
  • $\begingroup$ I don't have such an example and would think that $\text{dr}(G) \leq 2$ for finite graphs. I have no idea about infinite graphs concerning the drinking number. $\endgroup$ Apr 22, 2021 at 20:16
  • 3
    $\begingroup$ I found a paper, Integer programming approach to static monopolies in graphs, whose abstract says, "A subset $M$ of vertices of a graph is called a static monopoly, if any vertex $v$ outside $M$ has at least $\lceil{1\over 2}\deg(v)\rceil$ neighbors in $M$." So the statement that $\mathrm{dr}(G)\le 2$ for a finite graph $G$ is equivalent to the statement that the vertex set of $G$ can be partitioned into two disjoint static monopolies. $\endgroup$ Apr 22, 2021 at 21:24
  • 4
    $\begingroup$ In human language, you want to color the vertices of a graph so that, for each vertex $v$, at most half the neighbors of $v$ have the same color as $v$. For a finite graph it's quite easy to show that $2$ colors are enough: just tale a $2$-coloring which minimizes the number of edges joining vertices of the same color. (I'm sure this question has been answered more than once on math.stackexchange but I can't find it now.) The answer is probably the same for infinite graphs but I haven't thought about that. $\endgroup$
    – bof
    Apr 22, 2021 at 22:15
  • 3
    $\begingroup$ @bof You should spell out the details and post that as an answer. $\endgroup$ Apr 22, 2021 at 23:18

1 Answer 1

12
$\begingroup$

Known as unfriendly partition conjecture. Open for countable graphs: http://www.openproblemgarden.org/op/unfriendly_partitions.

$\endgroup$
3
  • 2
    $\begingroup$ Specifically, according to the link, it is open whether (in the language of the OP) $\mathrm{dr}(G)\leq 2$ for every countably infinite graph $G$. The link explains why for finite graphs $G$ this is easily seen to be true (as also mentioned in the comment of bof above). $\endgroup$ Apr 22, 2021 at 23:59
  • 1
    $\begingroup$ Could you briefly describe the Milner–Shelah uncountable counterexample, so that this won't be a "link-only" answer? Does their counterexample have dr(G) arbitrarily large, or just dr(G)=3? $\endgroup$
    – bof
    Apr 23, 2021 at 0:13
  • 3
    $\begingroup$ Milner and Shelah not only show that there are graphs with no unfriendly 2-partition, they also prove that every graph has an unfriendly 3-partition $\endgroup$ Apr 23, 2021 at 5:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.