?

Log in

0xDE
31 August 2015 @ 09:33 pm
 
 
 
0xDE
04 August 2015 @ 11:11 pm
If you've been paying any attention to my blog posts and other online activity, you probably know that I'm a huge fan of Wikipedia. I think it's a great way to communicate theoretical research to a wider audience, a great way to practice writing in a setting that encourages writing for readability, and a great place to publish survey-like material. Since I began editing Wikipedia in 2006, I have made over 90000 edits and created over 700 new articles (not counting redirects etc), most of them on mathematical subjects. I've also regularly been using collections of Wikipedia readings as textbooks in some of my classes for which there is no published text that matches the material I want to cover. I've encouraged others to contribute their expertise and will take the opportunity to do so again: Edit Wikipedia! Contribute your knowledge to the broader world!

But if you've read many Wikipedia article on mathematical subjects, you'll know that they can have a few issues. The content may sometimes be amateurish and topics may be missing, but those can be fixed with some effort. (Edit Wikipedia! Contribute your knowledge!) Another, more stubborn issue concerns the formatting of its mathematical equations.

Read more...Collapse )
 
 
 
0xDE
15 May 2015 @ 10:36 pm
 
 
0xDE
07 May 2015 @ 11:15 pm
The Schulze method for determining the results of multiway votes has three parts:

1. Use the ballots to determine the results (winner and margin of victory) of each possible head-to-head contest.
2. Perform an all-pairs widest path computation on a directed complete graph weighted by the margins of victory.
3. Find the candidate with wider outgoing than incoming paths to all other candidates.

The second part can be done in cubic time using the Floyd-Warshall algorithm (the choice in practice) or faster using fast matrix multiplication. And the third part is easy. But what about the first part? Here, some Wikipedia editor wrote in 2011 that the first part, "if implemented in the most straightforward way, takes time proportional to C2 times the number of voters" (where C is the number of candidates). But then last year some other editor tagged this claim as being original research.

This raised some questions for me. Given how straightforward it is, can this really be considered to be original research? Is it possible to find a published source for the time analysis of this step that can be used to untag it? (If you know of one, please tell me or add it to the article.) Is the algorithm with this time bound really "the most straightforward way"? And if this is the time bound you get by doing things straightforwardly, can we get a better time bound by trying to be more clever?

Read more...Collapse )
 
 
 
 
0xDE
15 February 2015 @ 05:32 pm
I don't know what Google+ is doing under the hood (and don't really want to know) but whatever it is seems kind of bloated to me, enough to kill my browser and the responsiveness on my whole machine when I try to open 14 G+ tabs at once. But anyway, here they are:
 
 
 
0xDE
15 November 2014 @ 10:03 pm
 
 
 
0xDE
15 October 2014 @ 01:30 pm
 
 
0xDE
29 June 2014 @ 10:21 pm
One of Wikipedia's less well-known features is its Book: namespace. The things there are called books, and they could be printed on paper and bound into a book if you're one of those rare Wikipedia users who doesn't use a computer to read things, but really they're curated collections of links to Wikipedia articles. I've made two of them before, Book:Graph Algorithms and Book:Fundamental Data Structures, which I have used for the readings in my graduate classes on those topics because I wasn't satisfied with the textbooks on those subjects. This week I put together a third one, Book:Graph Drawing.

It's not complete (what on Wikipedia is?), and the writing quality and depth of coverage are as variable as always, but there are about 100 topics there and I hope that collecting them in this way proves useful. I've listed a few more things that I think should be added but don't yet have their own Wikipedia articles on the talk page, but if you see something else missing then please let me know or, even better, add it.
 
 
0xDE
03 June 2014 @ 10:33 pm
While cleaning up some badly-sourced articles on Wikipedia, I ran across the one on reverse perspective, a strange drawing style in which nearby objects are shown as small and far-away objects are shown as big. Despite the strangeness, it's mathematically consistent: it's what you get when you put objects between the perspective point (your eye in conventional perspective) and the viewing plane (a window through which you're looking at the world). Here's a nice example:



Although it's been used a lot in art (sometimes deliberately, for effect, sometimes naively, and sometimes for reasons lost to history and hotly debated), I don't know of any attempts to use it for visualization. It has some effects that might be useful, notably the ability to see more sides of an object at once than is possible in a conventional view.
 
 
0xDE
21 April 2014 @ 11:33 am
I just added a new article to Wikipedia on indifference graphs (also known as unit interval graphs or proper interval graphs): the graphs formed from sets of points on the real line by connecting every two points whose distance is less than one.



There are many papers on algorithms for going from the graph to a geometric representation in linear time. The following method for the reverse problem, going from the set of points (or equivalently unit intervals) to its graph must be known, possibly in the context of its generalization to higher dimensional unit disk graphs, but I don't know a good reference for it.

Read more...Collapse )

