User sam hopkins - MathOverflow

Is there a characterization of hyperplane arrangement intersection posets?

2013-01-24T03:21:01Z

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})$.

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:

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.

Is there a known characterization of hyperplane arrangement intersection posets?

Non-constructive proofs vs. efficient algorithms

2012-12-30T00:25:39Z

My question concerns what is meant by "nonconstructive", and whether it has ever been defined in terms of computational complexity.

The wikipedia article on constructive proof 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 the probabilistic method 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.

Consider Erdős's celebrated proof of the lower bound of the Ramsey number. This proof shows that as long as $\binom{n}{r} < 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 does 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.

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.

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.

What is the graphical version of the circle parking story?

2013-03-14T02:51:39Z

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.

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.

Now it is pretty clear how to translate this to graphs. For background on the Abelian sandpile model, see http://arxiv.org/abs/1112.6163. 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:

parking preference of $v_i$ ---> number of grains of sand on $v_i$
order that cars approach spaces ---> firing preference order
order that cars park ---> order that vertices fire
all the cars park ---> all the vertices fire

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}$.

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 algebraic. 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: http://arxiv.org/abs/1112.5421.

Is there a n/2 version of the Erdős-Hanani conjecture?

2013-02-16T01:02:33Z

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.

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

$\kappa_n = \binom{n}{t} / \binom{k}{t}(1 + o(1))$.

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.

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

$\kappa_n = \frac{1}{\lfloor n / 2 \rfloor} \binom{n}{\lfloor n/2 \rfloor}(1 + o(1))$?

Background

The EH conjecture lead to the study of what is called "packing in a hypergraph." See http://en.wikipedia.org/wiki/Packing_in_a_hypergraph. 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 as long as their edge sizes are bounded! Unfortunately the $n/2$ version of EH involves hypergraphs of unbounded edge size and the existing methods appear useless.

Some ideas

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.

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: http://mathoverflow.net/questions/101886/size-of-union-of-a-set-of-subsets-and-its-permutations. That question is interesting in its own right, but this EH conjecture is really why I wanted an answer.

Answer by Sam Hopkins for Elementary applications of linear algebra over finite fields

2013-01-14T17:39:55Z

You can use linear algebra over $\mathbb{F}_2$ to solve the game "Lights Out": http://en.wikipedia.org/wiki/Lights_Out_%28game%29

Answer by Sam Hopkins for New grand projects in contemporary math

2012-12-31T16:23:56Z

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.

Number of forests of size $i$ and the Tutte polynomial

2012-11-03T00:59:16Z

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 here.

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)$?

Hypergraph coloring problem motivated by legal billards racks

2012-08-31T03:06:25Z

Motivation

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.

Problem

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?

For instance, with $n=4$, a legal coloring is,

     A
    B A
   A B B
  B B A B

but an illegal coloring is,

     A
    B A
   A A B
  B A B A

because it contains a triangle with three $A$s.

If $\kappa(n)$ denotes the number of legal colorings for a grid with base $n$, what is $\kappa(n)$?

Size of union of a set of subsets and its permutations

2012-07-10T20:20:54Z

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|$.

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)|$?

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}$.

The question is, can we always (ever?) do much better than this average?

Comment by Sam Hopkins

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.

Comment by Sam Hopkins

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)?

Comment by Sam Hopkins

2013-05-04T05:01:29Z

Does the matroid property easily generalize to $n \times n$-Sudoku?

Comment by Sam Hopkins

2013-04-27T18:29:43Z

Is it obvious that the limit exists?

Comment by Sam Hopkins

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 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.

Comment by Sam Hopkins

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?

Comment by Sam Hopkins

2013-04-12T02:46:21Z

Thank you, I think this is the most comprehensive and clear answer.

Comment by Sam Hopkins

2013-04-08T22:43:23Z

What does "N(b) > n" mean?

Comment by Sam Hopkins

2013-04-05T03:23:10Z

What about the cardinality of the symmetric difference between the complexes viewed as abstract simplicial complexes?

Comment by Sam Hopkins

2013-03-13T18:56:28Z

Choosing a sink vertex, there is the sandpile group associated to a graph.

Comment by Sam Hopkins

2013-03-09T06:30:11Z

Whoops, I understand now that the analytic sense of automorphism (holomorphic bijection) is meant.

Comment by Sam Hopkins

2013-03-09T04:51:58Z

Their paper is now on the arxiv: arxiv.org/abs/1303.1551

Comment by Sam Hopkins

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.

Comment by Sam Hopkins

2013-02-27T09:45:59Z

Is parallelism believed to speed up a quantum computer?

Comment by Sam Hopkins

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: 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$.