Subjects -> MATHEMATICS (Total: 1118 journals)     - APPLIED MATHEMATICS (92 journals)    - GEOMETRY AND TOPOLOGY (23 journals)    - MATHEMATICS (819 journals)    - MATHEMATICS (GENERAL) (45 journals)    - NUMERICAL ANALYSIS (26 journals)    - PROBABILITIES AND MATH STATISTICS (113 journals) MATHEMATICS (819 journals)                  1 2 3 4 5 | Last

1 2 3 4 5 | Last

Similar Journals
 Combinatorics, Probability and ComputingJournal Prestige (SJR): 0.839 Citation Impact (citeScore): 1Number of Followers: 4      Hybrid journal (It can contain Open Access articles) ISSN (Print) 0963-5483 - ISSN (Online) 1469-2163 Published by Cambridge University Press  [400 journals]
• Optimal group testing

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)

• Tree limits and limits of random trees

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)

• Powers of paths in tournaments

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)

• On symmetric intersecting families of vectors

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)

• Polynomial-time approximation algorithms for the antiferromagnetic Ising
model on line graphs

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)

• Extremal problems for GCDs

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)

• Additive bases via Fourier analysis

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)

• Universal and unavoidable graphs

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)

• Counting matchings via capacity-preserving operators

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)

• Turán-type results for intersection graphs of boxes

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)

JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762