2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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) $\endgroup$ Jun 6, 2010 at 8:18

1 Answer 1

1
$\begingroup$

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

$\endgroup$

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.