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 directed graphs where all nodes have 2 inputs and 2 outputs. If we design a box with N inputs and N outputs, what is the smallest number of nodes it must contain to satisfy “pair symmetry” (i.e., each input is paired with some output, but relabeling the N pairs does not change the graph). Please specify the corresponding minimal graph solutions for N=3 and N=4.

Here are two graph examples to help show what I'm looking for: alt text

share|cite|improve this question
I will be honest, I do not understand your question. In particular, the meaning of "box", "input", "output", and "pair" are not clear. Perhaps you should explain your examples in more detail. – fkenter Apr 12 '13 at 9:45
Each node has two lines with arrows indicating inward flow and two lines with arrows indicating outward flow; these are the two inputs and two outputs (this should be natural to people familiar with directed graphs). To draw this fast, I didn't show arrows on some lines, but please consider all lines to have a flow arrow. Both of my examples have 3 inputs and 3 outputs which are unconnected which can be itemized in pairs by writing in1, out1, in2, out2, in3, out3. Box is more like "black box" where this whole construction is like a node with many inputs and outputs. – bobuhito Apr 12 '13 at 23:14
As far as I undestand, the question may be formulated as follows. We have a digraph where each vertex has both in- and out-degrees equal to 2. $n$ independent vertices are marked (there are in/outputs of the black box), and for every permutation of the marked vertices there exists an automorphism of the graph inducing exactly this permutation. Is this what you meant? – Ilya Bogdanov Apr 13 '13 at 9:52
Yes, but marking 2*n independent vertices is probably required (as in the left example above) since I really wanted to mark the lines from the vertices. There are really n labels for permutation because of my pairing. The automorphism then needs to induce the same pairs. If you're curious, this is a practical application for building a network with many inter-communicating IOs from small primitive routers. – bobuhito Apr 13 '13 at 12:59

Your Answer


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

Browse other questions tagged or ask your own question.