I spent the last week visiting the Institute for Pure and Applied Mathematics at UCLA, for a workshop on combinatorial geometry. Rather than post here about the many exciting new results I heard about (for which see the conference program) I thought I'd describe a few open problems that came up in some of the talks.

( Coloring line segments )

( Blocking visibilities among points )

( Counting spanning trees in bipartite graphs )

( Triple crossings of unit circles )

Another new paper of mine, “Area-Universal Rectangular Layouts,” with Mumford, Speckmann, and Verbeek (my third recent coauthor named Kevin), just appeared on the arXiv. It's about designing cartograms (stylized maps) in such a way that they can be morphed so that their areas represent arbitrary quantitative data about the regions they depict. I'd like to discuss it in more detail soon, but first I wanted to talk about Birkhoff's representation theorem for finite distributive lattices, the subject of a Wikipedia article I worked on recently and a key tool in our rectangular layout paper.

( Read more... )

Remove a perfect matching from a complete bipartite graph K_n,n (forming a crown graph), and count the number of (directed) Hamiltonian cycles in the remaining graph. Alternatively, remove a Hamiltonian cycle from the same complete bipartite graph, and count the number of perfect matchings in the remaining graph. The two sequences of numbers generated in this way are almost the same! (They differ by a factor of (n − 1)! from each other.) Perhaps this will be more surprising if I list the smaller of the two sequences of numbers (the number of matchings in the graph with the cycle removed) to show that they're not something familiar like powers of two or factorials. They are (starting at n = 3):

1, 2, 13, 80, 579, 4738, 43387, 439792, 4890741, 59216642, 775596313, ...

Both sets of numbers come up in the problème des ménages concerning seating plans for n couples so that men and women alternate and nobody sits next to his or her partner. The numbers of matchings are the ménage numbers describing ways of arranging the men once the women have already been seated, while the larger numbers of Hamiltonian cycles count seating plans in which everyone is free to move but only the cyclic order of the participants, and not their precise placement into chairs, is significant.

I'm not sure at this point whether the symmetry between the two graph-theoretic ways of describing these numbers is a coincidence or a piece of some sort of deeper duality.

Rather than spending much time blogging about SODA today, I spent the time instead updating the Wikipedia article on Davenport–Schinzel sequences with Gabriel Nivasch's new and very nice results tightening the bounds for the order-3 and even-order cases of these sequences.

Gabriel deservedly won the best student paper award at SODA for these results, a preprint of which can be found at arXiv:0807.0484.

Given how efficiently I was corrected about the mistake I made in yesterday's post (I had given a too-large time bound for the planar Steiner tree PTAS, now fixed I hope), I hope any necessary corrections to these edits will be equally efficient.

Several important families of objects in combinatorics and order theory can be represented as collections of dichotomies (partitions of a set into two subsets), where each pair of dichotomies in the collection must be compatible with each other. Examples, described in more detail below, are the family of weak orders on a fixed set of objects, the family of trees on a fixed set of leaves, the family of plane trees on a set of leaves with a fixed cyclic order, the family of set partitions, the family of partitions of a convex polygon by its diagonals, and the family of subsequences of a linear order or cyclic order. When this happens, we can form a graph linking compatible pairs of dichotomies, and represent the objects in question as cliques in this compatibility graph. Cliques form a median algebra: if any three cliques vote on which vertices to include or exclude, the result is again a clique. This means that the same sort of median structure can be extended to other objects such as weak orders and trees. More, we can use ideas such as the clique complex and simplex graph to form topological spaces and graphs that represent these families of objects.

( Read more... )

Gil Kalai lists five open questions about polyhedra. Two of them are ones I've worked on in a paper with Kuperberg and Ziegler:

(1) How big can the numbers of k-faces be in a polytope with n vertices and n facets? Gil asks the question for four-dimensional polytopes (where the issue is whether the numbers of edges and ridges can be larger than the numbers of vertices and facets by more than a constant factor) but the same question can be asked in any higher dimension. A simple construction forms polytopes with Omega(n^ceiling((d-1)/3))) intermediate-dimension faces and it's reasonable to hope that's the right answer. My paper with Kuperberg and Ziegler showed that there are cell complexes that look like 4-polytopes combinatorially and topologically but where the number of edges and vertices is large, but it's not obvious whether these complexes can be realized as polytopes.

(2) Are there polytopes that look simplicial in their low-dimensional faces and simple in their high dimensional faces? That is, all 2-faces should be triangles, all 3-faces tetrahedra, ..., and the same for the dual polytope. In the same paper, we showed that there are infinitely many 2-simple 2-simplicial 4-polytopes. Gil is asking for 5-simple 5-simplicial 10-polytopes.

