JournalTOCs

Combinatorics, Probability and Computing
Journal Prestige (SJR): 1.013
Citation Impact (citeScore): 35
Number of Followers: 4

Hybrid journal (It can contain Open Access articles)
ISSN (Print) 0963-5483 - ISSN (Online) 1469-2163
Published by Cambridge University Press

[367 journals]

Ramsey Goodness of Bounded Degree Trees
- Authors: IGOR BALLA; ALEXEY POKROVSKIY, BENNY SUDAKOV
  Pages: 289 - 309
  Abstract: Given a pair of graphs G and H, the Ramsey number R(G, H) is the smallest N such that every red–blue colouring of the edges of the complete graph KN contains a red copy of G or a blue copy of H. If a graph G is connected, it is well known and easy to show that R(G, H) ≥ (|G|−1)(χ(H)−1)+σ(H), where χ(H) is the chromatic number of H and σ(H) is the size of the smallest colour class in a χ(H)-colouring of H. A graph G is called H-good if R(G, H) = (|G|−1)(χ(H)−1)+σ(H). The notion of Ramsey goodness was introduced by Burr and Erdős in 1983 and has been extensively studied since then.In this paper we show that if n≥ Ω(|H| log4 |H|) then every n-vertex bounded degree tree T is H-good. The dependency between n and |H| is tight up to log factors. This substantially improves a result of Erdős, Faudree, Rousseau, and Schelp from 1985, who proved that n-vertex bounded degree trees are H-good when n ≥ Ω(|H|4).
  PubDate: 2018-05-01T00:00:00.000Z
  DOI: 10.1017/S0963548317000554
  Issue No: Vol. 27, No. 3 (2018)
On Zeros of a Polynomial in a Finite Grid
- Authors: ANURAG BISHNOI; PETE L. CLARK, ADITYA POTUKUCHI, JOHN R. SCHMITT
  Pages: 310 - 333
  Abstract: A 1993 result of Alon and Füredi gives a sharp upper bound on the number of zeros of a multivariate polynomial over an integral domain in a finite grid, in terms of the degree of the polynomial. This result was recently generalized to polynomials over an arbitrary commutative ring, assuming a certain ‘Condition (D)’ on the grid which holds vacuously when the ring is a domain. In the first half of this paper we give a further generalized Alon–Füredi theorem which provides a sharp upper bound when the degrees of the polynomial in each variable are also taken into account. This yields in particular a new proof of Alon–Füredi. We then discuss the relationship between Alon–Füredi and results of DeMillo–Lipton, Schwartz and Zippel. A direct coding theoretic interpretation of Alon–Füredi theorem and its generalization in terms of Reed–Muller-type affine variety codes is shown, which gives us the minimum Hamming distance of these codes. Then we apply the Alon–Füredi theorem to quickly recover – and sometimes strengthen – old and new results in finite geometry, including the Jamison–Brouwer–Schrijver bound on affine blocking sets. We end with a discussion of multiplicity enhancements.
  PubDate: 2018-05-01T00:00:00.000Z
  DOI: 10.1017/S0963548317000566
  Issue No: Vol. 27, No. 3 (2018)
On Quantitative Noise Stability and Influences for Discrete and Continuous
Models
- Authors: RAPHAËL BOUYRIE
  Pages: 334 - 357
  Abstract: Keller and Kindler recently established a quantitative version of the famous Benjamini–Kalai–Schramm theorem on the noise sensitivity of Boolean functions. Their result was extended to the continuous Gaussian setting by Keller, Mossel and Sen by means of a Central Limit Theorem argument. In this work we present a unified approach to these results, in both discrete and continuous settings. The proof relies on semigroup decompositions together with a suitable cut-off argument, allowing for the efficient use of the classical hypercontractivity tool behind these results. It extends to further models of interest such as families of log-concave measures and Cayley and Schreier graphs. In particular we obtain a quantitative version of the Benjamini–Kalai–Schramm theorem for the slices of the Boolean cube.
  PubDate: 2018-05-01T00:00:00.000Z
  DOI: 10.1017/S0963548318000044
  Issue No: Vol. 27, No. 3 (2018)
Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey
Numbers
- Authors: CLAYTON COLLIER-CARTAINO; NATHAN GRABER, TAO JIANG
  Pages: 358 - 386
  Abstract: An r-uniform hypergraph is called an r-graph. A hypergraph is linear if every two edges intersect in at most one vertex. Given a linear r-graph H and a positive integer n, the linear Turán number exL(n,H) is the maximum number of edges in a linear r-graph G that does not contain H as a subgraph. For each ℓ ≥ 3, let Crℓ denote the r-uniform linear cycle of length ℓ, which is an r-graph with edges e1, . . ., eℓ such that, for all i ∈ [ℓ−1], |ei ∩ ei+1|=1, |eℓ ∩ e1|=1 and ei ∩ ej = ∅ for all other pairs {i,j}, i ≠ j. For all r ≥ 3 and ℓ ≥ 3, we show that there exists a positive constant c = cr,ℓ, depending only r and ℓ, such that exL(n,Crℓ) ≤ cn1+1/⌊ℓ/2⌋. This answers a question of Kostochka, Mubayi and Verstraëte [30]. For even ℓ, our result extends the result of Bondy and Simonovits [7] on the Turán numbers of even cycles to linear hypergraphs.Using our results on linear Turán numbers, we also obtain bounds on the cycle-complete hypergraph Ramsey numbers. We show that there are positive constants a = am,r and b = bm,r, depending only on m and r, such that \begin{equation}R(C^r_{2m}, K^r_t)\leq a \Bigl(\frac{t}{\ln t}\Bigr)^{{m}/{(m-1)}}\quad\text{and}\quadR(C^r_{2m+1}, K^r_t)\leq b t^{{m}/{(m-1)}}.\end{equation}
  PubDate: 2018-05-01T00:00:00.000Z
  DOI: 10.1017/S0963548317000530
  Issue No: Vol. 27, No. 3 (2018)
