The Nonexistence of Ternary [38, 6, 23] Codes

It has been shown by Bogdanova and Boukliev [1] that there exist a ternary [38,5,24] code and a ternary [37,5,23] code. But it is unknown whether or not there exist a ternary [39,6,24] code and a ternary [38,6,23] code. The purpose of this paper is to prove that (1) there is no ternary [39,6,24] code and (2) there is no ternary [38,6,23] code using the nonexistence of ternary [39,6,24] codes. Since it is known (cf. Brouwer and Sloane [2] and Hamada and Watamori [14]) that (i) n₃(6,23) = 38> or 39 and d₃(38,6) = 22 or 23 and (ii) n₃(6,24) = 39 or 40 and d₃(39,6) = 23 or 24, this implies that n₃(6,23) = 39, d₃(38,6) = 22, n₃(6,24) = 40 and d₃(39,6) = 23, where n3<>(k,d) and d<>3(n,k) denote the smallest value of n and the largest value of d, respectively, for which there exists an [n,k,d] code over the Galois field GF(3).     

Generalized Steiner systems GS4 (2, 4, v,g) for g = 2, 3, 6

Generalized Steiner systems GS_d(t, k, v, g) were first introduced by Etzion and used to construct optimal constant‐weight codes over an alphabet of size g + 1 with minimum Hamming distance d, in which each codeword has length v and weight k. Much work has been done for the existence of generalized Steiner triple systems GS(2, 3, v, g). However, for block size four there is not much known on GS_d(2, 4, v, g). In this paper, the necessary conditions for the existence of a GS_d(t, k, v, g) are given, which answers an open problem of Etzion. Some singular indirect product constructions for GS_d(2, k, v, g) are also presented. By using both recursive and direct constructions, it is proved that the necessary conditions for the existence of a GS₄(2, 4, v, g) are also sufficient for g = 2, 3, 6. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 401–423, 2001     

Optimal ternary linear codes

Let n _q (k, d) denote the smallest value of n for which there exists a linear [n, k, d]-code over GF(q). An [n, k, d]-code whose length is equal to n _q (k, d) is called optimal. The problem of finding n _q (k, d)has received much attention for the case q = 2. We generalize several results to the case of an arbitrary prime power q as well as introducing new results and a detailed methodology to enable the problem to be tackled over any finite field.In particular, we study the problem with q = 3 and determine n ₃(k, d) for all d when k 4, and n ₃(5, d) for all but 30 values of d.     

Error-Correcting Codes over an Alphabet of Four Elements

The problem of finding the values of A_q(n,d)—the maximum size of a code of length n and minimum distance d over an alphabet of q elements—is considered. Upper and lower bounds on A₄(n,d) are presented and some values of this function are settled. A table of best known bounds on A₄(n,d) is given for n 12. When q M < 2q, all parameters for which A_q(n,d) = M are determined.     

Energy of Flows on Percolation Clusters

It is well known for which gauge functions H there exists a flow in Z ^d with finite H energy. In this paper we discuss the robustness under random thinning of edges of the existence of such flows. Instead of Z ^d we let our (random) graph cal C cal (Z ^d,p) be the graph obtained from Z ^d by removing edges with probability 1–p independently on all edges. Grimmett, Kesten, and Zhang (1993) showed that for d3,p>p _c(Z ^d), simple random walk on cal C cal (Z ^d,p) is a.s. transient. Their result is equivalent to the existence of a nonzero flow f on the infinite cluster such that the x ² energy _e f(e)² is finite. Levin and Peres (1998) sharpened this result, and showed that if d3 and p>p _c(Z ^d), then cal C cal (Z ^d,p) supports a nonzero flow f such that the x ^q energy is finite for all q>d/(d–1). However, for general gauge functions, there is a gap between the existence of flows with finite energy which results from the work of Levin and Peres and the known results on flows for Z ^d. In this paper we close the gap by showing that if d3 and Z ^d supports a flow of finite H energy then the infinite percolation cluster on Z ^d also support flows of finite H energy. This disproves a conjecture of Levin and Peres.     

Random polytopes in thed-dimensional cube

LetC ^d be the set of vertices of ad-dimensional cube,C ^d ={(x ₁, ...,x _d ):x _i =±1}. Let us choose a randomn-element subsetA(n) ofC ^d . Here we prove that Prob (the origin belongs to the convA(2d+x2d))=(x)+o(1) ifx is fixed andd . That is, for an arbitrary>0 the convex hull of more than (2+)d vertices almost always contains 0 while the convex hull of less than (2-)d points almost always avoids it.     

Bounding the number of connected components of a real algebraic set

