User alejandro erickson - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T16:53:09Z http://mathoverflow.net/feeds/user/5407 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/103165/monomer-dimer-tatami-tilings-need-better-relationships-with-other-math-summary Monomer-Dimer tatami tilings need better relationships with other math. Summary of results. Alejandro Erickson 2012-07-26T07:11:38Z 2012-07-31T17:07:11Z <p>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).</p> <p>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. </p> <p>Here is my favourite example, which has all of the possible "features". First it is shown uncoloured</p> <p><img src="http://geoburst.ca/eggs/tatami/bare_tatami_example.png" alt="A tatami tiling showing all possible features, up to rotation"></p> <p>And here it is coloured</p> <p><img src="http://geoburst.ca/eggs/tatami/coloured_tatami_example.png" alt="A tatami tiling showing all possible features, up to rotation"></p> <p>The magenta tiles show the types of features it can have, and here they are on their own:</p> <p><img src="http://geoburst.ca/eggs/tatami/loner_vee.png" alt="Loner and Vee features"></p> <p><img src="http://geoburst.ca/eggs/tatami/bidimer_vortex.png" alt="Bidimer and vortex features"></p> <p>I'll introduce my question here, and then summarize some more results later. <strong>I want to find more and better ties between tatami tilings and other less esoteric math problems.</strong> If you think of a paper or subject I might want to look into, don't hesitate to answer.</p> <p>In our <a href="http://www.combinatorics.org/Volume_18/PDF/v18i1p109.pdf" rel="nofollow">first paper</a>, we proved the above structure and showed that:</p> <ol> <li>A tiling is described by the tiles on its boundary, and hence has a description that is linear in the dimensions of the grid.</li> <li>The maximum number of monomers is at most max(r+1,c+1), and this is achievable.</li> <li>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).</li> </ol> <p>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?</p> <p><img src="http://geoburst.ca/eggs/tatami/tomoku.png" alt="Tomoku game. Is it NP-hard?"></p> <p>Or tile a given orthogonal region with no monomers?</p> <p><img src="http://geoburst.ca/eggs/tatami/strider.png" alt="Water striders. Is it NP-hard?"></p> <p>Next we focused on <a href="http://www.sciencedirect.com/science/article/pii/S1570866712000561" rel="nofollow">enumerating tilings of the $n\times n$ grid</a>, 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:</p> <blockquote> <p>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$.</p> </blockquote> <p>We also found an algorithm to generate the ones with $n$ monomers, and a Gray code of sorts.</p> <p>Nice numbers, and a cute problem, but another paper that is self contained with elementary (albeit, somewhat complicated) reasoning.</p> <p>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: <img src="http://geoburst.ca/eggs/tatami/pn_roots.png" alt="Complex roots of mysterious polynomial"></p> <p>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:</p> <p><img src="http://geoburst.ca/eggs/tatami/genvh8_7.png" alt="Output of cat algorithm generating tilings. This is genVH(8,7), for $8\times 8$ tilings with $8$ monomers and $7$ vertical dimers."></p> <p>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 <strong>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.</strong> </p> <p>Feel free to comment about what you think is interesting, or not, about tatami tilings too!</p> http://mathoverflow.net/questions/83200/how-to-efficiently-vacuum-the-house How to efficiently vacuum the house Alejandro Erickson 2011-12-11T20:04:33Z 2011-12-11T20:25:17Z <p>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$). </p> <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$.</p> <ol> <li>How can we compute the minimum number of pivots over all covering sequences $S$?</li> <li>How can we compute the minimum covered area over all covering sequences $S$?</li> </ol> <p>Better formulations of the problem are welcome.</p> <p>For a rectangular polygon, $h\times w$ and a line segment of length $l$, with $h &lt; w$, and $l &lt; 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.</p> <pre><code>___________________________ | l--&gt; | 1 pivot at each end | &lt;--l | | l--&gt; | | &lt;--l | 2 pivots if h is not integer multiple of l --------------------------- </code></pre> http://mathoverflow.net/questions/81523/swat-vs-rioters-cops-vs-robbers-variant SWAT vs Rioters (cops vs robbers variant) Alejandro Erickson 2011-11-21T16:33:05Z 2011-11-21T16:38:15Z <p>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.</p> <p>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.</p> <p>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.</p> <p>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.</p> <p>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.</p> <p>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?</p> <p>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.</p> http://mathoverflow.net/questions/68591/proportion-of-n-symbol-sequences-whose-lp-norm-is-equal-to-n-p proportion of $n$ symbol sequences whose $l^p$ norm is equal to $|[n]|_p$ Alejandro Erickson 2011-06-23T07:00:49Z 2011-06-23T07:00:49Z <p>and each symbol is at most $n$...</p> <p>Any ideas about where to find previous work?</p> <p>I can find the answers for small $n$ using a brute force search, but I'd like to know more generally.</p> <p>For example, $1^3+2^3+3^3+4^3+5^3+6^3+7^3 = 784$</p> <p>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$).</p> <ol> <li><p>For which $p$ is the norm of a permutation of $[n]$ distinct from the norm of these other sequences? </p></li> <li><p>Otherwise, what is the proportion of "false positives"? </p></li> <li><p>Is there a $p_0$ for which $p>p_0$ always gives this distinction? What is $p_0$?</p></li> </ol> http://mathoverflow.net/questions/42850/formulate-edge-length-problem-as-convex-optimization-problem formulate edge length problem as convex optimization problem Alejandro Erickson 2010-10-20T00:01:38Z 2010-10-21T09:35:02Z <p>I want to us convex optimization to describe a problem in computational geometry.</p> <p>Let <code>$E = (E_1, E_2,\ldots , E_m)$</code> 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 <em>critical path</em> 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.</p> <p>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?</p> <p>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).</p> <p>I have a formulation of the above as what appears to be a second-order cone problem (as far as I understand).</p> <p>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$</p> <p>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$,</p> <p>$\min z$</p> <p>such that</p> <p>$|e_i|_2 \le z, 1\le i \le m-1$</p> <p>$x_{l,i} \le x \le x_{r,k}, 1 \le i \le m$</p> <p>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?</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/3044/tools-for-collaborative-paper-writing/21540#21540 Answer by Alejandro Erickson for Tools for collaborative paper-writing Alejandro Erickson 2010-04-16T06:21:48Z 2010-04-16T06:21:48Z <p>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.</p> http://mathoverflow.net/questions/83200/how-to-efficiently-vacuum-the-house Comment by Alejandro Erickson Alejandro Erickson 2011-12-11T20:39:06Z 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. http://mathoverflow.net/questions/83200/how-to-efficiently-vacuum-the-house/83204#83204 Comment by Alejandro Erickson Alejandro Erickson 2011-12-11T20:37:28Z 2011-12-11T20:37:28Z Neat. I didn't think this problem had received so much attention. http://mathoverflow.net/questions/68591/proportion-of-n-symbol-sequences-whose-lp-norm-is-equal-to-n-p Comment by Alejandro Erickson Alejandro Erickson 2011-06-23T15:12:15Z 2011-06-23T15:12:15Z needless to say, I can cut some of the computation by considering multisets of size $n$ on $n$ symbols. http://mathoverflow.net/questions/49298/is-mathematical-intuition-innate-or-can-we-train-and-improve-it Comment by Alejandro Erickson Alejandro Erickson 2010-12-13T19:46:39Z 2010-12-13T19:46:39Z thanks, will delete when the option becomes available (2 days, it says). reposting the question on my blog http://mathoverflow.net/questions/42850/formulate-edge-length-problem-as-convex-optimization-problem/43029#43029 Comment by Alejandro Erickson Alejandro Erickson 2010-10-21T21:48:37Z 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? http://mathoverflow.net/questions/42850/formulate-edge-length-problem-as-convex-optimization-problem Comment by Alejandro Erickson Alejandro Erickson 2010-10-20T21:54:31Z 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. http://mathoverflow.net/questions/42850/formulate-edge-length-problem-as-convex-optimization-problem Comment by Alejandro Erickson Alejandro Erickson 2010-10-20T16:48:02Z 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. http://mathoverflow.net/questions/42850/formulate-edge-length-problem-as-convex-optimization-problem Comment by Alejandro Erickson Alejandro Erickson 2010-10-20T16:44:37Z 2010-10-20T16:44:37Z @ricky ha, maybe i should write one then. I will try those others, not sure what they are.