Search

We show that every convex code realizable by compact sets in the plane admits a realization consisting of polygons, and analogously every open convex code in the plane can be realized by interiors of polygons. We give factorial-type bounds on the number of vertices needed to form such realizations. Consequently we show that there is an algorithm to decide whether a convex code admits a closed or open realization in the plane. [ABSTRACT FROM AUTHOR]

Given two random finite sequences from [k ]n such that a prefix of the first sequence is a suffix of the second, we examine the length of their longest common subsequence (LCS). If is the length of the overlap, we prove that the expected length of an LCS is approximately max(Î, E[Ln]), where Ln is the length of an LCS between two independent random sequences. We also obtain tail bounds on this quantity. [ABSTRACT FROM AUTHOR]

We study how a single value of the shatter function of a set system restricts its asymptotic growth. Along the way, we refute a conjecture of Bondy and Ha jnal which generalizes Sauer's lemma. [ABSTRACT FROM AUTHOR]

Let a1....,an be a permutation of [n]. Two disjoint order-isomorphic subsequences are called twins. We show that every permutation of [n] contains twins of length Ω (n3/5) improving the trivial bound of Ω (n1/2). We also show that a random permutation contains twins of length Ω (n2/3), which is sharp. [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]

Given a set of t ≥ κ +2 words of length n over a κ-letter alphabet, it is proved that there exists a common subsequence among two of them of length at least n/κ + cn1-1/(t-k-2) for some c > 0 depending on κ and t. This is sharp up to the value of c. [ABSTRACT FROM AUTHOR]

We present a generalization of a version of the Kruskal--Katona theorem due to Lovász. A shadow of a d-tuple (S1,…, Sd) ∈ (X/r)d consists of d-tuples (S'1,…, S'd) ∈ (X/r--1) d obtained by removing one element from each of the Si. We show that if a family Ƒ ⊂ ( X/r)d has size |Ƒ| = (x/r)d for a real number x ≥ r, then the shadow of Ƒ has size at least (x/r-1)d. [ABSTRACT FROM AUTHOR]