?

Log in

0xDE
27 January 2016 @ 09:59 pm
The image below is a drawing of (part of) a pseudoline arrangement, a collection of curves in the plane that behave like lines in the sense that each curve partitions the plane into two unbounded regions and each two curves have exactly one point of intersection, where they cross. It's from my latest arXiv preprint, "Convex-Arc Drawings of Pseudolines" (with Mereke van Garderen, Bettina Speckmann, and Torsten Ueckerdt, arXiv:1601.06865).



Read more...Collapse )
 
 
0xDE
21 January 2016 @ 03:59 pm
In my previous post here I remarked that the hypercubes are the face lattices of simplexes. I also drew the face lattice of a square, which you might have noticed forms a planar graph, the graph of another polyhedron (the tetragonal trapezohedron, an octahedron with eight kite-shaped faces). This turns out not to be a coincidence. For every many (see comments) d-dimensional convex polytopes P, the covering graph of its face lattice is the graph of a (d + 1)-dimensional convex polytope, which for lack of a better name I'll call the face incidence polytope, or incidence polytope for short (although that shorter phrase does already have a different meaning).

Read more...Collapse )
 
 
0xDE

The binary strings of a given length, like the length-8 string "11011110" in the name of my blog, can be thought of as naming the vertices of a hypercube of the same dimension: each bit is one of the Cartesian coordinates of a vertex. In the same way, binary strings with wildcard characters, like "11***1*0", can be thought of as naming the nonempty faces of the hypercube; the number of stars gives the dimension of the face, up to the string "********" which represents the whole cube. But there's one more face, the empty set Ø, which cannot be represented in the same way.

As with the collection of faces of any polyhedron, the faces of a hypercube can be partially ordered by inclusion, and this partial order forms a lattice: every family of faces has a unique meet (its greatest lower bound, the intersection of all the faces), and a unique join (its least upper bound, the unique minimal face that contains all of them). For instance, the meet of two opposite sides of an ordinary 3-dimensional cube (for instance the two sides **0 and **1) is the empty set (that's why Ø needs to be a face) and the join of the same two opposite sides is the whole cube ***. This is the face lattice of the hypercube. (The hypercube itself can also be viewed as a face lattice of another kind of polyhedron, a simplex.)

Here's an example, for the face lattice of a square (a 2-dimensional cube). The inclusion ordering is shown by the edges, and each lattice element is labeled both by the part of the square it represents and by the corresponding wildcard string.

Read more...Collapse )
 
 
 
0xDE
12 January 2016 @ 11:53 pm
The 27th ACM-SIAM Symposium on Discrete Algorithms, in Arlington, Virginia, just finished, along with its satellite workshops ALENEX (experimental algorithmics, one of the most heavily rejected topics from SODA) and ANALCO (analytic combinatorics). With four parallel sessions going at most times, there's no way to take in everything, so here are my impressions of the small fraction I saw.

Read more...Collapse )
 
 
0xDE
05 January 2016 @ 10:34 pm
As in past years, here's a roundup of what's been happening in the data structures and algorithms (cs.DS) section of arXiv.org. Over the last year, there were 1340 new algorithms preprints on arXiv; that's up about 13% from 1182 in 2014. The explosive growth rate of this section has been gradually diminishing over the years, but this time it didn't: it's higher than 2014's 10% growth rate. Statistics on arXiv submissions more generally are also available.

I picked out the following ten papers (listed chronologically) as being particularly interesting to me. I'm not going to claim that they're in any objective sense the best of the year. Nevertheless I hope they're interesting to others as well.Read more...Collapse )
 
 
 
0xDE
21 December 2015 @ 05:55 pm
A hypergraph is just another way of talking about a family of sets: one thinks of the elements of the sets as vertices and the sets themselves as being like edges of a graph. Except that, unlike edges, sets in a family of sets can have more than two vertices, so we call them hyperedges rather than edges. An r-uniform hypergraph is one in which all the hyperedges have the same number of vertices as each other; for instance, a 2-uniform hypergraph is just an ordinary graph.

If the vertices of a hypergraph are given two colors (black and white), the discrepancy of the coloring measures how evenly each hyperedge is colored. In an ordinary graph, a proper 2-coloring has equal numbers of each color in each edge, and we want to get as close to that as we can in a hypergraph as well. So the discrepancy of a hyperedge is defined to be the absolute value of the difference between the numbers of black and white vertices, the discrepancy of a coloring is defined as the maximum of the discrepancies of any of the edges, and the discrepancy of a hypergraph is defined as the minimum discrepancy of any of its 2-colorings. For instance, the 4-uniform hypergraph shown as a Venn diagram below has discrepancy 2: it turns out not to be possible to 2-color the vertices so that all four hyperedges are evenly balanced between black and white. For if it were, the three lower sets (red, blue, and yellow, all sharing the bottom three vertices but each with a different top vertex) would force the three top vertices to have the same color as each other, causing the upper green set to be unbalanced.



