Discussion
- [1] Dana Ernst commented on Impartial achievement and avoidance games for generating finite groups RE: topics: #combinatorics #mathematics #arXiv (Jul. 4, 2014)
- [2] Christopher Hanusa commented on A $q$-Queens Problem. I. General Theory RE: topics: #combinatorics (Feb. 21, 2014)
-
Show discussion.
A q-Queens Problem
The first three parts in our series about counting nonattacking chess piece configurations are now available on the arXiv. It gives a first mathematical approach to answering the n-Queens Problem: "In how many ways can you place n queens on an n×n chessboard in such a way that no two are attacking each other?".
As is the case with many mathematical questions, we developed a theory that answers a more general question, in which the board can be an arbitrary convex polygon, the pieces can be any "rider" piece that has unbounded moves in specified directions, and the number of pieces q is fixed. This is why it is entitled A q-Queens Problem.
The introduction to the first part sets the stage for the entire series, so if you want to get a feel for the papers, you should read those two and a half pages. This project has taken over seven years; it is nice to see it coming together.
Part I: General Theory http://arxiv.org/abs/1303.1879
Part II: The Square Board http://arxiv.org/abs/1402.4880
Part III: Partial Queens http://arxiv.org/abs/1402.4886
Once I get some time (ha! ha!) I hope to write some blog posts that go more thoroughly into the mathematics that is related to Ehrhart's theory of lattice point counting.
#spnetwork #combinatorics http://arxiv.org/abs/1303.1879- Dana Ernst replies (Feb. 21, 2014): When I have time (ha! ha!) I hope to read these.
- [3] David Roberts commented on Graham's Number is Less Than 2^^^6 RE: topics: #combinatorics #RamseyTheory (Oct. 22, 2013)
-
Show discussion.
The title of this paper is misleading. The number most often referred to as 'Graham's number', sometimes denoted by g_64, was originally mentioned in a 1977 article by Martin Gardner in Scientific American. It arose as an upper bound on a particular problem from Ramsey theory, a subfield of combinatorics [1]. +John Baez has some history of this [2], most notably the fact that g_64 doesn't appear in the joint paper Graham eventually published with Rothschild, but the smaller bound F^7(12), where F(n) = 2↑...n...↑3 (see [3] for Knuth's up-arrow notation). The paper by Lavrov, Lee and Mackey establishes a much smaller upper bound on the Ramsey-theoretic problem, and it is the exact solution to this problem that they are calling 'Graham's number'. In fact the bound given in the title, 2↑↑↑6, is a simplification, and not the smallest bound arrived at in the paper, which is 2↑↑2↑↑2↑↑9 (despite the apparent increase in complexity, this number is much smaller than 2↑↑↑6). In terms of the function F of Graham and Rothschild, the LLM bound is between F(4) and F(5).
[1] http://en.wikipedia.org/wiki/Ramsey_theory
[2] https://plus.google.com/117663015413546257905/posts/KJTgfjkTZCQ
[3] http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation
#spnetwork arXiv:1304.6910 #RamseyTheory #combinatorics
http://arxiv.org/abs/1304.6910 - [4] Timothy Gowers commented on Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem RE: topics: #combinatorics #breakthrough #functionalanalysis (Jul. 1, 2013)
-
Show discussion.
The recent solution of the Kadison-Singer problem, due to Adam Marcus, Daniel Spielman and Nikhil Srivastava, has received a lot of publicity, and rightly so. I had a different plan for my second contribution to the Selected Papers Network, but I like the idea of writing about recent results, so here goes.
Before I start, let me give an important disclaimer: I have not read the paper. However, (i) I have talked to a very good mathematician who has read it carefully and says that it is correct, (ii) the purpose of this post is more to say a bit about the problem for people who don't know it than to give an authoritative review, and (iii) I very much hope that what I write will not be the only contribution to the SPN on this paper.
In fact, all I want to do is describe a beautiful problem that is known to be equivalent to the Kadison-Singer problem (which is a problem about \(C^*\)-algebras). Let \(v_1,\ldots,v_n\) be unit vectors in a Hilbert space, and suppose that for any coefficients \(a_1,\ldots,a_n\) we have the inequality \(\|\sum_{i=1}^n a_i v_i \|^2\leq C\sum_{i=1}^n |a_i|^2\). In other words, if you define a linear map from \(\ell_2^n\) to the Hilbert space by sending the standard basis vector \(e_i\) to the vector \(v_i\) for each \(i\), then the norm of that map is at most \(C^{1/2}\). Bourgain and Tzafriri proved that given that condition one can find a proportional-sized subset of the \(v_i\) such that an inequality holds in the reverse direction as well. That is, you can find a subset \(A\subset\{1,2,\ldots,n\}\) and a constant \(c>0\) such that \(|A|/n\) and \(c\) both depend on \(C\) only, and such that \(\|\sum_{i\in A} a_i v_i \|^2 \geq c\sum_{i\in A} |a_i|^2\) for any coefficients \(a_i\).
The proof of Bourgain and Tzafriri used a very interesting combination of tools and the result had several applications. However, it appeared that more ought to be true: one should be able to partition the set \(\{1,2,\ldots,n\}\) into a bounded number of pieces (in other words, a number depending on \(C\) only) \(A_1,\ldots,A_k\) such that the conclusion above holds for each \(A_i\). It is this statement that is (along with several other interesting reformulations) equivalent to the Kadison-Singer problem.
Actually, Marcus, Spielman and Srivastava attack a different equivalent statement, due to Weaver. It is stated as Conjecture 1.1 in their paper and is also a very appealing combinatorial statement.
The main tool they use, interlacing polynomials, looks destined to be a major addition to the toolbox of the mathematical community. In an earlier paper, the authors used it to give a surprisingly simple proof of the existence of Ramanujan graphs.
#spnetwork #combinatorics #functionalanalysis #breakthrough arXiv:1306.3969- Aleksandar Nikolov replies (Jul. 2, 2013): Dear Tim, there is a stronger version of Bourgain and Tzafriri's result and I am wondering if it is generalized in a similar way by Kadison-Singer.
Let's make the same assumptions on the \(v_i\) and let \(T\) be the linear operator that sends \(e_i\) to \(v_i\). Additionally we are given vectors \((u_i)_1^m\), all in \(C^n\), s.t. \(\sum u_i u_i^* = I\) where \(I\) is the identity in \(C^n\). Then there exists a set \(A \subseteq [m]\) (as large as in B-T) for which \(\|\sum_{i \in A} a_iTu_i\|^2 \geq c\sum_{i \in A} a_i^2\) for any sequence \((a_i)\). This version, together with John's theorem, was used by Roman Vershynin to prove some results in convex geometry (e.g. the contact points of a convex set in John's position and its John ellipsoid contain a well-conditioned basis that spans a subspace of dimension \(\Omega(n)\)).
I am wondering if there is a Kadison-Singer version of this stronger theorem.- Timothy Gowers replies (Jul. 3, 2013): I think the answer is yes, but that shouldn't be taken as an absolute confirmation.
- Aleksandar Nikolov replies (Jul. 2, 2013): Dear Tim, there is a stronger version of Bourgain and Tzafriri's result and I am wondering if it is generalized in a similar way by Kadison-Singer.
- [5] Timothy Gowers commented on An Infinite Sidon Sequence RE: topics: #combinatorics #interestingpaper (Jun. 18, 2013)
-
Show discussion.
This is a short appreciation of the paper, "An infinite Sidon sequence," by Imre Ruzsa, written for the Selected Papers Network.
In combinatorics, a Sidon set is a subset A of the positive integers such that no integer can be written in more than one way as a difference of elements of A. An old problem is to determine the maximum growth rate of the counting function \(f(n)=|A\cap\{1,2,...,n\}|\) of such a set. A greedy algorithm (repeatedly pick the smallest element you can add to the set without violating the constraint) yields a set where the counting function grows like the cube root of n. On the other hand, a fairly simple algebraic construction shows that for any fixed n you can find a subset of \(\{1,2,...,n\}\) of size proportional to the square root of n with no repeated differences. This suggests that it might be possible to obtain a growth rate closer to the square root of n, but it certainly doesn't prove it, since there is no obvious way of building an infinite example out of the finite ones.
For a long time there was no improvement on the cube root lower bound or the square root upper bound. Then Ajtai, Komlos and Szemeredi found a fairly hard argument that yielded a logarithmic improvement to the lower bound, which again was the record for a long time. It therefore came as a big surprise when Imre Ruzsa, in the paper in question, improved the bound to a better power: specifically, he obtains the power \(\sqrt{2}-1\), which is strictly between 1/3 and 1/2.
The paper is one of my favourite in mathematics, and the reason for that has less to do with the fact that it made unexpectedly large progress on a seemingly very hard problem, and more to do with the fact that the proof itself is extremely bold and unexpected. I think of it as the kind of idea that any normal mathematician would either not have or would dismiss without seriously investigating it. It starts with the observation that, by the fundamental theorem of arithmetic, the logarithms of the primes form a Sidon set of reals. One might have thought that since a random set of countably many reals (picked independently using any continuous probability distribution) also forms a Sidon set with probability 1, this observation couldn't possibly be of any use. But it is.
I think the best way of conveying the extraordinary flavour of the paper at this point is simply to quote the first two paragraphs of the second section (which is entitled "The construction"). The words "slightly unusual" below are a wonderful understatement.
"Our starting point is the observation that the numbers log p, for p prime, form a Sidon set of reals. Our plan is to take the binary development of these numbers and rearrange the digits to form a Sidon set of integers. If the developments were finite (and not too long), this could be done easily. Since the developments are infinite, we have to round them off. We will show that the resulting sequence still almost has the Sidon property, which will enable us to extract a large Sidon subset from it.
"Our construction will also be random, in a slightly unusual way. Rather than select individual elements randomly, we choose a random parameter \(\alpha\) in the interval [1,2] at the start which determines a set, and we show that for almost all choices of \(\alpha\) in this interval the set obtained will have the required properties."
I'll finish with two remarks. The first is that the logarithms of the primes do have a significant advantage over a random countable subset of the reals, which is that if p, q, r, s are primes with pq not equal to rs, then \(|pq-rs|\geq 1\). The second is that any mathematician with the courage to start Ruzsa's argument will fairly soon reach a point where it breaks down, which looks like a sign that it is not going to work. The "slightly unusual" random construction is an extremely ingenious way of salvaging it.
The construction in this paper is so clever that it is not clear that any techniques can be gleaned from it that are of use outside the rather narrow area of finding dense Sidon sets. However, if you are interested in combinatorics and would like a piece of mathematics to enjoy for its own sake, it is difficult to do better than this one.
#spnetwork #combinatorics #interestingpaper doi:10.1006/jnth.1997.2192- Kevin O'Bryant replies (Jun. 18, 2013): It's worth noting that Cilleruelo has recently gotten \(\sqrt{2}-1\) using a non-random construction, by cleverly nesting finite fields. How does the spnetwork handle comments and self-edits?
- Willie Wong replies (Jun. 18, 2013): +Kevin O'Bryant They will eventually show up, nested properly. You can keep an eye on it here: https://selectedpapers.net/shortDOI/dbm9nb . The Cilleruelo construction that is mentioned seems to be the preprint "Infinite Sidon sequences" available here: http://www.uam.es/personal_pdi/ciencias/cillerue/articulos.html
We study two impartial games introduced by Anderson and Harary and further developed by Barnes. Both games are played by two players who alternately select previously unselected elements of a finite group. The first player who builds a generating set from the jointly selected elements wins the first game. The first player who cannot select an element without building a generating set loses the second game. After the development of some general results, we determine the nim-numbers of these games for abelian and dihedral groups. We also present some conjectures based on computer calculations. Our main computational and theoretical tool is the structure diagram of a game, which is a type of identification digraph of the game digraph that is compatible with the nim-numbers of the positions. Structure diagrams also provide simple yet intuitive visualizations of these games that capture the complexity of the positions.
I'm really happy with how this paper turned out.
#mathematics #combinatorics #arXiv #spnetwork arXiv:1407.0784