• Linkage

    • You can find plenty of online stories celebrating the release into the public domain of Winnie the Pooh (text, not film), Hemingway’s The Sun Also Rises, etc. But the situation for Ludwig Wittgenstein is more complicated. All his own writing is now public domain in life+70 countries, but the work of later editors might not be. Michele Lavazza explains (\(\mathbb{M}\), via).
  • New Year's Eve linkage

  • Raytracing diamonds

    This comes from a question posed to me and others in 2019 by Stefan Langerman, a computational geometer who also happens to be a diamond dealer. The classic brilliant cut shape of diamonds has a flat “table” face on the top (visible) side of the gem, and many other smaller facets on the sides (“crown”) and back (“pavilion”), with angles chosen so that most of the light that enters through the table is reflected back out through the table, making the diamond look bright. Can we simulate this reflection process efficiently, without having to trace all the reflections of all (or a sufficiently dense sample of all) possible light rays?

  • Recursive bijective numbering

    Ordinary radix systems for representing numbers, like binary or decimal, use fixed finite sets of digits. The same is true for bijective numeration, used for columns of spreadsheets. In bijective numbering, every string of digits represents a unique number, shorter strings represent smaller numbers, and strings of equal length have the usual order. In spreadsheets, the digits are letters A–Z, one-letter strings represent numbers \(1\) through \(26\), two-letter strings represent \(27\) through \(26+26^2=702\), etc. Instead, mixed radix systems like the factorial number system have position-varying digit sets. In factorial numbering, the \(i\)th digit can range from \(0\) to \(i-1\), with place value \((i-1)!\). The value of a digit string is the sum of digits times place values. One could combine these ideas and get a bijective factorial number system, in which strings of at most \(i\) digits can represent numbers up to the sum of the first \(i\) factorials. But in all of these mixed radix systems, the digits are not drawn from a finite set. Maybe we need another numbering system just to describe each digit of a mixed-radix number? This leads to the idea of a recursive numbering system, where the digits of a mixed-radix system are themselves numbers in the same system.

  • Linkage with a couple of photos

  • Linkage

  • Linkage

  • Random independent sets in bounded-treewidth graphs

    This week my student Daniel Frishberg posted our new preprint “Rapid mixing of the hardcore Glauber dynamics and other Markov chains in bounded-treewidth graphs”, arXiv:2111.03898. Despite the somewhat-technical title and content, it’s on an easy-to-explain problem, of generating random combinatorial objects (like independent sets in graphs) using random walks. Start with an undirected graph and an empty subset of its vertices, and then repeatedly choose a random vertex, flipping whether it is in or out of the subset whenever the resulting subset remains independent. How many of these steps does it take until the resulting random distribution on independent sets is nearly uniform?

  • Gilbert tessellations from a cellular automaton

    A Gilbert tessellation is what you get from choosing a random set of points-with-slopes in the plane, growing line segments in both directions with the chosen slope from each chosen point, at constant speed, and stopping the growth when each line segment runs into something else. The slopes can be in uniformly random directions but one standard variant of the Gilbert tessellation uses only horizontal and vertical slopes.

  • Linkage

    • Square-difference-free set (\(\mathbb{M}\)), now a Good Article on Wikipedia. As the name suggests, these are sets of integers no two of which differ by a square. My favorite such set consists of the losing positions in subtract-a-square, where each move removes a square number of coins from a pile of coins, winning by taking the last coin. This general class of sets and the subtract-a-square set have \(o(n)\) elements up to \(n\), but their maximum density remains unknown.

subscribe via RSS