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?

Improve this question
$\endgroup$
5
  • 6
    $\begingroup$ What's an example where $\mathrm{dr}(G)\ge 3$? $\endgroup$
    – Timothy Chow
    Commented 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$
    – Dominic van der Zypen
    Commented 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$
    – Timothy Chow
    Commented 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
    Commented Apr 22, 2021 at 22:15
  • 3
    $\begingroup$ @bof You should spell out the details and post that as an answer. $\endgroup$
    – Timothy Chow
    Commented Apr 22, 2021 at 23:18

1 Answer 1

Reset to default
12
$\begingroup$

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

Improve this answer
$\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$
    – Sam Hopkins
    Commented 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
    Commented 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$
    – Florian Lehner
    Commented Apr 23, 2021 at 5:56

You must log in to answer this question.

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