Motivation. At a recent gathering of co-workers, somebody said that he thinks that of all the people present that he knows, about half are happy with the current COVID19 measures, and the other half are not. Which made me put this into a graph question: Given a finite, simple, undirected graph $G = (V,E)$, we say that G is "perfectly balanceable" if there is a set $C\subseteq V$ such that for every $v\in V$, exactly half of its neighbors are in $C$. Clearly, if a vertex has an odd number of neighbors, the graph cannot be perfectly balanceable. So, below I try to introduce a "discrepancy measure" that indicates how far a graph is from being perfectly balanceable.

Formal version. Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$, let $N(v)=\{w\in V: \{v,w\}\in E\}$. For $v\in V$ and $C\subseteq V$ let the discrepancy of $v$ with respect to $C$ be $$\text{d}_C(v) = \big|\#\big(N(v) \cap C\big) - \#\big(N(v) \cap(V\setminus C)\big)\big|\;,$$ where $\#(\cdot)$ denotes the size of a (finite) set. The maximal discrepancy of any vertex with respect to $C$ is denoted by $$\text{md}_G(C) = \max\{\text{d}_C(v): v\in V\}.$$ Clearly, we have $\text{md}_G(C) = \text{md}_G(V\setminus C)$ for all $C\subseteq V$. The overall discrepancy of $G$ finally is defined by $$\text{discr}(G) = \min\{\text{md}_G(C):C\subseteq V\}.$$

For example, it is not hard to see chat $\text{discr}(C_4) = 0$ for the circle on $4$ vertices: If the circle is $0 - 1 - 2 - 3 - 0$, take $C = \{0,1\}$ for getting $\text{md}_{C_4}(C) = 0$ and therefore $\text{discr}(C_4) = 0$. On the other hand, for any graph $G$ with a vertex $v$ such that $N(v)$ has an odd number of elements, we have $\text{discr}(G) > 0$.

Question. Given a positive integer $n>0$, is there a graph $G=(V,E)$ such that $\text{discr}(G) = n$?


1 Answer 1


Yes, there is such a graph. Let $A = \{1,\dots,2n\}$, let $B = \{b \subseteq A \colon |b|=n\}$, and let $G$ be a graph with vertex set $A \uplus B$ and an edge between $a\in A$ and $b\in B$ if $a \in b$.

For any set $C$ there are either $n$ vertices in $A \cap C$ or $n$ vertices in $A\setminus C$, and thus there is a vertex $b \in B$ with $d_C(b) = n$.

  • $\begingroup$ Really neat example -- thanks! $\endgroup$ Oct 14, 2021 at 19:43
  • 1
    $\begingroup$ Your example definitely has discrepancy at least $n$, but I am not sure it has discrepancy exactly $n$, since the neighbourhoods of the vertices in $A$ might have discrepancy larger than $n$. It is easy to fix this, by adding a copy $b'$ of each $b \in B$, and putting exactly one of $b,b'$ in $C$. This shows that graph discrepancy can model the usual notion of hypergraph discrepancy. $\endgroup$
    – Tony Huynh
    Oct 14, 2021 at 22:42

Your Answer

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

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