I noticed that there was a higher-than-usual density of arxiv preprints among the web pages I'd been bookmarking lately, so I thought maybe I'd share. The first one, especially, is very timely:

From the "Brazuca" ball to Octahedral Fullerenes: Their Construction and Classification

Yuan-Jia Fan, Bih-Yaw Jin, arXiv:1406.7058, via. The classical pentagon and hexagon soccer ball pattern (introduced for the 1970 World Cup) later became even more famous as the structure of the buckminsterfullerene Carbon-60 molecule, from which the fullerene graphs (planar graphs in which all faces are pentagons or hexagons) took their name. Another soccer ball pattern, used in the 2006 world cup, is topologically a truncated octahedron but with distorted face shapes that reduce its symmetry to tetrahedral; there also exist fullerenes with tetrahedral symmetry. And there's a new soccer ball pattern for the Brazil world cup, with the topology of the cube; the "via" article says that it has octahedral symmetry but I'm not convinced, because it doesn't seem to have the reflection symmetries that octahedra should have. Nevertheless Fan and Jin asked: are there fullerenes with octahedral symmetry? The positive answer comes from a nice construction involving cutting equilateral triangles out of the hexagonal tiling and then gluing them together to make a finite polyhedron.

The Shortest Path to Happiness: Recommending Beautiful, Quiet, and Happy Routes in the City

Daniele Quercia, Rossano Schifanella, Luca Maria Aiello, arXiv:1407.1031, via. Suppose you want an online map service to give you a walking tour of a city. You probably wouldn't want the shortest path from one part to another, but rather the nicest path. Changing how you weight the edges of the underlying graph to prioritize them differently is not so difficult (and I wrote a paper long ago on how you might adjust these weights to fit different users' preferences) but the harder part is gathering the data to measure what it means for a route to be nice. These authors approach the problem with online photo databases, in one case crowdsourcing the problem of quantifying niceness and in another attempting to use the image tags to determine it automatically. The analysis of how well it worked seemed very anecdotal and handwavy to me but maybe that's the nature of the subject.

The Convex Configurations of "Sei Shonagon Chie no Ita" and Other Dissection Puzzles

Eli Fox-Epstein, Ryuhei Uehara, arXiv:1407.1923. Given a puzzle like the tangram (a square subdivided into seven convex pieces) how many ways are there of rearranging it into convex shapes? I asked a similar question (with different shapes) in one of my old talks but the tangram question (and its answer) have been known for much longer, since at least 1942. This paper solves the same question for some more complex puzzles of a similar type. Like the 1942 tangram paper, the new preprint uses the observation that there is a smaller tile into which the puzzle pieces can all be subdivided, such that any solution is a subset of a regular tesselation of the plane by this tile. I don't know of a general algorithm for solving this kind of problem efficiently; perhaps there's something interesting to be done in that direction.

Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts

Radu Curticapean, Dániel Marx, arXiv:1407.2929. Ok, unlike the other ones this is not recreational mathematics. But it still interested me. The problem concerns the complexity of counting copies of subgraphs in larger graphs, something that seems to be quite topical lately. If the subgraph has a fixed number \( k \) of vertices and the larger graph has \( n \) vertices, then there's an obvious \( O(n^k) \) algorithm: just try all \( k \)-tuples of vertices, and it's not hard to extend this to the case where the subgraph has a subset of \( k \) vertices that together cover all of its edges. As Curticapean and Marx show, these are the only cases in which one gets a polynomial time algorithm (assuming standard complexity-theoretic conjectures): counting subgraphs from a given class does not have a fixed-parameter tractable algorithm unless the vertex cover number is bounded.




Comments:

None:
2014-07-14T21:34:37Z

Dear David,

I have not looked at this paper but I assuming that by a fullerene is meant a graph which is planar and 3-connected, all vertices 3-valent and 12 pentagons and some number h of hexagons with h not equal to one. A theorem of Grunbaum and Motzkin showed constructions of fullerene graphs with h hexagons h not 1, though many others have constructions as well. An Atlas of Fullerenes by Fowler and Manolopoulos states there are 28 different groups, which if I understand them properly, can be the automorphism groups of a fullerene graph. Non-isomorphic groups can of course have the same order. By Steinitz's Theorem one can realize the graph of a fullerene by a convex 3-dimensional polytope, and by a theorem of Peter Mani, if H is the (full) automorphism group of a fullerene graph G, then G can be realized by a convex 3-dimensional polytope who isometry group is H. The usual definition of the octahedral group is that it has order 48, and this is not one of the orders in the Fowler and Manolopoulos list. The rotation group of the octahedron has 24 symmetries. Perhaps what is being done relates to fullerenes with this group as its automorphism group?

Joe Malkevitch
https://york.cuny.edu/~malk

11011110:
2014-07-14T21:49:45Z

When I saw your name commenting I thought it would be re the convex puzzle rearrangements...I remember you once pointed me to some existing literature on the question of which convex shapes can be formed by triangles and squares.

Anyway, they seem to be using a looser definition which is again planar 3-connected 3-regular and girth five but allows faces of higher order such as (in this case) octagons as well as the usual pentagons and hexagons. I think they're coming at this from the chemical point of view without a lot of knowledge of what's already been done on the graph theory side of this problem.

None:
2014-07-15T16:22:45Z

There a very nice theorem of Grunbaum related to these matters, but only combinatorial issues are addressed. Grunbaum shows that when there are no triangles or 4-gons in the planar 3-connected graphs, graphs involving 5-gons and "big faces" (7-gons or more) and 3-valent, then for all solutions of the usual Euler relation for 3-valent graphs, all graphs can be constructed with the number of hexagons eight or more.

B. Grünbaum
Some analogues of Eberhard's theorem on convex polytopes
Israel J. Math., 6 (1968), pp. 398–411

I agree with your remark about combinatial/geometrical questions inspired by chemistry. A remarkable book here is: Michel Deza and Mathieu Dutour Sikiric, Geometry of Chemical Graphs Polycycles and Two-Faced Maps. Cambridge U. Press, 2008. This book collects the results in many of the papers of Deza and Sikric and has led to additional work.

Joseph Malkevitch
https:york.cuny.edu/~malk