How many hyperedges must an r-uniform hypergraph have in order to force it to be unbalanced? Read more...Collapse )
 
 
0xDE
18 December 2015 @ 08:37 pm
I have a few new additions to my unmet-coauthor list in my latest arXiv preprint, "On the Planar Split Thickness of Graphs", arXiv:1512.04839, to appear at LATIN 2016.

The paper is on the following kind of graph drawing, where we draw each vertex multiple times (with labels so you can see which vertices are repeated where). To interpret the drawing, take the union of the adjacencies of the copies. For instance, the vertex d, repeated at the top of the drawing and the lower center, is adjacent to 6, 7, 2, 3, 0 (from the top), and also to 1, 4, 5, 8, 9 (from the bottom). If you check more carefully you'll see that each letter-digit pair is adjacent, so this is a complete bipartite graph.



This drawing style is related to graph minors (where the repeated copies of each vertex need to form a connected subgraph) and graph thickness (where only one copy of each vertex is allowed per connected component of the drawing) but without the constraints of either, allowing a little more flexibility in what can be drawn with a given amount of repetition. For instance, the complete bipartite graphs K6,10 (shown above), K5,16, and K7,8 can all be drawn this way with only two repetitions per vertex, but cannot be drawn with thickness two.

Unfortunately, it's NP-hard to find a drawing of this type with as few repetitions per vertex as possible. But fortunately, there are some important special cases where it's not so hard. In particular, one of our results is to solve the problem on graphs of bounded treewidth. The algorithm uses Courcelle's theorem, so there's probably a lot of room to make it more practical...
 
 
 
0xDE
07 December 2015 @ 09:35 pm
This is related to my post yesterday, which demonstrated that simplicial convex polyhedra (all faces are triangles) with integer edge lengths can be forced to have nasty vertex coordinates, without any closed form solution. How big do the edge lengths need to be for this to happen? My guess is that lengths 1 and 2 should be enough, but I haven't worked out an explicit example. But length 1 alone is not enough.

Read more...Collapse )
 
 
0xDE
The cube has the nice symmetric set of Cartesian vertex coordinates (±1, ±1, ±1). These give it an edge length of 2, but if you want any other number s just scale by s/2. Similarly, the regular octahedron can be give coordinates that are all the possible permutations of (0, 0, ±1), and the regular tetrahedron can be given coordinates that are a subset of the cube's vertices, the ones with an even number of plus signs; in both cases the scale factor involves the square root of two. The regular dodecahedron can be formed from the eight vertices of a cube by adding twelve more vertices with coordinates formed by cyclically permuting (0, ±φ, ±1/φ), where φ is the golden ratio; its scaling factor also involves the golden ratio. And the regular icosahedron, with side length 2 (like the cube, and with the same scaling factor), has coordinates given by all cyclic permutations of (0, ±1, ±φ). The three subsets of four vertices having the same cyclic permutation as each other form three golden rectangles, which interlock in the pattern of the Borromean rings and have the icosahedron as their convex hull:



It's also possible to make irregular variants of these polyhedra (or of any other polyhedron), with the same combinatorial structure and integer coordinates. For instance, the cyclic permutations of (0, ±1, ±2) give an irregular icosahedron. Finding small integer coordinates for a polyhedron combinatorially equivalent to the regular dodecahedron makes an amusing exercise, and bounding how big the coordinates need to be to realize all polyhedra remains an intriguing open problem.

Given all this, you might be forgiven for thinking that every polyhedron has a nice closed-form formula for its vertex coordinates. But when the geometry and not just the combinatorics of the polyhedron is specified, it's not true, even when the polyhedron's faces are particularly simple (say, integer-sided triangles).

Read more...Collapse )
Tags:
 
 
0xDE
30 November 2015 @ 11:05 pm
 
 
0xDE
24 November 2015 @ 02:49 pm
Jenny Lam, my teaching assistant for algorithms this quarter, passed today her thesis defense. She has been working with Sandy Irani, primarily on online algorithms for replacement and memory management strategies in heterogeneous caches (such as web proxies that have to maintain copies of documents of widely varying sizes), and has three papers on that subject, one at ALENEX and two at Middleware. She also has another paper on security-related algorithms in submission, which I'm also a co-author on. My understanding is that she will be teaching next semester at Pomona College on a temporary basis, while she looks for a more permanent position. Congratulations!
Tags:
 
 
0xDE
23 November 2015 @ 11:27 am
This weekend I helped add a new sequence to OEIS, A264737 of the prime numbers that divide at least one telephone number (the numbers of matchings in a complete graph etc).