For every polynomial mapf=(f ₁,…,f _k): ℝ ⁿ →ℝ ^k , we consider the number of connected components of its zero set,B(Z _f) and two natural “measures of the complexity off,” that is the triple(n, k, d), d being equal to max(degree off _i), and thek-tuple (Δ₁,...,Δ₄), Δ _k being the Newton polyhedron off _i respectively. Our aim is to boundB(Z _f) by recursive functions of these measures of complexity. In particular, with respect to (n, k, d) we shall improve the well-known Milnor-Thom’s bound μ _d (n)=d(2d−1) ⁿ⁻¹. Considered as a polynomial ind, μ _d (n) has leading coefficient equal to 2 ⁿ⁻¹. We obtain a bound depending onn, d, andk such that ifn is sufficiently larger thank, then it improves μ _d (n) for everyd. In particular, it is asymptotically equal to 1/2(k+1)n ^k−1 dⁿ, ifk is fixed andn tends to infinity. The two bounds are obtained by a similar technique involving a slight modification of Milnor-Thom's argument, Smith's theory, and information about the sum of Betti numbers of complex complete intersections.     

Momentopes, the Complexity of Vector Partitioning, and Davenport—Schinzel Sequences

The computational complexity of the partition problem , which concerns the partitioning of a set of n vectors in d -space into p parts so as to maximize an objective function which is convex on the sum of vectors in each part, is determined by the number of vertices of the corresponding p-partition polytope defined to be the convex hull in (d\times p) -space of all solutions. In this article, introducing and using the class of Momentopes , we establish the lower bound v _p,d (n)=Ω(n^ \lfloor (d-1)/2 \rfloor p ) on the maximum number of vertices of any p -partition polytope of a set of n points in d -space, which is quite compatible with the recent upper bound v _p,d (n)=O(n ^d(p-1)-1 ) , implying the same bound on the complexity of the partition problem. We also discuss related problems on the realizability of Davenport—Schinzel sequences and describe some further properties of Momentopes. Received April 4, 2001, and in revised form October 3, 2001. Online publication February 28, 2002.     

The structure of the set of satisfying assignments for a random <Emphasis Type="Italic">k</Emphasis>-CNF

Let F _k (n, m) be a random k-CNF obtained by a random, equiprobable, and independent choice of m brackets from among all k-literal brackets on n variables. We investigate the structure of the set of satisfying assignments of F _k (n, m). A method is proposed for finding r(k, s)such that the probability of presence of ns-dimensional faces (0 < s < 1) in the set of satisfying assignments of the formula F _k s(n, r(k, s)n) goes to 1 as n goes to infinity. We prove the existence of a sequential threshold for the property of having ns-dimensional faces (0 < s < 1). In other words, there exists a sequence r _n (k, s) such that the probability of having an ns-dimensional face in the set of satisfying assignments of the formula F _k (n, r _n (k, s)(1 + d)n) goes to 0 for all d > 0 and to 1 for all d < 0. __________ Translated from Prikladnaya Matematika i Informatika, No. 26, pp. 61–95, 2007.     

On the postulation of a general projection of a curve inP 3

Summary We say that a curve C in P ³ has maximal rank if for every integer k the restriction map r_c(k):H ⁰(P ³, O_P3(k)) H⁰ (C, O_C(k))has maximal rank. Here we prove the following results. Theorem 1Fix integers g, d with 0g3,dg+3.Fix a curve X of genus g and L Pic^d (X).If g=3and X is hyperelliptic, assume d8. Let _L(X)be the image of X by the complete linear system H ⁰(X, L). Then a general projection of _L(X)into P ³ has maximal rank. Theorem 2For every integer g0,there exists an integer d(g, 3)such that for every dd(g, 3),for every smooth curve X of genus g and every LPic^d (X) the general projection of _L(X)into P ³ has maximal rank.     

The Smallest Parallelepiped of n Random Points and Peeling

Let n random points be given with uniform distribution in the d-dimensional unit cube [0,1]^d. The smallest parallelepiped A which includes all the n random points is dealt with. We investigate the asymptotic behavior of the volume of A as n tends to . Using a point process approach, we derive also the asymptotic behavior of the volumes of the k-th smallest parallelepipeds A _n ^(k) which are defined by iteration. Let A _n = A _n ⁽¹⁾ . Given A _n ^(k,-,1) delete the random points X _i which are on the boundary A _n ^(k,-,1) , and construct the smallest parallelepiped which includes the inner points of A _n ^(k,-,1) , this defines A _n ^(k) . This procedure is known as peeling of the parallelepiped A_n.     

Circular perfect graphs

