Some mathematical interests

Numbers.1
Here's a the outline of a little talk I gave a while back about some relatives of the Fibonacci numbers. To make a long story short, there are some pretty curious properties associated with these peculiar numbers (all except for 23, 139, 211, 422, 461, and 761 of course!).

In the mid 1970's I contemplated the sequence of powers of 2 and 3, combined together and sorted:

(2,3,4,8,9,16,27,32,64,81,128,243,256,512,729,1024,...). I wondered whether the ordering of the sequence by bases (2 or 3) as follows: (2,3,2,2,3,2,3,2,2,3,2,3,2,2,3,2,2,3,2,...) would ever repeat or not. I asked a couple of mathematician friends about it and none seemed to know. I forgot about the question for a decade or so, but while at the University of Alaska I asked Ron Gatterdam about it. He was certain the sequence was irrational (non-repeating) and was confident he could prove it. The next day we both produced proofs that it was irrational. I then forgot about the problem for another 20 years.

Recently I started thinking about it again, and discovered some interesting properties and conjectures about these Ordered Exponential Sequences, and have been working up some of what I know. In the meantime, a colleague informed me about the Online Encyclopedia of Integer Sequences. The sequence has apparently been looked at as early as 1931. It even has a sequence number A006899.

Here's a little calculator for dealing with some properties of these Ordered Exponential Sequences.

Tiling
I've been looking into something I call the "tile number" of a graph. Informally, the tile number is the smallest number of rigid polygons, out of which a given planar graph can be constructed. That such a number exists is clear from the well-known result that one can draw any planar graph using straight lines for edges. Some of the non-deterministic tilings displayed here can be used to show that many different graphs of the same size (nodes and lines) have tile number equal to one. A companion inquiry concerns the construction of graphs out of fixed components. This particular piece of JavaScript allows you to construct such graph tilings quasi-randomly (here are a couple of related things: weaving and wallpaper. One question I've played with is this: what is the smallest tile number of a class of planar graphs such that the 3-coloration of those graphs is NP-complete? If the number is small, then we can randomly generate all interesting problems pretty easily.

Four-regular planar graphs
Some four-regular graphs can be traversed by a single "forward walk". For a given planar embedding of the graph, we begin at any node n and construct a walk as follows: choose p, any neighbor of n, as the next node. Consider the lines entering p: orient each line into p in counterclockwise order, beginning with the line from n to p. Label these lines "back," "right," "forward," and "left." A forward walk consists of a walk which always chooses the forward line. A tangle is a planar four-regular graph in which a single forward walk visits every line. In my dissertation I showed that three-coloration of tangles was NP-complete. Tangles have numerous other interesting properties: the dual is bipartite; each node appears in both odd and even positions in the complete forward walk; the tangle number of a three-connected graph is a graph-invariant, etc.

Approximating space with graphs
Perhaps the continuum is an illusion: a cognitive simplification of an ultimately discrete universe. In a paper in Discrete Mathematics I investigate the question of the smallest graph in which a given metric space can be modeled. Just as one might inquire about the space of smallest dimension to model a given set of proximities between objects, one might prefer the parsimony of assuming merely that space is a graph. I suspect that physics gets interesting in graphs, since there is no requirement that space be uniformly shaped.

Navigating in graphs
Are certain graphs intrinsically more navigable than others? That's what I'm looking into most recently. In addition to looking at such things as graph domination (analogs of beacons), and metric properties, I've also been looking at "field effects" like gravity and magnetism in graphs. If a graph is gravitationally flavorable, can we find our way around in it better. To get started, I've built Grapher which allows the building and editing of graphs. Try it out. A recent paper on the topic can be found here. 

Generating random objects
Generating a random number is fairly easy (though people still work on the problems of how best to do it with certain constraints on, for example, security.) Suppose we wish to generate a random graph, or a random polygon, or a collection of N colors that are maximally distinguishable by humans. How to proceed with these more complex objects? If you have a browser that can open SVG files, take a look at the approaches discussed here: drawing random polygons with JavaScript and SVG.

Calculating distances between objects
Distances between two points are easy to find. Suppose we wish to find distances or similarities between two more complex things like two strings, or two graphs. How might we do it? Here's a recent paper on the topic.

Non Platonic dice
While the Platonic solids all make for nice, and seemingly fair, dice, certain non Platonic polyhedra are just as fair. For any n, we may easily construct a 2n sided fair die by gluing together the bases of two pyramids. Each pyramid consists of one regular n-gon as its base and n triangular sides. In two dimensions the length of a side does not determine the probability of its occurrence: just as important is the position of the center of gravity relative to that side. Also, some dice allow probabilities of some sides to change depending on the distance they are dropped.

Non-associative groupoids
Just about all of published mathematics discusses associative structures. But not all things are associative. A black birdhouse is not equal to a blackbird house, for example. So, concatenation of English morphemes is not associative under English semantics. Other than its cognitive convenience, what makes a(bc)=(ab)c any better than say a(bc)=(ca)b? In a census of small groupoids, I discovered that associativity is neither the most nor least ubiquitous of principles. Its ability to help prove theorems (in conjunction with, say, a left identity or a right inverse) is also neither greatest nor least among axiomets of similar orthographic complexity. Look here to explore some non-associative groupoids in Java.

Here are some papers I've prepared.

[Spring 2006  (updated Fall 2012)- David Dailey]