User alejandro erickson - MathOverflow

Monomer-Dimer tatami tilings need better relationships with other math. Summary of results.

2012-07-26T07:11:38Z

A monomer-dimer tiling of a rectangular grid with $r$ rows and $c$ columns satisfies the \emph{tatami} condition if no four tiles meet at any point. (or you can think of it as the removal of a matching from a grid graph that breaks all $4$-cycles).

This simple restriction, brought to my attention by Don Knuth in Vol 4 of TAOCP, became my PhD thesis topic, when my research group and I discovered that it imposes a aesthetically pleasing structure with a nice description, and opened up lots of fun questions.

Here is my favourite example, which has all of the possible "features". First it is shown uncoloured

And here it is coloured

The magenta tiles show the types of features it can have, and here they are on their own:

I'll introduce my question here, and then summarize some more results later. I want to find more and better ties between tatami tilings and other less esoteric math problems. If you think of a paper or subject I might want to look into, don't hesitate to answer.

In our first paper, we proved the above structure and showed that:

A tiling is described by the tiles on its boundary, and hence has a description that is linear in the dimensions of the grid.
The maximum number of monomers is at most max(r+1,c+1), and this is achievable.
We found an algorithm for finding the rational generating polynomial of the numbers of tilings of height r (which I think can also be calculated with the transfer matrix method).

We posed a couple of complexity questions (which I am working on), for example, is it NP-hard to reconstruct a tatami tiling given its row and column projections?

Or tile a given orthogonal region with no monomers?

Next we focused on enumerating tilings of the $n\times n$ grid, and found a partition of $n\times n$ tiles with the maximum number of monomers into $n$ parts of size $2^{n-1}$. We also counted the number tilings with $k$ monomers, and this curious consequence:

The number of $n \times n$ tatami tilings is equal to the sum of the squares of all parts in all compositions of $n$. That is, $2^{n-1}(3n-4)+2$.

We also found an algorithm to generate the ones with $n$ monomers, and a Gray code of sorts.

Nice numbers, and a cute problem, but another paper that is self contained with elementary (albeit, somewhat complicated) reasoning.

Our third paper in this story (in preparation), looks at the generating polynomial for $n\times n$ tilings with $n$ monomers whose coefficients are the number of tilings with exactly $v$ vertical dimers (or $h$ horizontal dimers). It turns out this generating polynomials is a product of cyclotomic polynomials, and a somewhat mysterious and seemingly irreducible polynomial, who's complex roots look like this:

We've found a bunch of neat stuff about it, for example the evaluation of this polynomial at $-1$ is $\binom{2n}{n}$, for $2(n+1)\times 2(n+1)$ tilings, and we found our generating polynomial gives an algorithm to generate the tilings in constant amortized time. Here is some output of the implementation:

That's the most of the published (and almost published) story. There is a loose connection with other monomer-dimer problems, and things I can look into, like Aztec tatami tilings, but I'm looking for direct applications of other results to these, or vice versa, especially with this last paper in preparation. I'm not asking you to do research for me, but just your thoughts as they are now, so I can go learn new stuff.

Feel free to comment about what you think is interesting, or not, about tatami tilings too!

How to efficiently vacuum the house

2011-12-11T20:04:33Z

Let $P$ be a polygon (perhaps with no acute angles inside) and let $L$ be a line segment. The segment may move through the area inside $P$ in straight lines, orthogonal to $L$, or it may pivot on any point on $L$ (while remaining entirely within $P$).

Let $S$ be a legal sequence of pivots and straight motions for $L$ in $P$, and say $S$ covers $P$ if applying the motions $S$ to $L$, passes over every part of the area in $P$. The covered area of $S$ is the cumulative area passed over by $L$.

How can we compute the minimum number of pivots over all covering sequences $S$?
How can we compute the minimum covered area over all covering sequences $S$?

Better formulations of the problem are welcome.

For a rectangular polygon, $h\times w$ and a line segment of length $l$, with $h < w$, and $l < h$. So in the best sequence I can think of the number of pivotes is $\lceil h/l \rceil$, and the second question is just a sum of areas of semicircles of radius $l$, plus the rectangular overlap from the last strip.

