MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider a finite set $X$ of order $n$ and a symmetric function $f: X \times X \rightarrow X$.

$f$ can straightforwardly be considered as a multidigraph with

  • $n$ "object" nodes, representing the elements of $X$, and

  • $n(n+1)/2$ "argument" nodes, representing the pairs of arguments of $f$.

Each of the $n$ object nodes has $n+1$ out-arrows to its corresponding argument nodes. Each of the $n(n+1)/2$ argument nodes has exactly 2 in-arrows from its correspoding object nodes and 1 out-arrow to its corresponding "function value" node (an object node).

Now invert the situation and consider an arbitrary multidigraph with $N = n + n(n+1)/2 = n(n+3)/2$ nodes with the property P, that $n$ of them (the object nodes) have $n+1$ out-arrows and another $n(n+1)/2$ of them (the argument nodes) have exactly 2 in-arrows and 1 out-arrow.

Question: Can - or rather: under which conditions can - be shown that a multidigraph with property P is bipartite, in the sense of:

  • the out-arrows of an object node go to an argument node and vice versa

  • the in-arrows of an object node come from an argument node and vice versa.

share|cite|improve this question
Your point is that you want to have unlabelled digraphs, right? So the object node x has two parallel arcs to the argument node (x,x)? I think you need to require n such parallel arcs with different targets, otherwise it seems to me that bipartness does not suffice to make the graph be a functional graph. (An example, forgetting about the functional values: consider n=3, and the disjoint union of a K_{2,4} and a digraph on three nodes, one of which has outdegree 4, the other 2 having each indegree 2) – Martin Rubey Jun 6 '10 at 8:18

It's not true even for $n=1$. Consider the graph with two nodes, $a$ and $b$, with edges as follows:

  • $a\to a$
  • $a\to b$
  • $b\to b$

Thus, $a$ has exactly two out-arrows, $b$ has exactly two in-arrows and exactly one out-arrow. So it has property $P$ for $n=1$ but is not bipartite in th sense you wanted, since both $a$ and $b$ point at themselves.

(Note that the arrow $b\to b$ contributed both to the in-arrow sum and the out-arrow sum at $b$, which may not be how you wanted to consider things.)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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