A Sharp Dirac–Erdős Type Bound for Large Graphs
- Authors: H. A. KIERSTEAD; A. V. KOSTOCHKA, A. McCONVEY
  Pages: 387 - 397
  Abstract: Let k ⩾ 3 be an integer, hk(G) be the number of vertices of degree at least 2k in a graph G, and ℓk(G) be the number of vertices of degree at most 2k − 2 in G. Dirac and Erdős proved in 1963 that if hk(G) − ℓk(G) ⩾ k2 + 2k − 4, then G contains k vertex-disjoint cycles. For each k ⩾ 2, they also showed an infinite sequence of graphs Gk(n) with hk(Gk(n)) − ℓk(Gk(n)) = 2k − 1 such that Gk(n) does not have k disjoint cycles. Recently, the authors proved that, for k ⩾ 2, a bound of 3k is sufficient to guarantee the existence of k disjoint cycles, and presented for every k a graph G0(k) with hk(G0(k)) − ℓk(G0(k)) = 3k − 1 and no k disjoint cycles. The goal of this paper is to refine and sharpen this result. We show that the Dirac–Erdős construction is optimal in the sense that for every k ⩾ 2, there are only finitely many graphs G with hk(G) − ℓk(G) ⩾ 2k but no k disjoint cycles. In particular, every graph G with |V(G)| ⩾ 19k and hk(G) − ℓk(G) ⩾ 2k contains k disjoint cycles.
  PubDate: 2018-05-01T00:00:00.000Z
  DOI: 10.1017/S0963548318000020
  Issue No: Vol. 27, No. 3 (2018)
Density of Real Zeros of the Tutte Polynomial
- Authors: SEONGMIN OK; THOMAS J. PERRETT
  Pages: 398 - 410
  Abstract: The Tutte polynomial of a graph is a two-variable polynomial whose zeros and evaluations encode many interesting properties of the graph. In this article we investigate the real zeros of the Tutte polynomials of graphs, and show that they form a dense subset of certain regions of the plane. This is the first density result for the real zeros of the Tutte polynomial in a region of positive volume. Our result almost confirms a conjecture of Jackson and Sokal except for one region which is related to an open problem on flow polynomials.
  PubDate: 2018-05-01T00:00:00.000Z
  DOI: 10.1017/S0963548318000019
  Issue No: Vol. 27, No. 3 (2018)
On Lipschitz Bijections Between Boolean Functions
- Authors: SHRAVAS RAO; IGOR SHINKAR
  Pages: 411 - 426
  Abstract: Given two functions f,g : {0,1}n → {0,1}, a mapping ψ : {0,1}n → {0,1}n is said to be a mapping from f to g if it is a bijection and f(z) = g(ψ(z)) for every z ∈ {0,1}n. In this paper we study Lipschitz mappings between Boolean functions.Our first result gives a construction of a C-Lipschitz mapping from the Majority function to the Dictator function for some universal constant C. On the other hand, there is no n/2-Lipschitz mapping in the other direction, namely from the Dictator function to the Majority function. This answers an open problem posed by Daniel Varga in the paper of Benjamini, Cohen and Shinkar (FOCS 2014 [1]).We also show a mapping from Dictator to XOR that is 3-local, 2-Lipschitz, and its inverse is O(log(n))-Lipschitz, where by L-local mapping we mean that each output bit of the mapping depends on at most L input bits.Next, we consider the problem of finding functions such that any mapping between them must have large average stretch, where the average stretch of a mapping φ is defined as $${\sf avgstretch}(\phi) = {\mathbb E}_{x,i}[{\sf dist}(\phi(x),\phi(x+e_i)].$$ We show that any mapping φ from XOR to Majority must satisfy avgStretch(φ) ≥ c $\sqrt{n}$ for some absolute constant c > 0. In some sense, this gives a ‘function analogue’ to the question of Benjamini, Cohen and Shinkar (FOCS 2014 [1]), who asked whether there exists a set A ⊆ {0,1}n of density 0.5 such that any bijection from {0,1}n−1 to A has large average stretch.Finally, we show that for a random balanced function f: {0,1}n → {0,1}n, with high probability there is a mapping φ from Dictator to f such that both φ and φ−1 have constant average stretch. In particular, this implies that one cannot obtain lower bounds on average stretch by taking uniformly random functions.
  PubDate: 2018-05-01T00:00:00.000Z
  DOI: 10.1017/S0963548317000578
  Issue No: Vol. 27, No. 3 (2018)
Robust Tverberg and Colourful Carathéodory Results via Random Choice
- Authors: PABLO SOBERÓN
  Pages: 427 - 440
  Abstract: We use the probabilistic method to obtain versions of the colourful Carathéodory theorem and Tverberg's theorem with tolerance.In particular, we give bounds for the smallest integer N = N(t,d,r) such that for any N points in ℝd, there is a partition of them into r parts for which the following condition holds: after removing any t points from the set, the convex hulls of what is left in each part intersect.We prove a bound N = rt + O( $\sqrt{t}$ ) for fixed r,d which is polynomial in each parameters. Our bounds extend to colourful versions of Tverberg's theorem, as well as Reay-type variations of this theorem.
  PubDate: 2018-05-01T00:00:00.000Z
  DOI: 10.1017/S0963548317000591
  Issue No: Vol. 27, No. 3 (2018)