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)
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)
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)
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)
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)
Hybrid journal (It can contain Open Access articles)
[372 journals]
$$(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.
