# Functions and graphs

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.

-
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.)