András Salamon
|
Registered User
|
Graduate student in computer science, working on the computational complexity of constraint satisfaction problems.
|
|
2d |
comment |
Why don’t more mathematicians improve Wikipedia articles? Every Wikipedia page has its full date-stamped history available (it is one of the tabs visible on every page), complete with change tracking. In my experience truly anonymous edits tend to be either spam (and quickly reverted) or small fixes by someone who couldn't be bothered to log on; it is therefore usually easy to get a feel for who has made significant contributions. In fact, the sheer volume of Wikipedia change history can be overwhelming. |
|
2d |
comment |
Why don’t more mathematicians improve Wikipedia articles? I don't find this at all; the Wikipedia articles I look at daily (many of them in mathematics and technical subjects) could nearly all do with at least copy-editing or improvement of references. It takes about as long to fix a typo as it does to glance at the new mail in one's mailbox, and about as long to correct a sloppy reference as it does to read (but not contribute to) a soft question on MO with a dozen answers. |
|
2d |
comment |
Motivation for Frankl’s conjecture? From the abstract of Poonen's 1992 article Union-closed families dx.doi.org/10.1016/0097-3165(92)90068-6 comes the sentence "Frankl conjectured in 1979 that...". |
|
2d |
comment |
Motivation for Frankl’s conjecture? The Handbook was first published in 1995, and there is only one edition. |
|
May 19 |
comment |
Are all sets totally ordered ? The Howard/Rubin book cites: James D. Halpern and Azriel Levy, The ordering theorem does not imply the axiom of choice, Notices of the AMS 11 (1964), 56. |
|
May 4 |
comment |
Incremental minimum spanning tree Relevant is David Eppstein's work on dynamic algorithms for minimum spanning trees dx.doi.org/10.1006/jagm.1994.1033 or the preprint at ics.uci.edu/~eppstein/pubs/Epp-TR-92-04.pdf |
|
May 2 |
comment |
Weakest choice principle required for Robertson-Seymour Graph Minor Theorem? That seems to settle things -- thanks for elaborating. |
|
May 1 |
comment |
Weakest choice principle required for Robertson-Seymour Graph Minor Theorem? Andrey Bovykin's "Unprovability threshold for the planar graph minor theorem" from 2010 states that the upper bound for the Graph Minor Theorem is $\Pi_1^1-\text{CA}+\text{BI}$, from the Friedman/Robertson/Seymour paper mentioned in the question. I am not familiar with BI -- but is this just a fragment of second-order arithmetic? |
|
Apr 30 |
comment |
Weakest choice principle required for Robertson-Seymour Graph Minor Theorem? Emil, I think Timothy was just trying to say that (some form of) Kruskal's Tree Theorem is a special case of (some form of) Graph Minor Theorem, yet KTT usually does seem to need some form of choice. |
|
Apr 29 |
asked | Weakest choice principle required for Robertson-Seymour Graph Minor Theorem? |
|
Apr 28 |
comment |
What can be proven in Peano arithmetic but not Heyting arithmetic? I'm confused: to what are you referring when you say "(which refutes CT)"? |
|
Apr 17 |
comment |
In Szemerédi’s Regularity Lemma, how many blocks are in the partition? Thanks! It seems I'd read a reference to this in the survey paper: János Komlós, Ali Shokoufandeh, Miklós Simonovits, Endre Szemerédi, The Regularity Lemma and Its Applications in Graph Theory, STACS 2002, LNCS 2292. dx.doi.org/10.1007/3-540-45878-6_3 |
|
Apr 17 |
revised |
In Szemerédi’s Regularity Lemma, how many blocks are in the partition? fix braces |
|
Apr 17 |
comment |
In Szemerédi’s Regularity Lemma, how many blocks are in the partition? Thanks, that is a useful set of pointers! |
|
Apr 16 |
asked | In Szemerédi’s Regularity Lemma, how many blocks are in the partition? |
|
Mar 28 |
comment |
Awfully sophisticated proof for simple facts Although I like the example, I'm not sure I follow your argument. For the case of forests we already know the finite set of forbidden minors: $\{C_3\}$. So Robertson-Seymour doesn't really enter the picture except via the $O(n^3)$ test, which is really a different theorem. |
|
Mar 28 |
revised |
Awfully sophisticated proof for simple facts fixed second proof |
|
Mar 18 |
comment |
What is the spectrum of the Rado graph? Why would $0,…,n−1$ using Rado's original numbering be the natural choice of finite restriction—why not the $n$ least-numbered neighbours of some enumeration of the vertices, or the first $n$ vertices in some other numbering of the graph? The spectrum seems to depend on this choice, and it seems possible that the limits obtained for some choices differ from other choices. |
|
Mar 18 |
comment |
What is the spectrum of the Rado graph? As David Cohen commented, what notion of spectrum are you intending for a graph in which every vertex has infinite degree? |
|
Dec 31 |
accepted | Simple lower bounds for Bell numbers (number of set partitions)? |
|
Dec 30 |
answered | Old books still used |
|
Dec 14 |
answered | Simple lower bounds for Bell numbers (number of set partitions)? |
|
Dec 14 |
comment |
Simple lower bounds for Bell numbers (number of set partitions)? @Gerhard Paseman: Those two naming strategies give the lower and upper bounds I sketched (Kousha Etessami originally suggested the idea to me). To go from $\log c_n \ge -(1+\epsilon)$ to $\log c_n \ge 0$ seems to require a new idea. |
|
Dec 13 |
revised |
Simple lower bounds for Bell numbers (number of set partitions)? correct grammar |
|
Dec 13 |
asked | Simple lower bounds for Bell numbers (number of set partitions)? |
