Here's a cute little geometric factoid that has something to do with one of the posts over at the 33rd Carnival of Mathematics. I'll leave it as a puzzle which post it belongs to...

Let ABC be any triangle in the Euclidean plane, and AD be any line. Form points A', B', and C' as the perpendicular projections of A onto BC, B onto AD, and C onto AD respectively. Then triangles ABC and A'B'C' are similar.

( diagram )

(Hint: in the post I have in mind, ABC is isosceles and A' is the midpoint of BC.)

A cograph is a graph formed from single vertices by disjoint union and complement operations, but I think it makes the theory a little cleaner to think of them as generated instead by the following set of three operations:

• vertex(): takes no arguments and returns a single vertex
• union(G,H): takes two graphs as arguments and returns their disjoint union
• join(G,H): takes two graphs as arguments and adds all possible edges connecting the two

( Read more... )

Every distance-hereditary graph can be represented as a circle graph, the intersection graph of the chords of a chord diagram. And every bipartite distance-hereditary graph can be represented in this way by a chord diagram in which all interior faces of the arrangement formed by the chords are quadrilaterals. But the converse is not true.

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

The local girl scouts held their annual International Day event this weekend. Each troop gets assigned a different country; they all dress up in their idea of a national costume, set up pavilions in a big square, parade around the square, and then sell food samples to each other and to their parents and siblings for a dime apiece from their pavilions. My daughter's troop ended up with Indonesia; for their costumes they all wore sarongs (with whatever tops they felt like) and for their food samples they sold klepon, sweet coconut rice-flour -dough balls stuffed with palm sugar and tasting sort of like coconut mochi. A good time was had by all, I think. Photos here.

This was my fifth International Day; photos from past years' events are here, here, here, and here.

On the subject of photography, I finally decided my old D60 was getting tired and replaced it with a Canon 40D, so this weekend's photos may be the last batch from the old camera. The newer one has 60% more pixels, 60% more light-gathering ability, twice the burst rate, and much better autofocus (the D60's weakest point). I chose a package that also included Canon's 17-85 kit lens; when I can do so, I'd rather use primes or my 70-200IS, as I'm sure the optical quality on the 17-85 isn't quite as good and it won't open as wide, but it should make a very good travel lens.

Another of my papers, “Straight skeletons of three-dimensional polyhedra” (with Gill Barequet, Mike Goodrich, and Gill's student Amir Vaxman) is now available on the arXiv. The straight skeleton is a way of representing a shape (such as a polygon in the plane) by a lower dimensional structure (a collection of line segments having roughly the same overall shape as the original polygon). It can be formed (conceptually, at least, although it takes more work to turn this into an algorithm) by continuously moving the sides of the polygon inwards at the same speed as each other, and collecting the line segments traced out by the vertices of the polygon as the sides move. It also has some architectural applications, as it describes the shape of a fixed-pitch roof over a given set of walls. Compared to the medial axis, another type of skeleton, it has the advantage of only using straight line segments and not curves, but the disadvantage of being harder to compute.

It had been thought to be difficult or impossible to define the straight skeleton in 3d: one can imagine continuously moving the sides of a polyhedron inward as before, but at certain points in this process it becomes ambiguous how to connect them up to each other. In 2d, if you know the positions of a set of lines defining a polygon, and you know the order the lines should connect up with each other, you know where the vertices must be (at the points where the lines cross) but in 3d, if you only know the positions of a set of planes defining a polyhedron, there may be multiple ways of connecting those planes together at edges and vertices. We resolve this ambiguity by using a two-dimensional straight skeleton process whenever the inward-moving sides reach a point of ambiguity.

We also have some results on more efficiently computing straight skeletons when the input is orthogonal; in this case there are no ambiguities to worry about and the resulting skeleton is provably less complicated than it might be in the general case.

I had a little difficulty getting this paper uploaded to the arXiv due to it having a large number of bitmap figures (the output of Vaxman's implementation of the algorithm for general polyhedra) and the arXiv requiring all uploads to fit in a total size of 1Mb. The solution turned out to be to use pdftex, as pdf versions of the figures compressed better than the eps format they were in before. I've usually been using pdftex anyway for my papers, but for historical reasons this one had been using postscript figures. I found these instructions for converting to pdflatex helpful (especially the part about pstex). The arXiv's instructions for submission of pdflatex are here.

In a turnaround from the usual story about a bad student threatening legal action against all the faculty who dare to assess the student as bad, a Dartmouth writing lecturer is threatening to sue her students (and some faculty, and Dartmouth itself) for discrimination. There are too many different postings to link to them all here, but there's a pretty thorough roundup at this post.

The claimed cause for the lawsuits is harassment but, as this story notes, that is not covered by the title under which the lecturer is threatening to sue.

One familiar name in all this is that of Tom Cormen, Dartmouth algorithms guru (and writing program director), mentioned in this interview as having committed the heinous crimes of (1) interrupting classes he was sitting in on, and (2) NOT interrupting the classes he was sitting in on when he stepped out of them.

I received my copy of Knuth's Art of Computer Programming, Volume 4, Fascicle 0, this week. It contains a long section on median graphs, and coincidentally I had just added a long article on median graphs to Wikipedia, so I've been reading that part with great interest.

One of the exercises, 7.1.1 ex.109, caught my attention. In it, Knuth describes the "binary majorization lattice" in which the elements are the n-bit binary numbers and in which x is greater than y if x has at least as many nonzeros as y with x's highest order nonzero bit larger than y's, x's second highest nonzero bit larger than y's, and so on. Here it is as drawn by my algorithm for drawing graphs that can be embedded on an integer grid — here the integer grid turns out to be three dimensional, and the awkward folds in the drawing are there because my algorithm doesn't know any better than to put them in.

( Read more... )

I spoke today about graph drawing at a seminar in our School of Social Sciences. They're very mathematically sophisticated over there (and more interested in combinatorics than our mathematicians are) but it was still mostly not a very technical talk — I just showed lots of pretty pictures and used them to motivate some thoughts about how I think graph drawing should be done. Slides here.

Early in the talk, I included a bit of an ad for the annual graph drawing conference, so let me do that here too. Graph drawing! Crete! September! The submission deadline is May 31, and the call for papers may be found at http://www.gd2008.org/.

Three long but interesting posts showed up today on Crooked Timber regarding academic freedom.

First, can anyone play this game? Or, is academic freedom really something different from free speech? Also covering why it might be a bad idea to have a lawyer who specializes in the First Amendment and calls it "a robust marketplace that will marginalize extremism" as Ivy League university president.

Second, some propositions. Moving from the east to the west coast, what is the philosophical basis for academic freedom? Is it a self-evident right? Is it a societal contract, in which academics receive quid (freedom) for quo (some other benefit to society that arises from free academics)? Is it just good management on the universities' part, to keep their employees happy? And what does this all have to do with whether Berkeley should continue to employ war criminal John Yoo?

And third, some resources. Less in-depth than the other two posts, but a useful list for those who find the blog coverage of this issue too shallow and want some real reading.

Been a long time since I posted any photos here, hasn't it? Here's a few more from today's Celebrate UCI / Wayzgoose / Earth Day festival. As usual, there were plenty of ethnic food booths, battling SCAdians, classic cars, kiddie rides, and music and dance performances — a pleasant way to spend an afternoon.

Jeff Shallit takes his turn at posting Carnival of Mathematics #31.

I'm way behind on reading arXiv postings (and other recent papers, for that matter, other than what I've had to for various program committees), but I've kept pointers to some interesting older ones in hopes of catching up later. The three here don't really go very far towards catching up, but they're at least a start.

( Tantrix )

( Phutball )

( Fanorona )

I just created the following image of a pentagram for Wikipedia:

( cut for large image )

If you look at the source code I used to draw it, you'll see that it uses neusis, or the modern equivalent, binary search, to find the appropriate scale of the outside pentagram relative to the inside one so that the points all line up. (You'll also see that I don't comment heavily when I write quick one-off code like this, but I hope it's short enough to be readable anyway.) Is this figure drawable with compass and unmarked straightedge alone?