Another of his questions, the one about whether centrally symmetric polytopes always have 3^d or more faces, came up earlier in the comment threads of this post by Terry Tao.

First question: suppose you want to cover all the edges of an n-vertex complete graph with complete bipartite subgraphs (bicliques). How many bicliques do you need?

( Read more... )

Ok, now time for the second question. Instead of covering a complete graph, let's cover a different graph G_n, in the form of a bipartite graph K_n,n minus a perfect matching. Since G_n is bipartite, we might as well describe it with a simplified adjacency matrix in which one side of the bipartition indexes the rows and the other side indexes the columns. But this simplified adjacency matrix for G_n is identical to the adjacency matrix of the clique K_n that we started with, zero on the main diagonal and all ones elsewhere! We're just interpreting it differently. In this interpretation, the bicliques we're covering G with can only cover half as many of the ones in the adjacency matrix as they could when we were covering a complete graph. So we need twice as many bicliques, right?

( Read more... )

The binomial coefficients forming Pascal's triangle count, among other things, the number of lower sets in a two-dimensional rectangular grid. What about three-dimensional grids?

( Read more... )

A linear threshold function is a function that maps n-tuples of Boolean variables to a single Boolean variable. Such a function is defined by choosing a weight w_i to each variable and a target weight W. We can then compute the function value by summing the weights of the true input variables, and letting the output be true if this sum is at least W. Geometrically, the 2ⁿ possible input tuples can be mapped to the vertices of a hypercube {-1,+1}ⁿ by making the coordinate value +1 whenever the corresponding input variable is true and -1 whenever it is false. The weights define a hyperplane in Rⁿ, such that the hypercube vertices for which the function is true are on one side of the hyperplane and the hypercube vertices for which the function is false are on the other side. It appears to be open to determine exactly how many different threshold functions exist; OEIS lists the number of threshold functions only up to eight variables. If these numbers grow exponentially with the square of the dimension (as seems likely from the OEIS data) then this would lead to an exponentially small bound on the margin of linear classifiers for hypercubes, answering Leo Kontorovich's recent question about how small these margins can get.

( Read more... )

Fields Medalist Terence Tao has a new blog on which he asks about the asymptotics of cap sets. This is a version of the no-three-in-line problem, that, as an anonymous commenter points out, should be familiar to anyone who's played Set. In Set, one has a deck of 81=3⁴ cards in which four different characteristics each take on three values: the color can be purple, green, or red; the number can be one, two, or three; the shape can be diamond, oval, or squiggle; and the pattern can be hollow, shaded, or solid. A set is a triple of cards that in each characteristic is either all the same or all different, and Tao's question is how many cards can one have without being able to pick out any set. For the 81 cards of a Set deck the answer appears to be 20, but Tao wants to know the answer more generally for decks of 3^k cards, k large.

Less new, but new to me, is Absolutely Regular, by Leonid Kontorovich, Aaron Greenhouse, and Steven J. Miller. Kontorovich recently posted a question I found interesting: for a linearly separable partition of hypercube vertices, how small can the maximum margin of a linear separator be? I think this can be dualized in a way that turns it into a question about lower-bounding how many linearly separable partitions are possible, but I don't have a complete solution.

A little more detail on the sandpile conjecture from the Babai-Gorodezky talk (and it turns out also from their proceedings paper) that I mentioned very briefly Monday.

A sandpile, in the problem studied by B+G, is an n×n grid of nonnegative integers, thought of as counting grains of sand in each cell. Whenever a grid cell contains four or more sand grains, one can tip it over by moving four of its grains one unit in each of the four orthogonal directions. This usually results in adding one to the numbers stored in four neighboring cells, but if the tipped cell is on the boundary of the grid some grains fall off the grid and are removed from the problem.

( Read more... )

The Prime Game, Jeff Shallit. There are only finitely many primes that do not have another smaller prime hidden in them as a subsequence of their decimal representations. True more generally for any set instead of "primes" and any base instead of decimal, but for decimal primes Jeff can actually tell you what the minimal ones are.

Dilworth's Theorem: in any partial ordering, the size of the largest possible antichain is equal to the smallest possible number of chains in a partition of the items into chains.

( Proof sketch )

Anyway, I've now implemented all this in PADS. It's in a new module PartialOrder.py, which also contains everything that used to be in TopologicalOrder.py. Along with the new MaximumAntichain and MinimumChainDecomposition functions, I included a TransitiveClosure function, as it was needed when the input order is given by a sparser DAG.