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]

We show that, for every set of |$n$| points in the |$d$| -dimensional unit cube, there is an empty axis-parallel box of volume at least |$\Omega (d/n)$| as |$n\to \infty $| and |$d$| is fixed. In the opposite direction, we give a construction without an empty axis-parallel box of volume |$O(d^2\log d/n)$|⁠. These improve on the previous best bounds of |$\Omega (\log d/n)$| and |$O(2^{7d}/n)$|⁠ , respectively. [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]

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 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]

We consider list decoding in the zero-rate regime for two cases—the binary alphabet and the spherical codes in Euclidean space. Specifically, we study the maximal $\tau \in [{0,1}]$ for which there exists an arrangement of $M$ balls of relative Hamming radius $\tau $ in the binary hypercube (of arbitrary dimension) with the property that no point of the latter is covered by $L$ or more of them. As $M\to \infty $ the maximal $\tau $ decreases to a well-known critical value $\tau _{L}$. In this paper, we prove several results on the rate of this convergence. For the binary case, we show that the rate is $\Theta (M^{-1})$ when $L$ is even, thus extending the classical results of Plotkin and Levenshtein for $L=2$. For $L=3$ , the rate is shown to be $\Theta (M^{-({2}/{3})})$. For the similar question about spherical codes, we prove the rate is $\Omega (M^{-1})$ and $O(M^{-({2L}/{L^{2}-L+2})})$. [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]

Given a family H of graphs, the extremal number ex(n;H) is the largest m for which there exists a graph with n vertices and m edges containing no graph from the family H as a subgraph. We show that for every rational number r between 1 and 2, there is a family Hr of graphs such that ex(n;Hr) Θ(nr). This solves a longstanding problem in extremal graph theory. [ABSTRACT FROM AUTHOR]

Let P s be the s -dimensional complex projective space, and let X , Y be two non-empty open subsets of P s in the Zariski topology. A hypersurface H in P s × P s induces a bipartite graph G as follows: the partite sets of G are X and Y , and the edge set is defined by u ¯ ∼ v ¯ if and only if ( u ¯ , v ¯ ) ∈ H . Motivated by the Turán problem for bipartite graphs, we say that H ∩ ( X × Y ) is ( s , t ) -grid-free provided that G contains no complete bipartite subgraph that has s vertices in X and t vertices in Y . We conjecture that every ( s , t ) -grid-free hypersurface is equivalent, in a suitable sense, to a hypersurface whose degree in y ¯ is bounded by a constant d = d ( s , t ) , and we discuss possible notions of the equivalence. We establish the result that if H ∩ ( X × P 2 ) is ( 2 , 2 ) -grid-free, then there exists F ∈ C [ x ¯ , y ¯ ] of degree ≤ 2 in y ¯ such that H ∩ ( X × P 2 ) = { F = 0 } ∩ ( X × P 2 ) . Finally, we transfer the result to algebraically closed fields of large characteristic. [ABSTRACT FROM AUTHOR]

We consider codes over fixed alphabets against worst case symbol deletions. For any fixed k \ge 2 , we construct a family of codes over alphabet of size k with positive rate, which allow efficient recovery from a worst case deletion fraction approaching 1-(2/(k+\sqrt k)) . In particular, for binary codes, we are able to recover a fraction of deletions approaching 1/(\sqrt 2 +1)=\sqrt 2-1 \approx 0.414 . Previously, even non-constructively, the largest deletion fraction known to be correctable with positive rate was 1-\Theta (1/\sqrt k) , and around 0.17 for the binary case. Our result pins down the largest fraction of correctable deletions for $k$ -ary codes as 1-\Theta (1/k)$ , since 1-1/k$ is an upper bound even for the simpler model of erasures where the locations of the missing symbols are known. Closing the gap between and 1/2 for the limit of worst case deletions correctable by binary codes remains a tantalizing open question. [ABSTRACT FROM PUBLISHER]

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]

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]

The following result was proved by Bárány in 1982: For every d≥1, there exists c d>0 such that for every n-point set S in ℝ d, there is a point p∈ℝ d contained in at least c d n d+1− O( n d) of the d-dimensional simplices spanned by S. We investigate the largest possible value of c d. It was known that c d≤1/(2 d( d+1)!) (this estimate actually holds for every point set S). We construct sets showing that c d≤( d+1)−( d+1), and we conjecture that this estimate is tight. The best known lower bound, due to Wagner, is c d≥ γ d:=( d2+1)/(( d+1)!( d+1) d+1); in his method, p can be chosen as any centerpoint of S. We construct n-point sets with a centerpoint that is contained in no more than γ d n d+1+ O( n d) simplices spanned by S, thus showing that the approach using an arbitrary centerpoint cannot be further improved. We also prove that for every n-point set S⊂ℝ d, there exists a ( d−2)-flat that stabs at least c d, d−2 n3− O( n2) of the triangles spanned by S, with $c_{d,d-2}\ge\frac{1}{24}(1-1/(2d-1)^{2})$ . To this end, we establish an equipartition result of independent interest (generalizing planar results of Buck and Buck and of Ceder): Every mass distribution in ℝ d can be divided into 4 d−2 equal parts by 2 d−1 hyperplanes intersecting in a common ( d−2)-flat. [ABSTRACT FROM AUTHOR]

Abstract: An induced subgraph is called homogeneous if it is either a clique or an independent set. Let denote the size of the largest homogeneous subgraph of a graph G. In this short paper we study properties of graphs on n vertices with for some constant C. We show that every such graph contains an induced subgraph of order αn in which vertices have different degrees, where α and β depend only on C. This proves a conjecture of Erdős, Faudree and Sós. [Copyright &y& Elsevier]

Abstract: A core-particle (CP) model is derived to analyze transverse orbits of test-particles evolving in the presence of a core ion beam that has uniform density within an elliptical cross-section. The model can be applied to both quadrupole and solenoidal focused beams in periodic or aperiodic lattices. Efficient analytical descriptions of electrostatic space-charge fields external to the beam core are derived to simplify model equations. Image-charge effects are analyzed for an elliptical beam centered in a round, conducting pipe to estimate model corrections resulting from image-charge nonlinearities. Transformations are employed in diagnostics to remove coherent flutter motion associated with oscillations of the ion beam core due to rapidly varying, linear applied-focusing forces. Diagnostics for particle trajectories, Poincaré phase-space projections, and single-particle emittances based on these transformations better illustrate the effects of nonlinear forces acting on particles evolving outside the core. A numerical code has been written based on this model. Example applications illustrate model characteristics. The CP model described has recently been applied to identify physical processes leading to space-charge transport limits for an rms-envelope matched beam in a periodic quadrupole focusing-channel [S.M. Lund, S.R. Chawla, Nucl. Instr. and Meth. A 561 (2006) 203]. Further characteristics of these processes are presented here. [Copyright &y& Elsevier]