___________________________
| l-->                    | 1 pivot at each end
|                   <--l  |    
| l-->                    |
|                   <--l  | 2 pivots if h is not integer multiple of l
---------------------------

SWAT vs Rioters (cops vs robbers variant)

2011-11-21T16:33:05Z

I thought of this while at the Combinatorial Potlatch at Seattle University, where Peter Winkler gave an excellent talk on Cops vs Drunken Robbers. I'll just open it up to the floor. The problem formulation might need some help too.

Let $G=(V,E)$ be a loopless graph. Let $w$ be a non-negative integer (and $\infty$) edge weighting, and let $s,r$ be non-negative (finite) integer vertex weightings. Let $S$, $R$ be real functions.

At each ply of the SWAT vs Rioters game we first remove the rioters, setting $r_v=0$, at any vertex $v$ for which the SWAT, $s_v$, overpowers them. The SWAT overpowers the Rioters (and perhaps arrests them all) whenever $S(s_v) \ge R(r_v)$. Then, either the Rioters or the SWAT, according to whose turn it is, must make a move by displacing at least one available unit from at least one vertex, along an edge, to at least one of its neighbours. The weight of the edge defines the maximum number of units that may be displaced through it, and units received from other neighbours in that ply are not "available" until the next turn.

Precisely defined, the above says, for each $v$, set $r_v=0$ if and only if $S(s_v) \ge R(r_v)$, and then, if it is the SWAT's turn, create a temporary variable $s_v'$ for each vertex $v$, and set $s_v' \leftarrow 0$. For each pair of vertices $u,v$, with an arc $uv$, and some number of units $k$, with $0\le k \le \min(w_{uv},s_u)$, set $s_v' \leftarrow s_v'+k$ and $s_u\leftarrow s_u-k$. Finally, for each vertex $v$, set $s_v = s_v+s_v'$. Do the same with $r$ if it is the Rioters' turn.

I'm only vaguely familiar with the usual Cop vs Robbers problems, but I suppose we would want to characterize conditions which are SWAT win, and find the number of moves it takes for SWAT to win, as well as an algorithm.

Take for example, all edge weights equal to 2, S(k)=k^2, R(k)=k. Then perhaps 1 SWAT and 3 Rioters at each vertex. Does anyone care to propose interesting initial conditions?

Cops vs Robbers is the case where edge weights are 1, S(k) = k, R(k) = k, 1 SWAT and 1 Rioter somewhere in the graph.

proportion of $n$ symbol sequences whose $l^p$ norm is equal to $|[n]|_p$

2011-06-23T07:00:49Z

and each symbol is at most $n$...

Any ideas about where to find previous work?

I can find the answers for small $n$ using a brute force search, but I'd like to know more generally.

For example, $1^3+2^3+3^3+4^3+5^3+6^3+7^3 = 784$

Of the sequences of length $n$ using the symbols in ${1,\ldots, n}$, 5460 of them have this same sum of cubes. $5460-7!$ of them are not permutations of $[n]$. The same thing happens with the sum of fourth powers (but not when $p=5$).

For which $p$ is the norm of a permutation of $[n]$ distinct from the norm of these other sequences?
Otherwise, what is the proportion of "false positives"?
Is there a $p_0$ for which $p>p_0$ always gives this distinction? What is $p_0$?

formulate edge length problem as convex optimization problem

2010-10-20T00:01:38Z

I want to us convex optimization to describe a problem in computational geometry.

Let $E = (E_1, E_2,\ldots , E_m) $ be a sequence of line segments in the plane, where $E_1$ and $E_m$ may be points and the rest are non-degenerate segments. A critical path on $E$ is a selection of points $(p_1,p_2,\cdots ,p_m)$ with $p_i\in E_i$ with edges $e_i=(p_i,p_{i+1})$ such that (1) all $e_i$ has the same length $l$ and (2) no other selection of points results in a path with edges that are not longer than $l$ and some that are shorter.

