Sam Hopkins
|
Registered User
|
|
|
May 20 |
comment |
objects which can’t be defined without making choices but which end up independent of the choice The sandpile group of a graph (as an abstract group) is independent of the choice of sink vertex, but I don't see how it could be defined without respect to a sink vertex. |
|
May 20 |
comment |
Yitang Zhang’s preprint on Landau-Siegel zeros Isn't it the third major claim in analytic number theory (along with Zhang's work on bounded gaps in the primes and H. A. Helfgott's proof of the weak Goldbach conjecture)? |
|
May 4 |
comment |
Verifying the correctness of a Sudoku solution Does the matroid property easily generalize to $n \times n$-Sudoku? |
|
Apr 27 |
comment |
Expected edit distance Is it obvious that the limit exists? |
|
Apr 20 |
comment |
Will quantum computing kill cryptography ? Fair enough. I know that there has at least been a good deal of research into breaking codes of this sort via quantum computers. See en.wikipedia.org/wiki/…. Although the crypto-optimist might as easily argue that the fact that there has been research but no results shows the systems to be safe. |
|
Apr 20 |
comment |
Will quantum computing kill cryptography ? But isn't it the case that an efficient quantum algorithm for the dihedral hidden subgroup problem would break these vector cryptosystems? |
|
Apr 12 |
comment |
Non-constructive proofs vs. efficient algorithms Thank you, I think this is the most comprehensive and clear answer. |
|
Apr 8 |
comment |
How long can this string of digits be extended? What does "N(b) > n" mean? |
|
Apr 5 |
comment |
Combinatorial distance between simplicial complexes What about the cardinality of the symmetric difference between the complexes viewed as abstract simplicial complexes? |
|
Mar 25 |
awarded | ● Fanatic |
|
Mar 15 |
revised |
What is the graphical version of the circle parking story? added 214 characters in body; edited tags; edited title; edited body |
|
Mar 14 |
asked | What is the graphical version of the circle parking story? |
|
Mar 9 |
comment |
to find a function with a property Whoops, I understand now that the analytic sense of automorphism (holomorphic bijection) is meant. |
|
Mar 9 |
comment |
Does this poset have a unique minimal element? Their paper is now on the arxiv: arxiv.org/abs/1303.1551 |
|
Feb 18 |
comment |
What is the sandpile torsor? Having to choose a vertex as sink when defining the sandpile group is indeed annoying. I don't know whether it has anything to say about this question, but in this paper: arxiv.org/abs/1112.5421, Dave Perkinson and I define "quasi-superstable" divisors of $G$ without distinguishing a sink and show how they encode all the superstable elements with respect to any sink of $G$. |
|
Feb 16 |
awarded | ● Nice Question |
|
Feb 16 |
comment |
Is there a n/2 version of the Erdős-Hanani conjecture? @Gerhard Paseman: it looks like the repository has $n < 100$, $k \leq 25$ and $t \leq 8$. With such small values it is not possible to detect the presence or absence of a log factor. |
|
Feb 16 |
revised |
Is there a n/2 version of the Erdős-Hanani conjecture? explained the permutation idea better |
|
Feb 16 |
comment |
Is there a n/2 version of the Erdős-Hanani conjecture? I should mention also that the Graham-Sloane construction means that the EH-conjecture for $k = \phi(n)$ and $t = k - 1$ has a positive answer when $\phi(n) = o(n)$, so $n/2$ is in fact the "hard case." |
|
Feb 16 |
comment |
Is there a n/2 version of the Erdős-Hanani conjecture? @Brendan McKay: Yes, thank you. It is corrected. |
|
Feb 16 |
revised |
Is there a n/2 version of the Erdős-Hanani conjecture? corrected t vs. l typo; added 6 characters in body |
|
Feb 16 |
asked | Is there a n/2 version of the Erdős-Hanani conjecture? |
|
Feb 15 |
comment |
Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another It might also be worth looking for a connection to sandpile models on digraphs, which also involve the movement of chips from node to node. |
|
Jan 25 |
comment |
How random are random spanning trees? @AaronMeyerowitz: I now see why this question is more difficult than I thought at first. Thanks. |
|
Jan 25 |
comment |
How random are random spanning trees? I assume you're considering labeled trees/graphs. Here's an answer for an easier version of the question, which maybe you have already considered: suppose you choose each connected graph on n vertices with equal probability, and suppose you choose from it a random spanning tree. Then it seems clear to me that all trees are equally likely. |
|
Jan 24 |
comment |
Is there a characterization of hyperplane arrangement intersection posets? Thank you for the reference, I will get a copy of this book. I assume that the answer is in general rather complicated? |
|
Jan 24 |
asked | Is there a characterization of hyperplane arrangement intersection posets? |
|
Jan 21 |
comment |
probability of zero subset sum I don't know the answer, but I do know that this problem is related to (in fact, essentially equivalent to): mathoverflow.net/questions/118960/… and mathoverflow.net/questions/62764/… via the finite field method |
|
Jan 19 |
comment |
Minimum sum among fixed length factors of a number So this minimum measures how close $n$ is to being a $k$-th power? |
|
Jan 19 |
awarded | ● Critic |
|
Jan 17 |
comment |
What is the expected value for this I haven't really thought about it, but you should be able to recast the problem in graph-theoretic terms and then use some probabilistic tools, similar to the proof of Ramsey number bounds. |
|
Jan 17 |
comment |
What is the expected value for this Related: en.wikipedia.org/wiki/Happy_ending_problem |
|
Jan 15 |
comment |
connected components of a real hyperplane arrangement This is a trivial observation, but if you use the finite field method, you get the characteristic polynomial is $\chi(q) = q^n - |\{(a_1,\ldots,a_n) \in \mathbb{F}_q^n\colon \textrm{some nonempty subset of the $a_i$ sums to $0 \mod q$}\}|$. That looks like a terribly difficult counting problem, of course. |
|
Jan 15 |
awarded | ● Nice Answer |
|
Jan 14 |
answered | Elementary applications of linear algebra over finite fields |
|
Jan 7 |
comment |
Usage of set theory in undergraduate studies Just to add on to what David Roberts mentioned in the first comment, according to wiki (en.wikipedia.org/wiki/William_Lawvere), ETCS came about after Lawvere needed some foundational axioms to teach a few undergraduate courses at Reed College. |
|
Jan 2 |
awarded | ● Nice Answer |
|
Dec 31 |
awarded | ● Teacher |
|
Dec 31 |
answered | New grand projects in contemporary math |
|
Dec 30 |
comment |
Non-constructive proofs vs. efficient algorithms Corrected, thanks. |
|
Dec 30 |
revised |
Non-constructive proofs vs. efficient algorithms edited body |
|
Dec 30 |
comment |
Non-constructive proofs vs. efficient algorithms If "give me an example" is what determines whether a proof is constructive, I think that the Erdos proof is nonconstructive. You'll never come up with a coloring for n=100, say. Better yet, consider the Green-Tao theorem. It provides a "constructive" proof that there is an arithmetic progression of 1,000 primes, but you will never get such a progression in the lifetime of the universe just using that proof and exhaustive search. |
|
Dec 30 |
asked | Non-constructive proofs vs. efficient algorithms |
|
Dec 28 |
comment |
Are there sampNP-intermediate problems? Does this question still make sense for other "average case" complexity classes like AvgP, DistP, and HeurP? I'm getting these from complexityzoo.uwaterloo.ca/Complexity_Zoo, which incidentally doesn't list sampP. |
|
Dec 24 |
comment |
A novice question on Quantum Mechanics Note that defining quantum states as equivalence classes of unit vectors that differ only by a global phase will also lead to problems with composite states and tensor products (where the phase difference between two tensor factors now suddenly matters.) |
