MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

# domotorp

 4,373 Reputation 1700 views

## Registered User

 Name domotorp Member for 3 years Seen 7 hours ago Website Location ELTE Age 31
I am an assistant professor at ELTE Budapest interested in combinatorics, complexity theory and combinatorial geometry.
 Jun12 comment If a unitsquare is partitioned into 101 triangles, is the area of one at least 1%?So there are some known lower bounds! Could you give some reference to what kind of gap-theorems you have in mind? I know practically nothing about this topic... Jun12 awarded ● Popular Question Jun11 comment If a unitsquare is partitioned into 101 triangles, is the area of one at least 1%?The above paper also gives only upper bounds, apparently the same as Willie got. It seems that Gunter Ziegler has already posed a similar question to mine in 2003 but there is no citation for it. Jun10 revised If a unitsquare is partitioned into 101 triangles, is the area of one at least 1%?added 204 characters in body Jun10 comment If a unitsquare is partitioned into 101 triangles, is the area of one at least 1%?Thank you, in fact Tapio also gave a similar counterexample, but without calculating the bounds. Jun10 comment If a unitsquare is partitioned into 101 triangles, is the area of one at least 1%?Good point, I did not analyze n=5 careful enough... Jun10 awarded ● Good Question Jun10 awarded ● Mortarboard Jun10 awarded ● Nice Question Jun10 asked If a unitsquare is partitioned into 101 triangles, is the area of one at least 1%? Jun7 comment Sperner’s lemma and Tucker’s lemmaHave you seen this? arxiv.org/pdf/1305.6158.pdf Jun7 comment the following inequality is true，but I can’t prove itI also don't think it is research level. I would try to pair up the terms on the LHS as k and (2d+1-k) and show that the latter is always bigger, then use the series expansion of e^d. Jun7 comment Sperner’s lemma and Tucker’s lemmaBoth Borsuk-Ulam and Tucker have been studied and shown to be PPAD-complete in the linked paper. I also believe that this shows that Sperner can be derived from Tucker, however, it would be nice to have a simple, straightforward reduction. May29 answered How to compute hereditary discrepancy May29 accepted Beck-Fiala for other discrepancies May29 answered Beck-Fiala for other discrepancies May29 comment Arrangements of graphs of linear functions Are you sure you want strict inequalities between g and f? In this case this would be quite easy to prove as $f_i=f_j+c$ and $g_i=g_j+c$ would hold for any i and j with some appropriate constants. Otherwise, I don't think this problem is that hard, I would try induction on $n$. May22 comment In what rigorous sense are Sperner’s Lemma and the Brouwer Fixed Point Theorem equivalent?For someone not into axioms, this can be the proof that they are practically "equivalent" - only one more line (compactness) is needed to derive Brouwer from Sperner. Apr24 revised Generating Random Young Tableaux: A peculiar probability identityfixed link Mar30 comment Is this min not less than a minI think all functions are differentiable in this problem. Or is your problem the max? It only takes the max of a few functions, so it should not cause a big problem. Mar27 comment Hobbled rook tour - Hamiltonian cycle on square gridI have three comments: 1, Meanders are different, there a vertex can be touched twice. 2, There is a related game called Slitherlink. 3, Similar (stronger/weaker?) concept is called Balanced Gray code. Mar24 comment A question about the size of a L1 ball(3) You are right, this is a problem indeed. If $s^*$ is some fix distribution with positive entries while $n\rightarrow\infty$, then the proof is correct, but otherwise not necessarily. E.g., if $s^*$ is zero in all but one row, then we cannot put any coins in the other rows, so we simply get $2^{|\mathcal Y|\log n}$. Either the Lemma is incorrect, or they allow negative entries, or something else is known about $s^*$. Mar24 comment A question about the size of a L1 ball(2) I don't see what is the question here - is it why the distribution is close to even in most cases? You can simply upper bound the cases when in a row the total is, say, 1/10 of the given value and see these do not contribute much. Mar24 comment A question about the size of a L1 ball(1) Because that is approximately that much. If you some from $\sqrt n/2$ to $\sqrt n$, you already get about this much. Mar23 revised A question about the size of a L1 balladded 428 characters in body; edited body Mar23 answered A question about the size of a L1 ball Mar19 awarded ● Nice Question Mar17 comment Turing-complete primitive blind automataWell, I told you I probably don't understand the question... Mar17 answered Turing-complete primitive blind automata Mar1 comment What properties does generalized Delaunay triangulation have?It seems that I have misunderstood the definition of reference-request, thank you for your answer. Feb27 comment What properties does generalized Delaunay triangulation have?Cross-posted on CSTheory: cstheory.stackexchange.com/questions/16661/… Feb27 comment What properties does generalized Delaunay triangulation have?I managed to access the book, it does not even mention Delaunay triangulations. Feb26 comment Is this min not less than a minI think it would be the simplest to find the extreme configuration for that problem too but that seems harder, but probably not much. Maybe you can show by using Lagrange multipliers where the extreme value is. Feb25 answered Is this min not less than a min Feb22 comment What properties does generalized Delaunay triangulation have?Thank you, I think I will cite the book, as in the dissertation the simple properties are not stated. (I hope they are in the book, since I could not access it.) Also, here is a direct link to the dissertation: fernuniversitaethagen.de/imperia/md/content/… Feb21 asked What properties does generalized Delaunay triangulation have? Feb9 comment Invariant measures for Cellular automata@R W: I think that if you have x followed by y, then you must take the x+1-st row of the matrix and the y+1-st column of it to get the new value of x. Jan29 answered Edge-coloring of the complete graph without any rainbow paths Jan28 comment Non-unique 2-factorization of 2k-regular graphsLet me counter-question - what is known about moving between 1-factorizations of regular bipartite graphs? Jan25 answered Non-unique 2-factorization of 2k-regular graphs Jan18 answered Majority vote of total orders Jan17 comment A generalization of intermediate value theorem on R^k.Yes, clear now, thx. Is anything known about how many dividing points are needed for the inverse integer generalization in higher dims? Jan16 comment A generalization of intermediate value theorem on R^k.I knew the k=2 result for functions (ie. f(x)=(x,g(x)), but not this one. More sadly, I cannot even understand it. Why can it not happen that the sum of the segments is 1/2(r(b)+r(a))? If x_1 and x_{n+1} have opposite signs, this seems to be the case. Jan10 comment Alternative proof for counting problem in graphsI think you should define what you mean by (spanning) subgraph in the question to avoid misunderstandings. Jan6 comment Covering all, but $k$ points with affine subspaces@Ilya: You are right, it becomes hard only for R instead of F2. @ACL: This is essentially the proof I linked to. Jan6 comment What are conjectures that are true for primes but then turned out to be false for some composite number?I see, thanks! Jan5 comment Covering all, but $k$ points with affine subspacesWhat is the easy proof for d=1 and k=1? I thought you need algebraic methods to prove this. math.uiuc.edu/~z-furedi/PUBS/… Jan5 comment What are conjectures that are true for primes but then turned out to be false for some composite number?I think I wrote the same in the second sentence of the problem description. Jan4 awarded ● Popular Question Jan4 comment What are conjectures that are true for primes but then turned out to be false for some composite number?@jp: example for what? I mentioned Carmichael numbers in the question. @Davidac897: ?