Search

In this paper, we present a fractional version of Haemers’ bound on the Shannon capacity of a graph, which is originally due to Blasiak. This bound is a common strengthening of both Haemers’ bound and the fractional chromatic number of a graph. We show that this fractional version outperforms any bound on the Shannon capacity that could be attained through Haemers’ bound. We show also that this bound is multiplicative, unlike Haemers’ bound. [ABSTRACT FROM AUTHOR]

We show that, for each fixed k, an n-vertex graph not containing a cycle of length 2k has at most $80\sqrt{k\log k}\cdot n^{1+1/k}+O(n)$ edges. [ABSTRACT FROM AUTHOR]

In 1981 Beck and Fiala proved an upper bound for the discrepancy of a set system of degree d that is independent of the size of the ground set. In the intervening years the bound has been decreased from 2d − 2 to 2d − 4. We improve the bound to 2d − log*d. [ABSTRACT FROM AUTHOR]

An L-spherical code is a set of Euclidean unit vectors whose pairwise inner products belong to the set L. We show, for a fixed 0 < α; β < 1, that the size of any [-1; -β] ∪ {α}-spherical code is at most linear in the dimension. In particular, this bound applies to sets of lines such that every two are at a fixed angle to each another. [ABSTRACT FROM AUTHOR]

In 2008, Bukh, Matoušek, and Nivasch conjectured that for every n-point set S in ℝ and every k, 0 ≤ k ≤ d - 1, there exists a k-flat f in ℝd (a "centerflat") that lies at "depth" (k + 1)n/(k + d + 1) - O(1) in S, in the sense that every halfspace that contains f contains at least that many points of S. This claim is true and tight for k = 0 (this is Rado's centerpoint theorem), as well as for k = d - 1 (trivial). Bukh et al. showed the existence of a (d - 2)-flat at depth (d - 1)n/(2d - 1) - O(1) (the case k = d - 2). In this paper we concentrate on the case k = 1 (the case of "centerlines"), in which the conjectured value for the leading constant is 2/(d + 2). We prove that 2/(d + 2) is an upper bound for the leading constant. Specifically, we show that for every fixed d and every n there exists an n-point set in ℝd for which no line in ℝd lies at depth greater than 2n/(d + 2) + o(n). This point set is the "stretched grid"--a set which has been previously used by Bukh et al. for other related purposes. Hence, in particular, the conjecture is now settled for ℝ³. [ABSTRACT FROM AUTHOR]