Timeline for Is there always a maximum anti-rectangle with a corner square?
Current License: CC BY-SA 3.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 23, 2014 at 14:13 | comment | added | Erel Segal-Halevi | @NickGill I added a link to a working paper in which I cited this thread. Thanks again! | |
| Nov 21, 2013 at 18:42 | comment | added | mhum | @ErelSegal-haLevi We don't take a minimal element from every equivalence class. We take an element from every minimal equivalence class (i.e.: each equivalence class containing a minimal element). | |
| Nov 21, 2013 at 9:38 | comment | added | Erel Segal-Halevi | @mhum "In fact, we can construct a maximum anti-rectangle by selecting one representative from each of the minimal equivalence classes" - I think this claim is slightly stronger than the previous claim. Are you sure that, if we take a minimal element from EVERY equivalence class, we get an anti-rectangle? (It is not relevant for the rest of the proof, but still interesting to know) | |
| Nov 19, 2013 at 6:02 | comment | added | Erel Segal-Halevi | @NickGill Sure, I will. It might take several months until I have a paper, though. | |
| Nov 18, 2013 at 10:10 | comment | added | Nick Gill | @ErelSegal-haLevi, perhaps when the paper is written you could add a link on this page - it would be good to see how this bit of work is used. | |
| Nov 18, 2013 at 10:07 | comment | added | Nick Gill | @mhum, I've been offline for the week-end and just seen your answer. Good work at straightening things out! (And forgive me for writing such a sketchy original answer - my excuse is that I was writing it on someone else's ipad-thingy and it was driving me mad.) | |
| Nov 18, 2013 at 8:56 | comment | added | Erel Segal-Halevi | @mhum I would like to cite your answer in a paper. What name should I use? (You can email me if you want) | |
| Nov 17, 2013 at 17:37 | comment | added | mhum | @ErelSegal-haLevi No problem. The equivalence classes defined above might be an interesting clue for whatever else you're looking at too. I'm pretty sure they're formed out of the rectangles you obtain by extending the edges of the polygon (if you work out some examples, I think you'll see what I mean). | |
| Nov 17, 2013 at 17:14 | vote | accept | Erel Segal-Halevi | ||
| Nov 17, 2013 at 17:14 | comment | added | Erel Segal-Halevi | Thank you very much! Now the answer seems complete so I am marking it as the correct answer. Unfortunately I cannot give the bounty twice and I hope you will excuse me for giving it to Nick which initiated the idea... | |
| Nov 17, 2013 at 16:39 | comment | added | mhum | @ErelSegal-haLevi Whoops! That's embarrassing! That'll teach me to go too fast. I've updated my answer with a better exposition (paragraph starting "The key lemma..."). | |
| Nov 17, 2013 at 16:35 | history | edited | mhum | CC BY-SA 3.0 |
Minor typo
|
| Nov 17, 2013 at 7:11 | comment | added | Erel Segal-Halevi | @mhum Excuse my simple question, but, I just cannot figure out your latter equation. For example, in a square, $r=4$, $rr=4$ and $rl=0$, so $rr+rl \neq 2r$. In an L-shape, $r=5$, $l=1$, $rr=4$ and $rl=2$, so again $rr+rl \neq 2r$... | |
| Nov 17, 2013 at 4:30 | comment | added | mhum | @ErelSegal-haLevi In inferred that there are more RR edges than LL edges not from the matching but from the fact that there are more R corners than L corners. Let $r$ and $l$ be the number of R and L corners. Let $rr$, $ll$, and $rl$ be the number of RR, LL, and RL/LR edges. Note that $rr+rl=2r$ and $ll+rl=2l$. Then, $0< r-l = (rr-ll)/2$. So $rr > ll$. | |
| Nov 16, 2013 at 19:43 | comment | added | Erel Segal-Halevi | BTW, the observation "we can construct a maximum anti-rectangle by selecting one representative from each of the minimal equivalence classes" is interesting in itself as a basis for an algorithm for finding anti-rectangles. | |
| Nov 16, 2013 at 19:40 | comment | added | Erel Segal-Halevi | I am not sure about "there are strictly more RR edges than LL edges". There are more R's than L's, but, what if there is a sequence LLL, such that the first LL pair matches an RR pair, and the second LL pair matches a disjoint RR pair, such as the following: i.sstatic.net/1jNJo.png | |
| Nov 15, 2013 at 22:45 | comment | added | mhum | Yes, that was the idea of the last sentence of the third-to-last paragraph: "Note that while there may be more than once such edge, for our purposes we will only need to choose one". I could have fixed the choice as, say, the left-most of such edges, but I thought it would be a little overkill. | |
| Nov 15, 2013 at 22:42 | comment | added | Harry Altman | One note -- you might match up your RR edge with more than one LL edge, I think, if there were two Es that were exactly as far south as one another. But this doesn't affect the result, because there are still more RR than LL, so putting even more LL on a single RR still leaves us with excess RR. | |
| Nov 15, 2013 at 22:02 | history | edited | mhum | CC BY-SA 3.0 |
deleted 4 characters in body
|
| Nov 15, 2013 at 21:02 | history | edited | mhum | CC BY-SA 3.0 |
deleted 19 characters in body
|
| Nov 15, 2013 at 20:40 | history | answered | mhum | CC BY-SA 3.0 |
