**( Read more...Collapse )**

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

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

- A great long-form new year's resolution to slim down your website (MF; G+)
- A guide to scholarly literature on online harassment and responses to it (G+)
- The free modular lattice and its resemblance to the free distributive lattice (G+)
- Escher's
*Stars*(G+) - Nerode prize in multivariate algorithmics, call for nominations (G+)
- Cutting pizza into congruent pieces that don't all meet at the center (arXiv; G+)
- Clear video explanation of the halting problem (G+)
- Challenge: draw these exploded polytopes automatically as nicely as Vi Hart did by hand (G+)
- Student evaluations better at measuring gender bias than teaching effectiveness (MF; G+)
- Co-authorship helps male but not female academics get ahead (G+)
- Part of a series of nice visualizations of Möbius transformations (G+)
- Gerrymandering explained and some computational experiments in using k-medians to avoid it (G+)
- The most-edited Wikipedia pages over the last 15 years (G+)

**( Read more...Collapse )**

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

- Why Wikipedia at 15 is a beautiful exercise in scholarly excellence (G+)
- Graph Drawing 2015 proceedings open access through Jan.18 (follow link from conference page; G+)
- How circle packings bring together some important ideas in geometry, topology, and analysis (G+)
- Many women in STEM fields expect to quit within five years, survey finds (G+)
- The MathJax project moves away from thinking of itself as a steppingstone to MathML (G+)
- Continued issues with peer review at MDPI (G+)
- Two ears theorem (G+)
- Using dot patterns to visualize Euclidean transformations (G+)
- Academic plagiarism leads to criminal charges in South Korea (G+)
- Evelyn Lamb compares Piper Harron's and Shinichi Mochizuki's approaches to telling the world about their mathematics (G+)
- Binary logarithm, newly listed as a Wikipedia Good Article (G+)
- Mathematical artwork visualizing conjugacy classes of subgroups of the icosahedral group, with new years wishes from the AMS (G+)
- Secret sharing, and an attempt to make more sense out of a minor technical subplot of
*Star Wars*(G+)

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

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 K

_{6,10}(shown above), K

_{5,16}, and K

_{7,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...

- Ramsey theory in the dining room (G+)
- Why the history of maths is also the history of art (G+)
- The merger of a bubble and a soap film, from the gallery of fluid motion (G+)
- Kepler Orrery IV, a video simulation showing the scales and temperatures of the extrasolar planetary systems discovered so far (G+)
- The Chung–Graham universal graphs for trees (G+)
- A video walk through fluffy clouds of red string and suspended keys (G+)
- Undercover Greenpeace activists buy off corrupt academics in a climate science sting (G+)
- An alphabet of heptagons: Seven-sided coins (via MF; G+)
- The big mid-1980s drop in women in CS (G+)
- Osgood curves, Jordan curves that themselves have nonzero area (G+)
- Escher museum displayed fakes without telling the punters (G+)
- Graph isomorphism in quasipolynomial time (G+)
- WaPo gives its blessing to singular they (G+)

**( Read more...Collapse )**

*s*just scale by

*s*/2. Similarly, the regular octahedron can be give coordinates that are all the possible permutations of

*φ*, ±1/

*φ*),

*φ*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

*φ*).

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

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

- This year's AMS fellows including Alon, Moore, Pach, Propp, Shub, and Sipser (G+)
- A computer science conference decides to replace its peer review process with online discussions on one of the more wretched hives of misogyny and racism on the net. What could possibly go wrong? (G+)
- Segerman and Nelson visualize hyperbolic honeycombs (G+)
- Riemann hypothesis still not proved (G+)
- Meet the new Google+. Simpler, faster, better, uglier. (G+ only, no link)
- Pirates who hijack the web sites of scientific journals and then divert article submission/publication fees to themselves (G+)
- Interview with Ken Ribet about how he uses the open-source Sage mathematics system (G+)
- Virasena's concept of ardhacheda, said to be an ancient discovery of binary logarithms. But is it really, or is it instead the 2-adic order? (G+)
- Kansas made even flatter and how to define the flatness of a region (G+)
- The history of the Willamette River made visible from the height of the land it once eroded (G+)
- The end of the internet dream? Or, making the internet "a lot more like TV and a lot less like a global conversation". (G+)
- How does a light-field camera work? (G+)
- MathOverflow question re convergence of the 0-1 law for first-order properties of random graphs (G+)

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.

- Reuleaux triangle, now a Wikipedia "good article" (G+)
- Triangle centers from curve shortening (MathOverflow question still missing a complete solution, but a lot of interesting partial results and discussion; G+)
- Rumors of Babai's graph isomorphism result (G+)
- Balancing understandability and pedantry in popular scitech writing (G+)
- A dubious similarity network of novelists, displaying the phenomenon that nearest-neghbor links are not bidirectional (G+)
- Southern California Theory Day, now past (G+)
- Advice from Valerie Barr on being a good feminist ally (G+)
- Reductio ad absurdum of "show your thinking" style math problems (G+)
- Petition to the EU to protest using gold-model open access as an excuse to redirect funding from researchers to publiishers (G+)
- Unification of random-walk and interior-point convex optimization (G+)
- Mathematical street art (G+)
- Can planets have corkscrew orbits? Greg Egan takes down an incautious 3-body analysis (G+)
- More women in science doesn't mean less sexism: the example of Argentinian astronomy (G+)
- The planted clique problem, part of a growing trend of interest in quasipolynomial time algorithmics (G+)

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

- How big publishers are likely to co-opt the open access movement (G+)
- Famous puzzle becomes amusing short story (G+)
- Test how not-ready-for-prime-time your browser's MathML implementation is (G+)
- It's hard to convince men of gender bias in STEM (G+)
- Daniel Widrig's geometric sculpture (G+)
- Maria Chudnovsky's search for a combinatorial perfect graph coloring algorithm (G+)
- Thank you LaTeX stack exchange for having useful answers to everyday questions, this time about a bad interaction between hyperref, natbib, and dois in bibtex data (G+)
- Another article about Neil Sloane and the OEIS (G+)
- Wikipedia cites open-access journals more frequently than closed-access ones (G+)
- GF(2)-polynomial multiplication instructions lead to a fast XOR-universal hash function (G+)
- Three times the House Science Committee abused its subpoena power to hassle scientists it disagreed with (G+)
- Simple 4-polytopes without good separators (G+)
- Hollow heaps, a supposedly-simpler replacement for Fibonacci heaps (G+)
- SWAT (the Scandinavian Symposium and Workshops on Algorithm Theory) goes open-access with LIPIcs (G+)
- Polyhedral approximations of gyroids and the Laves graph (G+)

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.

- Reversible cellular automaton, newly listed as a Wikipedia "Good Article" (G+)
- André Schulz's report from GD 2015, all the GD presentation slides, and Pat Morin's contest-winning freshman research project (G+)
- Lior Pachter's unsolved problems supplementing the Common Core (MF; G+)
- Dune trails on Mars (G+)
- Global coalition tells Facebook to kill its Real Names policy (G+)
- SODA formatting fixes (G+)
- Nature on Mochizuki's baffling ABC proof (Via; G+)
- The 120-cell and its decomposition into 12 rings of 10 dodecahedra (G+)
- How not to be ad-tracked by your Verizon cell-phone (G+)
- The collaborative and social nature of mathematics (G+)
- The WAVL tree data structure (G+)
- Augmented reality meets food psychology (G+)
- Serial sexual harasser resigns Berkeley professorship (G+)
- The importance of recreational mathematics (G+)