I'm far behind on my reading, so consider this as the first installment in my attempts to catch up.

( Efficient dual pairs of spanning trees )

( Robust de-anonymization of large datasets )

( Being first and ranking journals )

( Hinged dissections exist )

( Tribes of cubic partial cubes )

The Foster census lists cubic symmetric graphs; that is, graphs in which the vertices all have three edges, and some symmetry takes any directed edge to any other directed edge.

Among these graphs, the one with 24 vertices clearly deserves a name, as Ed Pegg wrote in his online MAA column in 2003. Naming it after a person is no good: the first person to write about it was Foster [Foster, R. M. (1932), "Geometrical circuits of electrical networks", Transactions of the American Institute of Electrical Engineers 51: 309–317], who gives his name to the whole list of cubic symmetric graphs, and apparently the second was Coxeter [Coxeter, H. S. M. (1950), "Self-dual configurations and regular graphs", Bulletin of the American Mathematical Society 56: 413–455] for whom plenty of graphs are already named. For lack of a better name, I'm going to call it the Nauru graph, because the flag of Nauru has a 12-point star greatly resembling the one in one of the standard drawings of this graph.

( Read more... )

Inspired by my previous post on a truncated-cube Cayley graph for permutations on four elements, I tried looking at similar presentations for larger permutation groups.

( Read more... )

The permutohedron (convex hull of permutations of (1,2,3,4), in the 3d subspace x+y+z+w=10 of R⁴) provides a convenient geometric representation of the permutations on four items, as the 24 vertices of a truncated octahedron. But the same 24-vertex graph that forms the skeleton of the permutohedron is also a Cayley graph of the symmetric group of permutations on four items, if one labels the vertices differently (by the inverses of their permutohedron labels) and uses as group generators the transpositions of adjacent items.

A different 24-vertex polyhedron, the truncated cube, also has a standard representation as a Cayley graph, of a different group: it is an example of the cube-connected cycles network, a Cayley graph of the group that acts on binary strings by cyclic shifts and bit-flipping.

But the truncated cube is itself in a different way the Cayley graph of the symmetric group. The generators are transpositions of the first two permutation elements and rotations of the last three elements. Behold:

( cut for large image )

I guess this means the CCC action on three-bit strings can be encoded by permutations on four items somehow? The first element in the permutation and the parity of the permutation together encode which bits have been flipped, and the rotation of the remaining permutation items encodes the rotation of the bitstring, but I'm not seeing a way of describing this correspondence clearly.

ETA: Although both truncated cubes are Cayley graphs of groups generated by order-2 and order-3 elements, they are not isomorphically labeled as Cayley graphs. In the permutation Cayley graph, the triangles are all oriented the same way as each other, while in the CCC Cayley graph, the triangles alternate orientations. That is, the permutation group has the presentation <x, y | x², y³, (xy)⁴>, while the CCC group has the presentation <x, y | x², y³, (xyxy^-1)²>. Perhaps this difference explains the difficulty in relating the CCC action to permutations.

The lattice of feasible sets of an antimatroid embeds isometrically into the hypercube of all sets on the same elements, of course. So that's one partial cube from an antimatroid. But there's another: its set of basic words (the maximal words in the formal language interpretation of the antimatroid) with two words adjacent if they differ by a single transposition. Each basic word is a permutation on the elements of the antimatroid, so can be viewed as a vertex of the permutohedron describing all permutations connected by transpositions; it turns out that the basic words of an antimatroid always form an isometric subgraph of the permutohedron.

The proof is straightforward, and involves showing that one can connect two any basic words by a path of transpositions. One way to do this is to find the position of the first symbol at which the two words differ, and perform a sequence of transpositions that makes the two sequences the same at that position; each such transposition can be shown to reduce the number of inversions separating the two basic words, and the antimatroid axioms can be used to show that each transposition produces another basic word.

For instance, in the case of antimatroids over a three-element set, the permutohedron on three elements is a hexagon. It has 25 isometric subsets. 19 of these correspond to the sets of linear extensions of a partial order: six single vertices correspond to the six total orders on three elements, six edges correspond to the six partial orders in which one element is larger than or smaller than the other two, six two-edge paths correspond to the six partial orders in which only two elements are comparable, and the whole hexagon corresponds to the partial order in which no two elements are comparable. Each of these partial orders can be viewed as an antimatroid, but there are three more antimatroids that do not come from partial orders, and that correspond to three of the six possible length-three paths in the hexagon. Finally, the remaining three length-three paths do not correspond to antimatroids directly, but rather, are the reverses of sets of basic words of antimatroids.

I have no idea what, if any, algorithmic consequences this may have.

An st-orientation of an undirected graph is an assignment of a direction for each edge, turning it into a directed acyclic graph with one source and one sink. For any biconnected graph such an orientation may be found in linear time via depth first search: For each DFS tree edge (u,v) (where u is the parent), orient (u,v) oppositely to the DFS tree edge down from the low vertex of v into the subtree containing u and v. For each nontree edge (u,v) (where u is the top vertex), orient (u,v) the same as the DFS tree edge down from u into the subtree containing v. I've been meaning to add this to PADS for a while, after lecturing on it as part of the graph drawing section of my undergraduate graph algorithms class this quarter, but it's now there (in Biconnectivity.py) after I found motivation in a connection to xyz graph recognition:

Any biconnected 3-regular graph can be partitioned in at most 2^n/2-1 different ways into three matchings. The idea of the proof is to process the vertices in a topological ordering (also added to PADS, in TopologicalOrder.py) of an st-orientation, and when processing each vertex choose how to assign the adjacent edges to the three matchings, consistently with prior choices. We only have to make a binary choice at the n/2-1 vertices with one incoming and two outgoing edges; at all other vertices there is no choice to be made. This leads to an O(n 2^n/2) time algorithm for recognizing xyz graphs, which I implemented as part of PADS in xyzGraph.py.

( Read more... )

The n! permutations of the vector (1,2,3,...,n) lie on a hyperplane, so their convex hull forms an (n-1)-dimensional shape, known as the permutohedron. E.g., the three-dimensional permutohedron, representing the permutations on four items, is below.

( Permutohedron )

Two permutations are connected by an edge in this shape if they differ by swapping two items that differ in value by one. The graph of vertices and edges of this shape is one of the standard examples of partial cubes, although it doesn't look very cubical in this form.

But now imagine the same graph, rearranged by moving every permutation to its inverse. What do you get?

( Inverse permutohedron )

I just found this paper: Cubic inflation, mirror graphs, regular maps, and partial cubes, by Brešar, Klavžar, Lipovec, and Mohar. According to it, not much is known about the problem of listing partial cubes in which all vertices have exactly three neighbors — there is one known infinite family (the prisms) and several other sporadic examples, among which is the permutohedron (truncated octahedron). The paper defines an expansion operation for graphs on surfaces (essentially the same as the gem representation from topological graph theory) which, when applied to certain planar graphs, leads to a few more examples.

This immediately made me think about zonohedra, since the truncated octahedron is one. Also, any zonohedron has a skeleton that's dual to a central plane arrangement in three-dimensional space (the arrangement of planes through the origin that are perpendicular to the edges of the zonohedron) and, as with the dual of any affine hyperplane arrangement, it's automatically a partial cube. So I thought I'd go through my catalog of interesting symmetric zonohedra to see whether any of them lead to additional cubic partial cubes.

( Read more... )