Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Authors:Amin Coja-Oghlan; Oliver Gebhard, Max Hahn-Klimroth, Philipp Loick Pages: 811 - 848 Abstract: In the group testing problem the aim is to identify a small set of k ⁓ nθ infected individuals out of a population size n, 0 < θ < 1. We avail ourselves of a test procedure capable of testing groups of individuals, with the test returning a positive result if and only if at least one individual in the group is infected. The aim is to devise a test design with as few tests as possible so that the set of infected individuals can be identified correctly with high probability. We establish an explicit sharp information-theoretic/algorithmic phase transition minf for non-adaptive group testing, where all tests are conducted in parallel. Thus with more than minf tests the infected individuals can be identified in polynomial time with high probability, while learning the set of infected individuals is information-theoretically impossible with fewer tests. In addition, we develop an optimal adaptive scheme where the tests are conducted in two stages. PubDate: 2021-11-01T00:00:00.000Z DOI: 10.1017/S096354832100002X Issue No:Vol. 30, No. 6 (2021)

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Authors:Svante Janson Pages: 849 - 893 Abstract: We explore the tree limits recently defined by Elek and Tardos. In particular, we find tree limits for many classes of random trees. We give general theorems for three classes of conditional Galton–Watson trees and simply generated trees, for split trees and generalized split trees (as defined here), and for trees defined by a continuous-time branching process. These general results include, for example, random labelled trees, ordered trees, random recursive trees, preferential attachment trees, and binary search trees. PubDate: 2021-11-01T00:00:00.000Z DOI: 10.1017/S0963548321000055 Issue No:Vol. 30, No. 6 (2021)

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Authors:Nemanja Draganić; François Dross, Jacob Fox, António Girão, Frédéric Havet, Dániel Korándi, William Lochet, David Munhá Correia, Alex Scott, Benny Sudakov Pages: 894 - 898 Abstract: In this short note we prove that every tournament contains the k-th power of a directed path of linear length. This improves upon recent results of Yuster and of Girão. We also give a complete solution for this problem when k=2, showing that there is always a square of a directed path of length , which is best possible. PubDate: 2021-11-01T00:00:00.000Z DOI: 10.1017/S0963548321000067 Issue No:Vol. 30, No. 6 (2021)

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Authors:Sean Eberhard; Jeff Kahn, Bhargav Narayanan, Sophie Spirkl Pages: 899 - 904 Abstract: A family of vectors in [k]n is said to be intersecting if any two of its elements agree on at least one coordinate. We prove, for fixed k ≥ 3, that the size of any intersecting subfamily of [k]n invariant under a transitive group of symmetries is o(kn), which is in stark contrast to the case of the Boolean hypercube (where k = 2). Our main contribution addresses limitations of existing technology: while there are now methods, first appearing in work of Ellis and the third author, for using spectral machinery to tackle problems in extremal set theory involving symmetry, this machinery relies crucially on the interplay between up-sets, biased product measures, and threshold behaviour in the Boolean hypercube, features that are notably absent in the problem considered here. To circumvent these barriers, introducing ideas that seem of independent interest, we develop a variant of the sharp threshold machinery that applies at the level of products of posets. PubDate: 2021-11-01T00:00:00.000Z DOI: 10.1017/S0963548321000079 Issue No:Vol. 30, No. 6 (2021)

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Authors:Martin Dyer; Marc Heinrich, Mark Jerrum, Haiko Müller Pages: 905 - 921 Abstract: We present a polynomial-time Markov chain Monte Carlo algorithm for estimating the partition function of the antiferromagnetic Ising model on any line graph. The analysis of the algorithm exploits the ‘winding’ technology devised by McQuillan [CoRR abs/1301.2880 (2013)] and developed by Huang, Lu and Zhang [Proc. 27th Symp. on Disc. Algorithms (SODA16), 514–527]. We show that exact computation of the partition function is #P-hard, even for line graphs, indicating that an approximation algorithm is the best that can be expected. We also show that Glauber dynamics for the Ising model is rapidly mixing on line graphs, an example being the kagome lattice. PubDate: 2021-11-01T00:00:00.000Z DOI: 10.1017/S0963548321000080 Issue No:Vol. 30, No. 6 (2021)

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Authors:Ben Green; Aled Walker Pages: 922 - 929 Abstract: We prove that if $A \subseteq [X,\,2X]$ and $B \subseteq [Y,\,2Y]$ are sets of integers such that gcd (a, b) ⩾ D for at least δ|A||B| pairs (a, b) ε A × B then $|A||B|{ \ll _{\rm{\varepsilon }}}{\delta ^{ - 2 - \varepsilon }}XY/{D^2}$. This is a new result even when δ = 1. The proof uses ideas of Koukoulopoulos and Maynard and some additional combinatorial arguments. PubDate: 2021-11-01T00:00:00.000Z DOI: 10.1017/S0963548321000092 Issue No:Vol. 30, No. 6 (2021)

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Authors:Bodan Arsovski Pages: 930 - 941 Abstract: Extending a result by Alon, Linial, and Meshulam to abelian groups, we prove that if G is a finite abelian group of exponent m and S is a sequence of elements of G such that any subsequence of S consisting of at least $$|S| - m\ln |G|$$ elements generates G, then S is an additive basis of G . We also prove that the additive span of any l generating sets of G contains a coset of a subgroup of size at least $$|G{|^{1 - c{ \in ^l}}}$$ for certain c=c(m) and $$ \in = \in (m) < 1$$; we use the probabilistic method to give sharper values of c(m) and $$ \in (m)$$ in the case when G is a vector space; and we give new proofs of related known results. PubDate: 2021-11-01T00:00:00.000Z DOI: 10.1017/S0963548321000109 Issue No:Vol. 30, No. 6 (2021)

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Authors:Matija Bucić; Nemanja Draganić, Benny Sudakov Pages: 942 - 955 Abstract: The Turán number ex(n, H) of a graph H is the maximal number of edges in an H-free graph on n vertices. In 1983, Chung and Erdős asked which graphs H with e edges minimise ex(n, H). They resolved this question asymptotically for most of the range of e and asked to complete the picture. In this paper, we answer their question by resolving all remaining cases. Our result translates directly to the setting of universality, a well-studied notion of finding graphs which contain every graph belonging to a certain family. In this setting, we extend previous work done by Babai, Chung, Erdős, Graham and Spencer, and by Alon and Asodi. PubDate: 2021-11-01T00:00:00.000Z DOI: 10.1017/S0963548321000110 Issue No:Vol. 30, No. 6 (2021)

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Authors:Leonid Gurvits; Jonathan Leake Pages: 956 - 981 Abstract: The notion of the capacity of a polynomial was introduced by Gurvits around 2005, originally to give drastically simplified proofs of the van der Waerden lower bound for permanents of doubly stochastic matrices and Schrijver’s inequality for perfect matchings of regular bipartite graphs. Since this seminal work, the notion of capacity has been utilised to bound various combinatorial quantities and to give polynomial-time algorithms to approximate such quantities (e.g. the number of bases of a matroid). These types of results are often proven by giving bounds on how much a particular differential operator can change the capacity of a given polynomial. In this paper, we unify the theory surrounding such capacity-preserving operators by giving tight capacity preservation bounds for all nondegenerate real stability preservers. We then use this theory to give a new proof of a recent result of Csikvári, which settled Friedland’s lower matching conjecture. PubDate: 2021-11-01T00:00:00.000Z DOI: 10.1017/S0963548321000122 Issue No:Vol. 30, No. 6 (2021)

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Authors:István Tomon; Dmitriy Zakharov Pages: 982 - 987 Abstract: In this short note, we prove the following analog of the Kővári–Sós–Turán theorem for intersection graphs of boxes. If G is the intersection graph of n axis-parallel boxes in $${{\mathbb{R}}^d}$$ such that G contains no copy of Kt,t, then G has at most ctn( log n)2d+3 edges, where c = c(d)>0 only depends on d. Our proof is based on exploring connections between boxicity, separation dimension and poset dimension. Using this approach, we also show that a construction of Basit, Chernikov, Starchenko, Tao and Tran of K2,2-free incidence graphs of points and rectangles in the plane can be used to disprove a conjecture of Alon, Basavaraju, Chandran, Mathew and Rajendraprasad. We show that there exist graphs of separation dimension 4 having superlinear number of edges. PubDate: 2021-11-01T00:00:00.000Z DOI: 10.1017/S0963548321000171 Issue No:Vol. 30, No. 6 (2021)