For 1 ≤ d ≤ k, let K_k/d be the graph with vertices 0, 1, …, k ? 1, in which i ～j if d ≤ |i ? j| ≤ k ? d. The circular chromatic number χ_c(G) of a graph G is the minimum of those k/d for which G admits a homomorphism to K_k/d. The circular clique number ω_c(G) of G is the maximum of those k/d for which K_k/d admits a homomorphism to G. A graph G is circular perfect if for every induced subgraph H of G, we have χ_c(H) = ω_c(H). In this paper, we prove that if G is circular perfect then for every vertex x of G, N_G[x] is a perfect graph. Conversely, we prove that if for every vertex x of G, N_G[x] is a perfect graph and G ? N[x] is a bipartite graph with no induced P₅ (the path with five vertices), then G is a circular perfect graph. In a companion paper, we apply the main result of this paper to prove an analog of Haj?os theorem for circular chromatic number for k/d ≥ 3. Namely, we shall design a few graph operations and prove that for any k/d ≥ 3, starting from the graph K_k/d, one can construct all graphs of circular chromatic number at least k/d by repeatedly applying these graph operations. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 186–209, 2005     

Even diameters of the classes W(r)H ω in the space C2π

For even values of n we find the exact values of the diameters d_n(W^(r)H) of the classes of 2-periodic functions ((t) is an arbitrary convex upwards modulus of continuity) in the space C₂. We find that d_2n(W^(r)H)=d_2n–1(W^(r)H) (n=1, 2, ... r=0, 1, 2, ...).Translated from Matematicheskie Zametki, Vol. 15, No. 3, pp. 387–392, March, 1974.The author expresses his thanks to N. P. Korneichuk for his interest in my work.     

How many atoms can be defined by boxes?

We study the functionb(n, d), the maximal number of atoms defined byn d-dimensional boxes, i.e. parallelopipeds in thed-dimensional Euclidean space with sides parallel to the coordinate axes. We characterize extremal interval families definingb(n, 1)=2n-1 atoms and we show thatb(n, 2)=2n ²-6n+7. We prove that for everyd, exists and . Moreover, we obtainb*(3)=8/9.     

Existence of a smooth solution of one boundary-value problem

We study a periodic boundary-value problem for the quasilinear equationu _tt–u_xx=F[u, u_t], u(0, t)=u(, t)=0,u(x, t+2)=u(x, t). We establish conditions that guarantee the validity of the uniqueness theorem.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 47, No. 12, pp. 1717–1719, December, 1995.     

On k -diameter of k -connected graphs

Let G be a k-connected simple graph with order n. The k-diameter, combining connectivity with diameter, of G is the minimum integer d _k (G) for which between any two vertices in G there are at least k internally vertex-disjoint paths of length at most d _k (G). For a fixed positive integer d, some conditions to insure d _k (G)⩽d are given in this paper. In particular, if d⩾3 and the sum of degrees of any s (s=2 or 3) nonadjacent vertices is at least n+(s−1)k+1−d, then d _k (G)⩽d. Furthermore, these conditions are sharp and the upper bound d of k-diameter is best possible. Supported by NNSF of China (19971086).     

Non polynomial splines and weakly singular two-point boundary value problems

In the present paper we shall consider an application of simple non-polynomial splines to a numerical solution of a weakly singular two-point boundary value problem:x ^– (x y)=f(x,y), (0<x1) subject toy(0)=0,y(1)=c ₁(1) ory(0)=c ₂,y(1)=c ₃(0<<1). Our collocation method gives a continuously differentiable approximation and isO(h ²)-convergent.     

Optimal holey packings OHP4(2, 4, n ,3)'s

An optimal holey packing OHP_d(2, k, n, g) is equivalent to a maximal (g + 1)‐ary (n, k, d) constant weight code. In this paper, we provide some recursive constructions for OHP_d(2, k, n, g)'s and use them to investigate the existence of an OHP₄(2, 4, n, 3) for n ≡ 2, 3 (mod 4). Combining this with Wu's result ( 18 ), we prove that the necessary condition for the existence of an OHP₄(2, 4, n, 3), namely, n ≥ 5 is also sufficient, except for n ∈ {6, 7} and except possibly for n = 26. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 111–123, 2006     

Codes of Steiner triple and quadruple systems

The code over a finite fieldF _q of orderq of a design is the subspace spanned by the incidence vectors of the blocks. It is shown here that if the design is a Steiner triple system on points, and if the integerd is such that 2 ^d –1<2 ^d+1–1, then the binary code of the design contains a subcode that can be shortened to the binary Hamming codeH _d of length 2 ^d –1. Similarly the binary code of any Steiner quadruple system on +1 points contains a subcode that can be shortened to the Reed-Muller code (d–2,d) of orderd–2 and length 2 ^d , whered is as above.     

Frobenius problem for semigroups \mathsf{S}(d_{1},d_{2},d_{3})

We find the matrix representation of the set Δ(d ³), where d ³=(d ₁,d ₂,d ₃), of integers that are unrepresentable by d ₁,d ₂,d ₃ and develop a diagrammatic procedure for calculating the generating function Φ(d ³;z) for the set Δ(d ³). We find the Frobenius number F(d ³), the genus G(d ³), and the Hilbert series H(d ³;z) of a graded subring for nonsymmetric and symmetric semigroups and enhance the lower bounds of F(d ³) for symmetric and nonsymmetric semigroups.