User sam hopkins - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T21:12:29Z http://mathoverflow.net/feeds/user/25028 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/119722/is-there-a-characterization-of-hyperplane-arrangement-intersection-posets Is there a characterization of hyperplane arrangement intersection posets? Sam Hopkins 2013-01-24T03:21:01Z 2013-04-11T16:08:14Z <p>For a hyperplane arrangement $\mathcal{A}$ over a vector space $V$, we define its intersection poset, $L(\mathcal{A})$, as the set of all nonempty intersections of hyperplanes in $\mathcal{A}$ ordered by reverse inclusion. The empty intersection, $V$ itself, is the unique minimal element of $L(\mathcal{A})$.</p> <p>It is known that $L(\mathcal{A})$ is a ranked meet-semilattice, and moreover, any interval $[x,y]$ in $L(\mathcal{A})$ is a geometric lattice. But these properties alone are not sufficient for some poset $P$ to be the intersection poset of a hyperplane arrangement. Consider the following poset:<img src="http://www.freeimagehosting.net/newuploads/b4quk.png" alt="poset"></p> <p>If this were the intersection poset of some arrangement, then $a$ would be parallel to $d$ and to $c$, $b$ would be parallel to $d$, and thus $b$ and $c$ would be parallel. But $b$ and $c$ have nonempty intersection, so this is nonsense.</p> <p>Is there a known characterization of hyperplane arrangement intersection posets?</p> http://mathoverflow.net/questions/117574/non-constructive-proofs-vs-efficient-algorithms Non-constructive proofs vs. efficient algorithms Sam Hopkins 2012-12-30T00:25:39Z 2013-04-05T08:17:41Z <p>My question concerns what is meant by "nonconstructive", and whether it has ever been defined in terms of computational complexity.</p> <p>The wikipedia article on <a href="http://en.wikipedia.org/wiki/Constructive_proof" rel="nofollow">constructive proof</a> begins, "a constructive proof is a method of proof that demonstrates the existence of a mathematical object by creating or providing a method for creating the object." On the other hand, the wiki article on <a href="http://en.wikipedia.org/wiki/Probabilistic_method" rel="nofollow">the probabilistic method</a> states, "the probabilistic method is a nonconstructive method [...] for proving the existence of a prescribed kind of mathematical object." I believe these two statements are at odds with one another.</p> <p>Consider Erdős's celebrated proof of the lower bound of the Ramsey number. This proof shows that as long as $\binom{n}{r} &lt; 2^{\binom{r}{2} - 1}$, there is some coloring of the edges of $K_n$ with $2$ colors that has no monochromatic sub-$K_r$. The proof offers no idea what such a coloring looks like; however, it <em>does</em> lead to a "method for creating" the object in question: try all possible colorings. The proof guarantees that this naive algorithm terminates. Of course, this algorithm quickly becomes computationally infeasible. But in principle, via exhaustive search, any proof of the existence of an object in some finite collection admits of a "method for creating" the object.</p> <p>Imagine now that we had a different proof of the lower bound of the Ramsey number. This new proof constructs two possible edge-$2$-colorings of $K_n$ and shows that at least one must result in no monochromatic sub-$K_r$, although it remains silent about which of the two colorings works. I think this would also qualify as a "non-constructive" proof (based on analogy to the wiki example with $\sqrt{2}^{\sqrt{2}}$), and yet it would lead to a wonderfully efficient method for finding such colorings. For any $r$, this hypothetical proof says we have to check only two candidates to get the object we're looking for. I think this even gives us a polynomial time algorithm for finding such a coloring (but this depends on how quickly we can verify a coloring.) At any rate, I hope the distinction I am trying to draw is clear.</p> <p>Does it makes sense to say that a constructive proof is a proof that leads to an efficient algorithm for creating an object with a desired set of properties? Has there been any work related to such a definition? The above is most relevant to statements in discrete math.</p> http://mathoverflow.net/questions/124475/what-is-the-graphical-version-of-the-circle-parking-story What is the graphical version of the circle parking story? Sam Hopkins 2013-03-14T02:51:39Z 2013-03-15T18:36:27Z <p>The classical parking function story is as follows: we have cars $v_1,\ldots,v_n$ who approach a line of spaces marked $0,\ldots,n-1$ in order. Each car $v_i$ has space preference $a_i$. A car will drive until it reaches its preferred spot; if its preferred spot is empty, it will park there, otherwise it will park in the first empty spot after this space. If there is no empty spot after its preferred space, the car cannot park. A parking function is a list $(a_1,\ldots,a_n)$ such that all the cars get to park.</p> <p>Say we add car $v_0$, space $-1$, and dictate that $v_0$ always prefers spot $-1$. A reformulation of the parking story is now as follows. Repeat the following as long as you can: look through the cars $v_i$ that have yet to park in order, and park the first one you come to whose preference is less than the number of cars that have yet parked. It is easy to see that if all the cars park, this gives the same parking order as above, and if the process here fails (i.e. not all cars park), then the process above fails as well.</p> <p>Now it is pretty clear how to translate this to graphs. For background on the Abelian sandpile model, see <a href="http://arxiv.org/abs/1112.6163" rel="nofollow">http://arxiv.org/abs/1112.6163</a>. Let $G$ be a graph on vertices $v_0,\ldots,v_n$, with $v_0$ identified as a sink. Consider some configuration $c := \sum c_i v_i$ on the vertices of $G$ with $c_0 = -1$ and $c_i \geq 0$ for $i > 0$. Let $c_{\mathrm{max}} := \sum (\mathrm{deg}(v_i) - 1)v_i$, and dualize your configuration to $b := c_{\mathrm{max}} - c$. Repeat the following as long as you can: look through the vertices $v_i$ that have yet to fire in order, and fire the first one you come to that is unstable. By Dhar's algorithm, the configuration $b$ is recurrent if and only if all of the vertices fire, and in this case $c$ is superstable, i.e. a $G$-parking function. We have thus a nice translation of the parking story to graphs; the dictionary between terms in the two stories looks like:</p> <ul> <li>parking preference of $v_i$ ---> number of grains of sand on $v_i$</li> <li>order that cars approach spaces ---> firing preference order</li> <li>order that cars park ---> order that vertices fire</li> <li>all the cars park ---> all the vertices fire</li> </ul> <p>There is a cute way to count classical parking functions. Add a space $n$ and put the parking spaces in a circle instead of a line. Allow preference for spot $n$. All the cars will now be able to park, and one space will be empty. But such a "circular" parking function is only a real parking function when space $n$ is empty. And (you can convince yourself of this by considering $(a_1 + j, \ldots, a_n + j)$ reduced mod $n$) over all circular parking functions, each spot is equally likely to be left blank. So the number of parking functions is $1/(n+1) \cdot (n+1)^{n} = (n+1)^{n-1}$, Cayley's formula for the number of spanning trees of $K_{n+1}$.</p> <p>My question is, can we translate this circle parking story to graphs so that the above dictionary of terms still makes sense? We cannot hope for a nice formula for the number of graphical parking functions because in general this number is the number of spanning trees of $G$ (which is the determinant of the reduced Laplacian). But perhaps this circle parking story will tell us something <i>algebraic</i>. In particular, I think that adding an extra spot corresponds in some way to considering the graph $G_{\bullet}$, the graph obtained from $G$ by adding an extra vertex $q$ connected by an edge to every vertex in $G$ and with $q$ now regarded as the sink. If so, the circle parking story might tell us how the superstable group of $G$ sits inside the stable semigroup of $G_{\bullet}$. For the connection between $G_{\bullet}$-parking functions and $G$-parking functions, see: <a href="http://arxiv.org/abs/1112.5421" rel="nofollow">http://arxiv.org/abs/1112.5421</a>.</p> http://mathoverflow.net/questions/121961/is-there-a-n-2-version-of-the-erds-hanani-conjecture Is there a n/2 version of the Erdős-Hanani conjecture? Sam Hopkins 2013-02-16T01:02:33Z 2013-02-16T02:24:27Z <p>This question comes out of REU research from this past summer. Unfortunately weeks of thought led to only trivial observations and the conclusion that the problem is quite hard.</p> <p>Fix $k,t$. Let $F$ be a set of $k$-subsets of $[n] := \{1,\ldots,n\}$ of minimal cardinality such that $F$ covers all $t$-subsets of $[n]$ (covers in the sense that any $t$-subset of $[n]$ is a subset of an element of $F$.) Let $\kappa_n := |F|$. The Erdős-Hanani conjecture states that </p> <blockquote> <p>$\kappa_n = \binom{n}{t} / \binom{k}{t}(1 + o(1))$. </p> </blockquote> <p>Of course $\binom{n}{t} / \binom{k}{t}$ is a lower bound on $\kappa_n$, so the EH conjecture is saying that the obvious necessary condition is asymptotically sufficient. Rödl proved the EH conjecture in 1985.</p> <p>This question is about what happens when $k$ and $t$ are not fixed. Specifically, take $k = \lfloor n/2 \rfloor$ and $t = \lfloor n/2\rfloor - 1$. Define $F$ and $\kappa_n$ as above. Is it true that</p> <blockquote> <p>$\kappa_n = \frac{1}{\lfloor n / 2 \rfloor} \binom{n}{\lfloor n/2 \rfloor}(1 + o(1))$?</p> </blockquote> <h1>Background</h1> <p>The EH conjecture lead to the study of what is called "packing in a hypergraph." See <a href="http://en.wikipedia.org/wiki/Packing_in_a_hypergraph" rel="nofollow">http://en.wikipedia.org/wiki/Packing_in_a_hypergraph</a>. Rödl's proof introduced what is now called the "Rödl nibble" and is pseudo-random in nature. Spencer gave a lovely proof using branching processes. There are a lot of results from the late 80s to 90s that say, as Kahn puts it in "Asymptotics of Hypergraph Matching, Covering and Coloring Problems", that hypergraphs are asymptotically well-behaved <i>as long as their edge sizes are bounded</i>! Unfortunately the $n/2$ version of EH involves hypergraphs of unbounded edge size and the existing methods appear useless.</p> <h1>Some ideas</h1> <p>A straightforward application of the method of alterations (or equivalently, some easy analysis of the greedy algorithm) gives that $\kappa_n \leq \log n \frac{1}{\lfloor n / 2 \rfloor} \binom{n}{\lfloor n/2 \rfloor} (1 + o(1))$, so the whole question is whether we can eliminate this log factor.</p> <p>A set of $\lfloor n/2 \rfloor$-subsets has maximum coverage of $(\lfloor n/2 \rfloor - 1)$-subsets when all its elements have pairwise symmetric difference of at least 4. So really this is a coding theory problem. The paper "Lower bounds for constant weight codes" by Graham and Sloane shows that we can find a set $H$ of $\lfloor n /2\rfloor$-subsets of $[n]$ such that $|H| \geq \frac{1}{2}\binom{n}{\lfloor n/2 \rfloor}$ and the hamming distance between elements is at least 4. Let $G$ be the set of $(\lfloor n/2 \rfloor - 1)$-subsets covered by $H$. $G$ is half the size we want it to be, but we only used half as many elements are we are allowed. So we might be optimistic that by allowing some small overlap we can cover everything we want. If we take a permutation $\sigma \in S_n$ and look at $\sigma(H)$ (i.e. apply the permutation to the elements of the elements of $H$) it covers $\sigma(G)$. Of course $|\sigma(G)| = |G|$. We could hope that a good choice of $\sigma$ gives $|G \cup \sigma(G)| \approx 2|G|$ and we have found an appropriate set $F := H \cup \sigma(H)$. I asked the question of whether such a $\sigma$ must exist before: <a href="http://mathoverflow.net/questions/101886/size-of-union-of-a-set-of-subsets-and-its-permutations" rel="nofollow">http://mathoverflow.net/questions/101886/size-of-union-of-a-set-of-subsets-and-its-permutations</a>. That question is interesting in its own right, but this EH conjecture is really why I wanted an answer.</p> http://mathoverflow.net/questions/118903/elementary-applications-of-linear-algebra-over-finite-fields/118906#118906 Answer by Sam Hopkins for Elementary applications of linear algebra over finite fields Sam Hopkins 2013-01-14T17:39:55Z 2013-01-14T17:39:55Z <p>You can use linear algebra over $\mathbb{F}_2$ to solve the game "Lights Out": <a href="http://en.wikipedia.org/wiki/Lights_Out_%28game%29" rel="nofollow">http://en.wikipedia.org/wiki/Lights_Out_%28game%29</a></p> http://mathoverflow.net/questions/117668/new-grand-projects-in-contemporary-math/117741#117741 Answer by Sam Hopkins for New grand projects in contemporary math Sam Hopkins 2012-12-31T16:23:56Z 2012-12-31T16:23:56Z <p>Is quantum computing too far away from pure math to qualify? Perhaps it has not shaken up mathematics so much, but it has brought together theoretical physics, computer science, and mathematics in a way unseen before.</p> http://mathoverflow.net/questions/111326/number-of-forests-of-size-i-and-the-tutte-polynomial Number of forests of size $i$ and the Tutte polynomial Sam Hopkins 2012-11-03T00:59:16Z 2012-11-03T02:59:33Z <p>In "The Potts model and the Tutte Polynomial", D.J.A. Welsh and C. Merino claim on pg. 1135, equation 18, that, \begin{align*} \sum_{i=0}^{n-1}f_i t^i = t^{n-1}T_G(1+\frac{1}{t},1) \end{align*} where $T_G(x,y)$ is the Tutte polynomial of some graph $G$ and $f_i$ denotes the number of forests of $G$ with exactly $i$ edges. Their paper is available online <a href="http://www.yaroslavvb.com/papers/welsh-potts.pdf" rel="nofollow">here</a>.</p> <p>Welsh and Merino do not give any citations or proof for this claim. Does anyone know of such a proof? Also, is there a more explicit formula for $f_i$ in terms of $T_G(x,y)$?</p> http://mathoverflow.net/questions/106013/hypergraph-coloring-problem-motivated-by-legal-billards-racks Hypergraph coloring problem motivated by legal billards racks Sam Hopkins 2012-08-31T03:06:25Z 2012-08-31T05:34:10Z <p>Motivation</p> <p>There are several rules about what makes a rack legal for a game of eight-ball: the top ball has to be a solid, the eight-ball is in the middle, the two bottom vertices have to be one solid and one stripe, etc. But a rule I learned when I first learned to play pool was that there should be no three balls which are pairwise touching each other that are all stripes or all solids. Apparently this is not an actual rule for professional eight-ball. Nevertheless, it is an interesting restriction.</p> <p>Problem</p> <p>Suppose we color the points in a triangular grid with base length $n$ with two colors, $A$ or $B$. How many such colorings have the property that no three points in a touching triangle are all the same color?</p> <p>For instance, with $n=4$, a legal coloring is,</p> <pre><code> A B A A B B B B A B </code></pre> <p>but an illegal coloring is,</p> <pre><code> A B A A A B B A B A </code></pre> <p>because it contains a triangle with three $A$s.</p> <p>If $\kappa(n)$ denotes the number of legal colorings for a grid with base $n$, what is $\kappa(n)$?</p> http://mathoverflow.net/questions/101886/size-of-union-of-a-set-of-subsets-and-its-permutations Size of union of a set of subsets and its permutations Sam Hopkins 2012-07-10T20:20:54Z 2012-07-10T20:20:54Z <p>For $[n] := \{1,...,n\}$, let $G$ be the set of all $\lceil n/2\rceil$-subsets of $[n]$. For a permutation $\rho \in S_{n}$, and some $F \subset G$, define $\rho(F)$ in the natural way: apply $\rho$ to each element in every set in $F$ and let $\rho(F)$ be the set of these new subsets. For example, if $F = \{ \{1,2\}, \{3,4\} \}$, and $\rho = 3241$ (in one-line notation), then $\rho(F) = \{\{2,3\},\{1,4\}\}$. Obviously $|\rho(F)| = |F|$. </p> <p>Fixing some integer $k$, is there anything we can say about $K(n,k) := \min_{F \subset G, |F| = k} \max_{\rho \in S_n} |F \cup \rho(F)|$?</p> <p>By symmetry considerations, for a fixed $F$, every $\lceil n/2\rceil$-subsets of $[n]$ is contained in the same number of $\rho(F)$'s, so for an "average" $\rho$ we have $\frac{|F \cap \rho(F)|}{|F|} = \frac{|F|}{|G|}$. That is, we can always find a $\rho$ such that $|F \cap \rho(F)| \leq \frac{|F|^2}{|G|}$. Then, $K(n,k) \geq 2k - \frac{k^2}{n \choose \lceil n/2 \rceil}$.</p> <p>The question is, can we always (ever?) do much better than this average?</p> http://mathoverflow.net/questions/131255/objects-which-cant-be-defined-without-making-choices-but-which-end-up-independen Comment by Sam Hopkins Sam Hopkins 2013-05-20T22:29:09Z 2013-05-20T22:29:09Z 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. http://mathoverflow.net/questions/131221/yitang-zhangs-preprint-on-landau-siegel-zeros/131254#131254 Comment by Sam Hopkins Sam Hopkins 2013-05-20T18:34:25Z 2013-05-20T18:34:25Z 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)? http://mathoverflow.net/questions/129143/verifying-the-correctness-of-a-sudoku-solution/129599#129599 Comment by Sam Hopkins Sam Hopkins 2013-05-04T05:01:29Z 2013-05-04T05:01:29Z Does the matroid property easily generalize to $n \times n$-Sudoku? http://mathoverflow.net/questions/128903/expected-edit-distance Comment by Sam Hopkins Sam Hopkins 2013-04-27T18:29:43Z 2013-04-27T18:29:43Z Is it obvious that the limit exists? http://mathoverflow.net/questions/128176/will-quantum-computing-kill-cryptography/128179#128179 Comment by Sam Hopkins Sam Hopkins 2013-04-20T18:49:48Z 2013-04-20T18:49:48Z 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 <a href="http://en.wikipedia.org/wiki/Hidden_subgroup_problem#Motivation" rel="nofollow">en.wikipedia.org/wiki/&hellip;</a>. 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. http://mathoverflow.net/questions/128176/will-quantum-computing-kill-cryptography/128179#128179 Comment by Sam Hopkins Sam Hopkins 2013-04-20T18:00:22Z 2013-04-20T18:00:22Z But isn't it the case that an efficient quantum algorithm for the dihedral hidden subgroup problem would break these vector cryptosystems? http://mathoverflow.net/questions/117574/non-constructive-proofs-vs-efficient-algorithms/126582#126582 Comment by Sam Hopkins Sam Hopkins 2013-04-12T02:46:21Z 2013-04-12T02:46:21Z Thank you, I think this is the most comprehensive and clear answer. http://mathoverflow.net/questions/126911/how-long-can-this-string-of-digits-be-extended Comment by Sam Hopkins Sam Hopkins 2013-04-08T22:43:23Z 2013-04-08T22:43:23Z What does &quot;N(b) &gt; n&quot; mean? http://mathoverflow.net/questions/126575/combinatorial-distance-between-simplicial-complexes Comment by Sam Hopkins Sam Hopkins 2013-04-05T03:23:10Z 2013-04-05T03:23:10Z What about the cardinality of the symmetric difference between the complexes viewed as abstract simplicial complexes? http://mathoverflow.net/questions/124443/group-of-a-graph-vs-graph-of-a-group Comment by Sam Hopkins Sam Hopkins 2013-03-13T18:56:28Z 2013-03-13T18:56:28Z Choosing a sink vertex, there is the sandpile group associated to a graph. http://mathoverflow.net/questions/124050/to-find-a-function-with-a-property Comment by Sam Hopkins Sam Hopkins 2013-03-09T06:30:11Z 2013-03-09T06:30:11Z Whoops, I understand now that the analytic sense of automorphism (holomorphic bijection) is meant. http://mathoverflow.net/questions/117151/does-this-poset-have-a-unique-minimal-element/118925#118925 Comment by Sam Hopkins Sam Hopkins 2013-03-09T04:51:58Z 2013-03-09T04:51:58Z Their paper is now on the arxiv: <a href="http://arxiv.org/abs/1303.1551" rel="nofollow">arxiv.org/abs/1303.1551</a> http://mathoverflow.net/questions/123679/cardinality-of-irrational-non-transcendental-numbers Comment by Sam Hopkins Sam Hopkins 2013-03-05T23:09:51Z 2013-03-05T23:09:51Z Of course the algebraic numbers (of which irrational non-transcendental numbers are a subset) are countable. This is known since Cantor. http://mathoverflow.net/questions/123084/quantum-algorithm-for-gcd Comment by Sam Hopkins Sam Hopkins 2013-02-27T09:45:59Z 2013-02-27T09:45:59Z Is parallelism believed to speed up a quantum computer? http://mathoverflow.net/questions/83552/what-is-the-sandpile-torsor Comment by Sam Hopkins Sam Hopkins 2013-02-18T10:13:49Z 2013-02-18T10:13:49Z 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: <a href="http://arxiv.org/abs/1112.5421" rel="nofollow">arxiv.org/abs/1112.5421</a>, Dave Perkinson and I define &quot;quasi-superstable&quot; divisors of $G$ without distinguishing a sink and show how they encode all the superstable elements with respect to any sink of $G$.