domotorp
|
Registered User
|
I am an assistant professor at ELTE Budapest interested in combinatorics, complexity theory and combinatorial geometry.
|
|
Jun 12 |
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... |
|
Jun 12 |
awarded | ● Popular Question |
|
Jun 11 |
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. |
|
Jun 10 |
revised |
If a unitsquare is partitioned into 101 triangles, is the area of one at least 1%? added 204 characters in body |
|
Jun 10 |
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. |
|
Jun 10 |
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... |
|
Jun 10 |
awarded | ● Good Question |
|
Jun 10 |
awarded | ● Mortarboard |
|
Jun 10 |
awarded | ● Nice Question |
|
Jun 10 |
asked | If a unitsquare is partitioned into 101 triangles, is the area of one at least 1%? |
|
Jun 7 |
comment |
Sperner’s lemma and Tucker’s lemma Have you seen this? arxiv.org/pdf/1305.6158.pdf |
|
Jun 7 |
comment |
the following inequality is true，but I can’t prove it I 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. |
|
Jun 7 |
comment |
Sperner’s lemma and Tucker’s lemma Both 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. |
|
May 29 |
answered | How to compute hereditary discrepancy |
|
May 29 |
accepted | Beck-Fiala for other discrepancies |
|
May 29 |
answered | Beck-Fiala for other discrepancies |
|
May 29 |
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$. |
|
May 22 |
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. |
|
Apr 24 |
revised |
Generating Random Young Tableaux: A peculiar probability identity fixed link |
|
Mar 30 |
comment |
Is this min not less than a min I 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. |
|
Mar 27 |
comment |
Hobbled rook tour - Hamiltonian cycle on square grid I 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. |
|
Mar 24 |
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^*$. |
|
Mar 24 |
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. |
|
Mar 24 |
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. |
|
Mar 23 |
revised |
A question about the size of a L1 ball added 428 characters in body; edited body |
|
Mar 23 |
answered | A question about the size of a L1 ball |
|
Mar 19 |
awarded | ● Nice Question |
|
Mar 17 |
comment |
Turing-complete primitive blind automata Well, I told you I probably don't understand the question... |
|
Mar 17 |
answered | Turing-complete primitive blind automata |
|
Mar 1 |
comment |
What properties does generalized Delaunay triangulation have? It seems that I have misunderstood the definition of reference-request, thank you for your answer. |
|
Feb 27 |
comment |
What properties does generalized Delaunay triangulation have? Cross-posted on CSTheory: cstheory.stackexchange.com/questions/16661/… |
|
Feb 27 |
comment |
What properties does generalized Delaunay triangulation have? I managed to access the book, it does not even mention Delaunay triangulations. |
|
Feb 26 |
comment |
Is this min not less than a min I 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. |
|
Feb 25 |
answered | Is this min not less than a min |
|
Feb 22 |
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/… |
|
Feb 21 |
asked | What properties does generalized Delaunay triangulation have? |
|
Feb 9 |
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. |
|
Jan 29 |
answered | Edge-coloring of the complete graph without any rainbow paths |
|
Jan 28 |
comment |
Non-unique 2-factorization of 2k-regular graphs Let me counter-question - what is known about moving between 1-factorizations of regular bipartite graphs? |
|
Jan 25 |
answered | Non-unique 2-factorization of 2k-regular graphs |
|
Jan 18 |
answered | Majority vote of total orders |
|
Jan 17 |
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? |
|
Jan 16 |
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. |
|
Jan 10 |
comment |
Alternative proof for counting problem in graphs I think you should define what you mean by (spanning) subgraph in the question to avoid misunderstandings. |
|
Jan 6 |
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. |
|
Jan 6 |
comment |
What are conjectures that are true for primes but then turned out to be false for some composite number? I see, thanks! |
|
Jan 5 |
comment |
Covering all, but $k$ points with affine subspaces What 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/… |
|
Jan 5 |
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. |
|
Jan 4 |
awarded | ● Popular Question |
|
Jan 4 |
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: ? |