(Hint: what kind of function is the binary search finding the root of?)

Via Mihai, who in turn got it from Joachim: the Scandinavian Workshop on Algorithm Theory (SWAT) acceptances. In other news, Joachim G. has a blog. You'd think "Joachim G." would be sufficient to identify a theorist uniquely, wouldn't you? But no, this is Joachim Gudmundsson, not Joachim Giesen.

And via Michael M.: the ICALP track A (algorithms and theory) acceptances.

Mihai also has an accurate description (from his point of view on the SWAT committee) of how the ICALP committee worked. Leslie Goldberg did a great job of making it run smoothly, though, and I think we made a good set of decisions.

Via CACM: UT Southwestern's Deja Vu project has applied text pattern matching algorithms to all the titles and abstracts in Medline and found up to 200,000 duplicates. Many of them have benign explanations (e.g. the first one I saw was a Chinese-language paper and its English-language translation, by the same authors) but many others are likely plagiarism: the database currently lists 200 duplicate pairs of abstracts with no author in common. This is just in the abstracts; I imagine that additional similarities would be turned up in a full-text search.

30th Carnival of Mathematics, now up at The Number Warrior.

When I teach shortest paths in my undergraduate algorithms classes, the methods I consider most important (in roughly that order) are breadth first search, Dijkstra's algorithm, A*, the linear time DAG shortest path algorithm (section 24.2 of CLRS), and Bellman-Ford. Every self-respecting computer scientist knows the first two, but it came as a bit of a shock to me to discover that very few of our incoming graduate students had even heard of A*.

( A* as preconditioner )

From the link below:

The world’s largest database on [scientific field], containing citations with abstracts to scientific articles, reports, books, and unpublished reports ... has been changed so that one can no longer search the term [XXX] ... As the representative from [the database] states, “As a federally funded project, we decided this was best for now.”

See this link (or these earlier ones) for details. And don't tell me I'm censoring anything for leaving out those details here: I've left out the key words describing exactly who at Hopkins runs this database and what they censored, deliberately, not as a matter of censorship but because I think this is appalling no matter the field and I'd prefer to focus more on issues of academic freedom and less on any emotional reactions people might have to the specific topic. It's a term that is relevant and likely to be searched within this field of scientific inquiry. It's still present in its uncensored glory if you follow the link.

ETA: Wired, /., BB; C+L update, NYT, JHU.

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