Find the critical path using convex optimization (if it exists). Can you use the convex optimization problem to show that the solution is unique (in certain cases)? Can you find exact locations for the points $p_i$ in polynomial time?

I have the impression that this is an elementary convex optimization problem, where points are restricted to segments, edge lengths must be minimized, and then check that the lengths are all the same (for existence).

I have a formulation of the above as what appears to be a second-order cone problem (as far as I understand).

The segment $E_i$ can be described as $E_i = {(x,a_ix+b_i): x_{l,i} \le x \le x_{r,i}}$ and the length of the edge $e_i$ is the distance between points $p_i$ and $p_{i+1}$. Here $p_i = (x_i, a_ix_i+b_i)$ for some choice of $x_i$ such that $x_{l,i} \le x_i \le x_{r,i}$, so $|e_i|_2^2 = (x_i-x_{i+1})^2 + (a_ix_i+b_i - a_{i+1}x_{i+1}-b_{i+1})^2 $

We can use the following second-order cone problem (or is that what it is?) to minimize the maximum length edge among all paths with points on the sequence $E$,

$\min z$

such that

$|e_i|_2 \le z, 1\le i \le m-1$

$x_{l,i} \le x \le x_{r,k}, 1 \le i \le m $

If there is a critical path on $E$, this problem has a unique solution. Otherwise it does not have a unique solution. But how do we prove this?

What we would like is a problem which has a provably unique solution if and only if there is a critical path and a method of finding the exact solution.

Please understand that this problem was misinterpreted in the comments below, that it is a research problem, and any useful answers posted here will be properly cited.

Answer by Alejandro Erickson for Tools for collaborative paper-writing

2010-04-16T06:21:48Z

On most papers it is far easier to coordinate your efforts by email than it is to learn svn or whatever. But I think the best is yet to come and it will be part of the class of tools being pioneered by scribtex.com verbosus.com and docs.latexlab.org. Take any of these and add -ftp or similarly convenient uploading, -some kind of guarantee of relative security/privacy, -inline preview like auctex and finally (fingers crossed), -compile with server or local TeX installations -offline mode. Those things combined will be very compelling with the added bonus of not having to install anything.

Comment by Alejandro Erickson

2011-12-11T20:39:06Z

Oddly enough, I was just eating breakfast. My girlfriend asked me why I looked lost in thought, and this is what I said to her.

Comment by Alejandro Erickson

2011-12-11T20:37:28Z

Neat. I didn't think this problem had received so much attention.

Comment by Alejandro Erickson

2011-06-23T15:12:15Z

needless to say, I can cut some of the computation by considering multisets of size $n$ on $n$ symbols.

Comment by Alejandro Erickson

2010-12-13T19:46:39Z

thanks, will delete when the option becomes available (2 days, it says). reposting the question on my blog

Comment by Alejandro Erickson

2010-10-21T21:48:37Z

ah yes, that is useful because we don't have to check uniqueness of the first solution. Suppose the result of the second program confirms that there is a critical path (by showing that the minimum sum is (m-1)z where m-1 is the number of edges, then I would like to show that the solutions to both programs (they should be the same) are unique. Are there some uniqueness results for SOCPs that would help me here? You implicitly agree that the program I wrote down is an SOCP then?

Comment by Alejandro Erickson

2010-10-20T21:54:31Z

oh... heh. I may have blackboxed too much of the problem. Our situation is that we have solved the problem using an algorithm that is a bit hard to read. While this has been accepted at the isaac conference (search for me on arxiv to find it), I would like to develop something more concise for the journal version. I have the impression that this might be a textbook problem in convex optimization (say, a second-order cone problem?), but the literature (Boyd and Vandenberghe) is a bit thick for me. I also don't think the question is that easy, as no one has even hinted at an answer.

Comment by Alejandro Erickson

2010-10-20T16:48:02Z

I don't understand why i would use those others when i have posted my question here. They appear to be newer versions of almost the same thing.

Comment by Alejandro Erickson

2010-10-20T16:44:37Z

@ricky ha, maybe i should write one then. I will try those others, not sure what they are.