The telephone numbers obey a simple recurrence T(n) = T(n-1) + (n-1)T(n-2), and it's easy to test whether a prime number p divides at least one telephone number by running this recurrence modulo p. Whenever n is 1 mod p, the right hand side of the recurrence simplifies to T(n-1) mod p, and we get two consecutive numbers that are equal mod p; After that point, the recurrence continues as it would from its initial conditiions (two consecutive ones), multiplied mod p by some unknown factor. Therefore, the recurrence mod p either repeats exactly with period p, or it becomes identically zero (as it does for p=2), or it repeats with a higher period that is a multiple of p and a divisor of p(p–1), where all sub-periods of length p are multiples of each other. In particular, if p divides at least one telephone number, it divides infinitely many of them, whose positions are periodic with period p.

All primes divide at least one Fibonacci number (a sequence of numbers with an even simpler recurrence) but that is not true for the telephone numbers. For instance, the telephone numbers mod 3 form the infinite repeating sequence 1,1,2,1,1,2,... with no zeros. So how many of the prime numbers are in the new sequence? A heuristic estimate suggests that the telephone primes should form a 1–1/e fraction of all primes (around 63.21%): p is a telephone prime when there is a zero in the first p terms of the recurrence sequence mod p, and if we use random numbers instead of the actual recurrence then the probability of not getting a zero is approximately 1/e. With this estimate in mind, I tried some computational experiments and found that among the first 10000 primes, 6295 of them (approximately 63%) are in the sequence. Pretty accurate, I think! But I have no idea how to approach a rigorous proof that this estimate should be correct.

Incidentally, while looking up background material for this I ran into a paper by Rote in 1992 that observes a relationship between the telephone number and another sequence, A086828. A086828 counts the number of states in a dynamic programming algorithm for the traveling salesman problem on graphs of bandwidth k, for a parameter k. So its calculation, in the mid-1980s, can be seen as an early example of the parameterized analysis of algorithms. It has the same recurrence relation as the telephone numbers, but with different initial conditions, so we can consider using this sequence instead of the telephone numbers. But the same analysis above showing that all subperiods of length p are similar applies equally well to this sequence, showing that after an initial transient of length p, all subperiods are either identically zero or similar to the corresponding subperiods of the telephone numbers. So if we ask which primes divide at least one member of A086828, we get almost the same answer, except possibly for some additional primes that either divide one of the first p numbers of A086828 (and then no other members of A086828 later in the sequence) or that divide all but finitely many members of A086828.
 
 
 
0xDE
11 November 2015 @ 12:37 am
A reptile is a creature, but a rep-tile is a shape that can tile a larger copy of the same shape. If you use that larger copy to tile still-larger copies, and so on, you get a tiling of the plane. It's often an aperiodic tiling, but not always: for instance, the square and the equilateral tiling are rep-tiles but generate periodic tilings when repped.

Another of the properties of the square and the equilateral triangle is that they are rep-tiles in many different way. Any square number of these tiles can be put together to make a larger copy. A rep-tile is said to be rep-k if it uses k tiles to tile its larger self; these shapes are rep-k for all square k. For tiles whose side lengths are all rational multiples of each other, that's the most versatile a rep-tile can be, because the side length of the larger copy is the square root of k. Let's say that a rep-tile is a pan-rep-tile if it has this same property, of being rep-k for all square k. Are there other pan-rep-tiles?

Read more...Collapse )
Tags:
 
 
 
0xDE
18 October 2015 @ 10:01 pm
Two years ago, and again this year, Irvine hosted the Solar Decathlon, a contest in which groups of university students design and build a small, inexpensive, and self-sufficient solar house and get judged on ten categories for how good their house is. The houses (and various related vendor exhibits) were on show to the public at a public park in Irvine, with students from each team on hand to explain their designs. So yesterday I went to see them, and took a few photos.



Unfortunately I didn't keep any shots from my favorite of the houses, an effort by Clemson involving a modular open-source design made out of aluminum composite panels, with amazingly lightweight but strong and attractive snap-together wooden furniture. It was also the only one to pack three bedrooms into the 1000 square foot limit for the enclosed part of the house.

Instead, here are some of the other houses, with annotations.