for Journals by Title or ISSN for Articles by Keywords help

Publisher: Cambridge University Press   (Total: 373 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  [373 journals]
• Ewens Sampling and Invariable Generation
• Authors: GERANDY BRITO; CHRISTOPHER FOWLER, MATTHEW JUNGE, AVI LEVY
Pages: 853 - 891
Abstract: We study the number of random permutations needed to invariably generate the symmetric group Sn when the distribution of cycle counts has the strong α-logarithmic property. The canonical example is the Ewens sampling formula, for which the special case α = 1 corresponds to uniformly random permutations.For strong α-logarithmic measures and almost every α, we show that precisely ⌈(1−αlog2)−1⌉ permutations are needed to invariably generate Sn with asymptotically positive probability. A corollary is that for many other probability measures on Sn no fixed number of permutations will invariably generate Sn with positive probability. Along the way we generalize classic theorems of Erdős, Tehran, Pyber, Łuczak and Bovey to permutations obtained from the Ewens sampling formula.
PubDate: 2018-11-01T00:00:00.000Z
DOI: 10.1017/S096354831800007X
Issue No: Vol. 27, No. 6 (2018)

• Kn+with+Few+Colours&rft.title=Combinatorics,+Probability+and+Computing&rft.issn=0963-5483&rft.date=2018&rft.volume=27&rft.spage=892&rft.epage=912&rft.aulast=CAMERON&rft.aufirst=ALEX&rft.au=ALEX+CAMERON&rft.au=EMILY+HEATH&rft_id=info:doi/10.1017/S0963548318000172">A (5,5)-Colouring of Kn with Few Colours
• Authors: ALEX CAMERON; EMILY HEATH
Pages: 892 - 912
Abstract: For fixed integers p and q, let f(n,p,q) denote the minimum number of colours needed to colour all of the edges of the complete graph Kn such that no clique of p vertices spans fewer than q distinct colours. Any edge-colouring with this property is known as a (p,q)-colouring. We construct an explicit (5,5)-colouring that shows that f(n,5,5) ≤ n1/3 + o(1) as n → ∞. This improves upon the best known probabilistic upper bound of O(n1/2) given by Erdős and Gyárfás, and comes close to matching the best known lower bound Ω(n1/3).
PubDate: 2018-11-01T00:00:00.000Z
DOI: 10.1017/S0963548318000172
Issue No: Vol. 27, No. 6 (2018)

• A Tutte Polynomial for Maps
• Authors: ANDREW GOODALL; THOMAS KRAJEWSKI, GUUS REGTS, LLUÍS VENA
Pages: 913 - 945
Abstract: We follow the example of Tutte in his construction of the dichromate of a graph (i.e. the Tutte polynomial) as a unification of the chromatic polynomial and the flow polynomial in order to construct a new polynomial invariant of maps (graphs embedded in orientable surfaces). We call this the surface Tutte polynomial. The surface Tutte polynomial of a map contains the Las Vergnas polynomial, the Bollobás–Riordan polynomial and the Krushkal polynomial as specializations. By construction, the surface Tutte polynomial includes among its evaluations the number of local tensions and local flows taking values in any given finite group. Other evaluations include the number of quasi-forests.
PubDate: 2018-11-01T00:00:00.000Z
DOI: 10.1017/S0963548318000081
Issue No: Vol. 27, No. 6 (2018)

• Volumes in the Uniform Infinite Planar Triangulation: From Skeletons to
Generating Functions
• Authors: LAURENT MÉNARD
Pages: 946 - 973
Abstract: We develop a method to compute the generating function of the number of vertices inside certain regions of the Uniform Infinite Planar Triangulation (UIPT). The computations are mostly combinatorial in flavour and the main tool is the decomposition of the UIPT into layers, called the skeleton decomposition, introduced by Krikun [20]. In particular, we get explicit formulas for the generating functions of the number of vertices inside hulls (or completed metric balls) centred around the root, and the number of vertices inside geodesic slices of these hulls. We also recover known results about the scaling limit of the volume of hulls previously obtained by Curien and Le Gall by studying the peeling process of the UIPT in [17].
PubDate: 2018-11-01T00:00:00.000Z
DOI: 10.1017/S0963548318000093
Issue No: Vol. 27, No. 6 (2018)

• Multicolour Sunflowers
• Authors: DHRUV MUBAYI; LUJIA WANG
Pages: 974 - 987
Abstract: A sunflower is a collection of distinct sets such that the intersection of any two of them is the same as the common intersection C of all of them, and |C| is smaller than each of the sets. A longstanding conjecture due to Erdős and Szemerédi (solved recently in [7, 9]; see also [22]) was that the maximum size of a family of subsets of [n] that contains no sunflower of fixed size k > 2 is exponentially smaller than 2n as n → ∞. We consider the problems of determining the maximum sum and product of k families of subsets of [n] that contain no sunflower of size k with one set from each family. For the sum, we prove that the maximum is $$(k-1)2^n+1+\sum_{s=0}^{k-2}\binom{n}{s}$$ for all n ⩾ k ⩾ 3, and for the k = 3 case of the product, we prove that the maximum is $$\biggl(\ffrac{1}{8}+o(1)\biggr)2^{3n}.$$ We conjecture that for all fixed k ⩾ 3, the maximum product is (1/8+o(1))2kn.
PubDate: 2018-11-01T00:00:00.000Z
DOI: 10.1017/S0963548318000160
Issue No: Vol. 27, No. 6 (2018)

• Density of Chromatic Roots in Minor-Closed Graph Families
• Authors: THOMAS J. PERRETT; CARSTEN THOMASSEN
Pages: 988 - 998
Abstract: We prove that the roots of the chromatic polynomials of planar graphs are dense in the interval between 32/27 and 4, except possibly in a small interval around τ + 2 where τ is the golden ratio. This interval arises due to a classical result of Tutte, which states that the chromatic polynomial of every planar graph takes a positive value at τ + 2. Our results lead us to conjecture that τ + 2 is the only such number less than 4.
PubDate: 2018-11-01T00:00:00.000Z
DOI: 10.1017/S0963548318000184
Issue No: Vol. 27, No. 6 (2018)

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
Fax: +00 44 (0)131 4513327

Home (Search)
Subjects A-Z
Publishers A-Z
Customise
APIs