Update, April 22: It appears that the correct reference for this is Bentley, Jon L.; Stanat, Donald F.; Williams, E. Hollins, Jr.
The complexity of finding fixed-radius near neighbors. Information Processing Lett. 6 (1977), no. 6, 209–212.
 
 
0xDE
So yesterday I was working on new Wikipedia articles on riffle shuffle permutations (an awkward name: I would have preferred riffle permutations but I couldn't find enough sources that called them that) and the Gilbert–Shannon–Reeds model of random shuffling. There's been a lot of work on how many riffles you need to do until all permutations are nearly equally likely (by some reasonable measures, the answer is 1.5 log2 n) but it occurred to me to ask a simpler question: how many riffles do you need to do until all permutations have nonzero probability? If you riffle the deck only once, for instance, you can only form a small fraction of the possible permutations: there are roughly 2n different riffles, a much smaller number than n!. And which permutation requires the most riffles to be generated?

Read more...Collapse )
 
 
0xDE
17 May 2013 @ 12:37 am
Today's new Wikipedia articles: Hanner polytopes and Kalai's 3d conjecture.

The 3d conjecture states that a centrally symmetric d-dimensional polytope must have at least 3d faces (of all dimensions including the d-dimensional polytope itself as a face but not including the –1-dimensional empty set). For instance, the cube has 8 vertices, 12 edges, 6 squares, and 1 cube as faces; 8 + 12 + 6 + 1 = 27 = 33.

The Hanner polytopes include the cubes, are closed under Cartesian products and duality, and if the conjecture is true have the fewest possible numbers of faces of all centrally symmetric d-dimensional polytopes. They also have some other interesting properties. In 3d there are only the cube and the octahedron, but in higher dimensions there are a lot more of them.
 
 
0xDE
25 March 2013 @ 02:37 pm
I've been working on a new Wikipedia article on circular layouts in graph drawing, and I wanted to say something in it about Planarity, a puzzle that involves moving the vertices of a graph drawing around, starting from a circular layout, to show that the graph is planar. However, despite the existence of quite a bit of academic work that explicitly states that it's inspired by Planarity, I couldn't find any published source that describes the initial layout of the puzzle.

Several near missesCollapse )

In the absence of good enough sources for the circularity of its layouts, I ended up mentioning Planarity in a see-also link of the circular layout article, rather than actually including it in the main text of the article. It's obvious to anyone who spends any amount of time playing Planarity that its initial layout is circular. But sometimes, being obvious isn't enough: you have to say it.
 
 
0xDE
03 February 2013 @ 08:45 pm
In editing a new Wikipedia article on Rota's basis conjecture, I came across a connection to a different problem in discrete geometry that seems closely related.

When applied to the Euclidean plane (a case for which it is known to be true), Rota's conjecture states the following: suppose you have nine points colored with three colors in such a way that each color forms a non-degenerate triangle. Then the points can be regrouped into three non-degenerate rainbow triangles (triangles with all three colors as vertices). Like so:



A different conjecture of Bárány and Larman can also be applied to points in the plane (where again it is known to be true; the harder part is in higher dimensions). For nine points colored in the same way, it states that the points can be regrouped into three rainbow triangles (this time allowed to be degenerate) whose intersection is nonempty.

So it occurred to me to wonder: suppose you have three non-degenerate triangles of three colors, the same as in Rota's conjecture. Do there always exist three rainbow triangles that are both non-degenerate and intersecting? Or maybe stronger, three rainbow triangles whose intersection is full-dimensional, as it is in the figure? And what about higher dimensions (where in general neither conjecture has been proven)?

ETA Feb. 5: There do not always exist three rainbow triangles with full-dimensional intersection; the figure below is a counterexample. At most two of the triangles can cover any point away from the origin, so if three triangles intersect they can only do so at the origin.