In another physics paper published by Zecchina (Combinatorial and topological approach to the 3D Ising model), Zecchina was fully aware but did not bother to mention that the main result had previously been proved by a mathematician.
Abstract: We extend the planar Pfaffian formalism for the evaluation of the Ising partition function to lattices of high topological genus g. ... The expansion of the partition function is given in terms of 22g Pfaffians classified by the oriented homology cycles of the lattice, i.e. by its spin structures. ...
For instance, for the case of complete graphs with random weights we find that an extremely small depth D_N is sufficient for reaching costs which are close to optimal ones for the unbounded trees [e.g., for the complete graph with random weights we find that D_N ~ log log N is sufficient to reach asymptotically a cost close to the optimal one zeta(3) [11,12] of the minimum spanning tree which has depth Theta(N^{1/3}) [13] ].The result in brackets is due to Angel, Flaxman, and Wilson, from whom Zecchina learned the result. There is nothing in the PRL paper's data or analysis that brings up zeta(3). Riccardo seemed surprised last summer when Omer and I told him about the zeta(3) result, and even the earlier weaker version that depth log_2 log N was enough to get constant weight came across as a surprise to him. So it is strange to see this result stated in the PRL paper without attribution.
The paragraph in question continues
For finite D the results of the cavity approach can be compared with rigorous upper and lower bounds [14] making us conjecture that the cavity approach is exact, as it happens for random matchings [15].
[no mention that the upper and lower bounds match to within a factor of 1+o(1)] and later in the paper it reads
For complete graph with random weights we are able to provide an accurate estimate of the scaling exponents which for alpha=1 are compatible with rational exponents predicted by rigorous analysis [14]. Moreover, we observe a very rapid decrease of the minimum cost with D, compatible with N^{1/(2^D-1)}. This suggests that very few ``hops'' (log log N) are in- deed sufficient to reach optimal costs. From a qualitative point of view we observe a nontrivial dependence on N and alpha of the size of the Steiner set. The size itself turns out to be sublinear, with a rational exponent that depends on D.
Whoever wrote this seems to be conveying the impression that the math paper does only fixed depth bound D, and from this the PRL paper infers log log N critical depth. This is nonsense. We figured out this log log N thing, and not only that, we proved it, we guessed the zeta(3) thing, we proved that too, we did this in summer 2007, and Riccardo knew all about our work.
It was also strange to read about the Steiner trees on the complete graph, since last fall I explained to Riccardo and one of his visitors in detail exactly what happens with bounded depth Steiner trees (i.e. with alpha<1) with random edge weights on the complete graph.
Our work addresses two questions: by analyzing the distributional equations we provide the phase diagrams of the problem in the control parameters alpha and D, where alpha N is the number of terminals in a graph of N vertices and D is the allowed depth of the tree from a randomly chosen root. We compute quantities like the behavior of the minimum cost as a function of D for a given fraction alpha of terminals, or the number of Steiner nodes c N^s where both c and the exponent s depend on D and alpha. Such quantities are of extreme interest in that they are directly connected with the topology of the tree.
Most of the quantities in Table 1 are well outside the estimated error bars, some by as much as a factor of 9 times the stated uncertainty. (We know the exact values for all the powers and constant factors, though not the low-order corrections.)
We talked to Riccardo about the misattribution in the PRL paper, but every time we brought up the log log N threshold and zeta(3), he sidestepped the question and kept emphasizing and re-emphasizing the citations to our work on the rational exponents for fixed depth, which of course we already knew about since we read the PRL paper. I tried to tell him about the errors in Table 1, but every time I started to say anything about Table 1, he immediately interrupted me, and despite repeated attempts, I never succeeded in saying anything about the errors. But I can't believe he doesn't know about the errors, since for D=2 he gives 1.47+-0.03 for the constant factor and quotes our exact value of 1.5, but for D=3 he gives 1.75+-0.02, and there is absolutely no mention of our exact value of 1.93... . One hypothesis is that Riccardo thought these constant factors were interesting enough to estimate by Monte Carlo and publish in PRL, and interesting enough to plug D=2 into our exact formula, but not interesting enough to plug D=3 into our exact formula. The other hypothesis is that he did plug D=3 into our exact formula, but didn't report the result. I don't know what to make of the estimates for the additive corrections. Riccardo also said that no-one was going to read the PRL paper.