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.     

On hyperplanes and polytopes

We call a convex subsetN of a convexd-polytopePE ^d ak-nucleus ofP ifN meets everyk-face ofP, where 0<k<d. We note thatP has disjointk-nuclei if and only if there exists a hyperplane inE ^d which bisects the (relative) interior of everyk-face ofP, and that this is possible only if [d+2/2]kd–1. Our main results are that any convexd-polytope with at most 2d–1 vertices (d3) possesses disjoint (d–1)-nuclei and that 2d–1 is the largest possible number with this property. Furthermore, every convexd-polytope with at most 2d facets (d3) possesses disjoint (d–1)-nuclei, 2d cannot be replaced by 2d+2, and ford=3, six cannot be replaced by seven.Partially supported by Hung. Nat. Found. for Sci. Research number 1238.Partially supported by the Natural Sciences and Engineering Council of Canada.Partially supported by N.S.F. grant number MCS-790251.     

Bounding the diameter of a distance regular graph by a function ofk d

Let be a distance regular graph with diameterd, and _d () the set of vertices at distanced from. is said to be thin if the induced subgraph on _d () is a union of cliques for every vertex. We show that the diameterd is bounded above by a function depending only onk _d, which is the cardinality of _d (), if is not thin. We also investigate thin distance regular graphs witha _d 0.     

Simplexes with Prescribed Edge Lengths in Minkowski and Banach Spaces

Existence of even a single regular d-simplex in an arbitrary Minkowski space M ^d of dimension d 4 is questionable. At least, for any d 4 there is an example of M ^d with four equidistant points in it which cannot be augmented by any fifth such point. At the same time, regular tetrahedra in M ^d , d 3, and regular triangles in M ^d , d 2, can be constructed as freely as in E ^d . Suppose that the Banach-Mazur distance between the unit balls of M ^d and E ^d satisfies

Blocking Structures of Hermitian Varieties

Given a hermitian variety H(d,q²) and an integer k (d–1)/2, a blocking set with respect to k-subspaces is a set of points of H(d,q²) that meets all k-subspaces of H(d,q²). If H(d,q²) is naturally embedded in PG(d,q²), then linear examples for such a blocking set are the ones that lie in a subspace of codimension k of PG(d,q²). Up to isomorphism there are k+1 non-isomorphic minimal linear blocking sets, and these have different cardinalities. In this paper it is shown for 1 k< (d–1)/2 that all sufficiently small minimal blocking sets of H(d,q²) with respect to k-subspaces are linear. For 1 k< d/2–3, it is even proved that the k+1 minimal linear blocking sets are smaller than all minimal non-linear ones.AMS Classification: 1991 MSC: 51E20, 51E21     

Every 8-uniform 8-regular hypergraph is 2-colorable

As is well known, Lovász Local Lemma implies that everyd-uniformd-regular hypergraph is 2-colorable, providedd 9. We present a different proof of a slightly stronger result; everyd-uniformd-regular hypergraph is 2-colorable, providedd 8.Research supported in part by Allon Fellowship and by a grant from the United States Israel Binational Science Foundation.     

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.     

On the geometry of random Cantor sets and fractal percolation

Random Cantor sets are constructions which generalize the classical Cantor set, middle third deletion being replaced by a random substitution in an arbitrary number of dimensions. Two results are presented here. (a) We establish a necessary and sufficient condition for the projection of ad-dimensional random Cantor set in [0,1]^d onto ane-dimensional coordinate subspace to contain ane-dimensional ball with positive probability. The same condition applies to the event that the projection is the entiree-dimensional unit cube [0,1] ^e . This answers a question of Dekking and Meester,⁽⁹⁾ (b) The special case of fractal percolation arises when the substitution is as follows: The cube [0,1] ^d is divided intoM ^d subcubes of side-lengthM ^–, and each such cube is retained with probabilityp independently of all other subcubes. We show that the critical valuep _c(M, d) ofp, marking the existence of crossings of [0,1] ^d contained in the limit set, satisfiesp _c(M, d)p _c(d) asM, wherep _c(d) is the critical probability of site percolation on a latticeL ^d obtained by adding certain edges to the hypercubic lattice ^d . This result generalizes in an unexpected way a finding of Chayes and Chayes,⁽⁴⁾ who studied the special case whend=2.     

Coincidences of Centers of Edge-Incentric, or Balloon, Simplices

An edge-incentric d-simplex is defined to be a d-simplex S which admits a (d − 1)-sphere that touches all the edges of S internally. The center of such a sphere is called the edge-incenter of S and is denoted by . Equivalently, S is edge-incentric if and only if its vertices are the centers of d + 1 (d − 1)-spheres in mutual external touch, and for this reason one may call such an S a balloon d-simplex. An orthocentric d-simplex is a d-simplex in which the altitudes are concurrent. The point of concurrence is called the orthocenter and is denoted by . The spaces of edge-incentric and of orthocentric d-simplices have the same dimension d in the sense that a d-simplex in either space can be parametrized, up to shape, by d numbers. Edge-incentric and orthocentric tetrahedra are the first two of the four special classes of tetrahedra studied in [1, Chapter IX.B, pp. 294–333]. The degree of regularity implied by the coincidence of two or more centers of a general d-simplex is investigated in [8], where it is shown that the coincidence of the centroid , the circumcenter , and the incenter does not imply much regularity. For an orthocentric d-simplex S, however, it is proved in [9] that if any two of the centers , and coincide, then S is regular. In this paper, the same question is addressed for edge-incentric d-simplices. Among other things, it is proved that if any three of the centers , and of an edge-incentric d-simplex S coincide, then S is regular, and it is also shown that none of the coincidences , and implies regularity (except when d ≤ 3, d ≤ 4, and d ≤ 6, respectively). In contrast with the afore-mentioned results for orthocentric d-simplices, this emphasizes once more the feeling that, regarding many important properties, orthocentric d-simplices are the true generalizations of triangles. Several open questions are posed. Received: June 19, 2006.     

On the Pellian Equation

Let (d) be the least solution of the Pellian equation x ²-dy ² = 1. It is proved that there exists a sequence of values of d having a positive density and such that (d) > d ^2-, where is an arbitrary positive constant. Bibliogrhaphy: 7 titles.     

Ambient Spaces of Dimensional Dual Arcs

A d-dimensional dual arc in PG(n, q) is a higher dimensional analogue of a dual arc in a projective plane. For every prime power q other than 2, the existence of a d-dimensional dual arc (d 2) in PG(n, q) of a certain size implies n d(d + 3)/2 (Theorem 1). This is best possible, because of the recent construction of d-dimensional dual arcs in PG(d(d + 3)/2, q) of size ^d–1 _i=0 q ⁱ, using the Veronesean, observed first by Thas and van Maldeghem (Proposition 7). Another construction using caps is given as well (Proposition 10).     

Tame and wild subspace problems

Assume thatB is a finite-dimensional algebra over an algebraically closed fieldk, B _d =Spec k[(B _d ] is the affine algebraic scheme whoseR-points are theB _k k[B_d]-module structures onR ^d, and M_d is a canonical B_k k[B_d]-module supported by k[B_d]^d. Further, say that an affine subscheme of B_d isclass true if the functor F_gn X M_{d k[B]} X induces an injection between the sets of isomorphism classes of indecomposable finite-dimensional modules over k[] andB. If B_d contains a class-true plane for somed, then the schemes B_e contain class-true subschemes of arbitrary dimensions. Otherwise, each B_d contains a finite number of classtrue puncture straight linesL(d, i) such that for eachn, almost each indecomposableB-module of dimensionn is isomorphic to someF _{L(d, i)} (X); furthermore,F _{L(d, i)} (X) is not isomorphic toF _{L(l, j)} (Y) if(d, i) (l, j) andX 0. The proof uses a reduction to subspace problems, for which an inductive algorithm permits us to prove corresponding statements.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 45, No. 3, pp. 313–352, March, 1993.     

On the dimension to represent a graph by a unit distance graph

It is proved that if a graphG has maximum degreed, then its vertices can be represented by distinct unit vectors inR ^2d so that two vectors are orthogonal if and only if the corresponding vertices are adjacent. As a corollary it follows that if a graph has maximum degreed, then it is isomorphic to a unit distance graph inR ^2d.     

On the shape of the convex hull of random points

Summary Denote by E _n the convex hull of n points chosen uniformly and independently from the d-dimensional ball. Let Prob(d, n) denote the probability that E _n has exactly n vertices. It is proved here that Prob(d, 2 ^d/2 d ^-)1 and Prob(d, 2 ^d/2 d ^(3/4)+)0 for every fixed >0 when d. The question whether E _n is a k-neighbourly polytope is also investigated.     

Lower Bounds For Multidimensional Zero Sums

Let f(n, d) denote the least integer such that any choice of f(n, d) elements in contains a subset of size n whose sum is zero. Harborth proved that (n-1)2 ^d +1 f(n,d) (n-1)n ^d +1. The upper bound was improved by Alon and Dubiner to c _d n. It is known that f(n-1) = 2n-1 and Reiher proved that f(n-2) = 4n-3. Only for n = 3 it was known that f(n,d) > (n-1)2 ^d +1, so that it seemed possible that for a fixed dimension, but a sufficiently large prime p, the lower bound might determine the true value of f(p,d). In this note we show that this is not the case. In fact, for all odd n 3 and d 3 we show that .     

Asymptotic Enumeration of Convex Polygons

A polygon is an elementary (self-avoiding) cycle in the hypercubic lattice ^dtaking at least one step in every dimension. A polygon on ^dis said to be convex if its length is exactly twice the sum of the side lengths of the smallest hypercube containing it. The number ofd-dimensional convex polygonsp_{n, d}of length 2nwithd(n)→∞ is asymptoticallywherer=r(n, d) is the unique solution ofr coth r=2n/d−1andb(r)=d(r coth r−r²/sinh² r). The convergence is uniform over alld?ω(n) for any functionω(n)→∞. Whendis constant the exponential is replaced with (1−d⁻¹)^2d. These results are proved by asymptotically enumerating a larger class of combinatorial objects calledconvex proto-polygonsby the saddle-point method and then finding the asymptotic probability a randomly chosen convex proto-polygon is a convex polygon.     

Decomposing complete edge-chromatic graphs and hypergraphs. Revisited

A d-graph is a complete graph whose edges are colored by d colors, that is, partitioned into d subsets some of which might be empty. We say that a d-graph is complementary connected (CC) if the complement to each chromatic component of is connected on V. We prove that every such d-graph contains a sub-d-graph Π or , where Π has four vertices and two non-empty chromatic components each of which is a P₄, while is a three-colored triangle. This statement implies that each Π- and -free d-graph is uniquely decomposable in accordance with a tree whose leaves are the vertices of V and the interior vertices of T are labeled by the colors 1,…d. Such a tree is naturally interpreted as a positional game form (with perfect information and without moves of chance) of d players I={1,…,d} and n outcomes V={v₁,…,v_n}. Thus, we get a one-to-one correspondence between these game forms and Π- and -free d-graphs. As a corollary, we obtain a characterization of the normal forms of positional games with perfect information and, in case d=2, several characterizations of the read-once Boolean functions. These results are not new; in fact, they are 30 and, in case d=2, even 40 years old. Yet, some important proofs did not appear in English.Gyárfás and Simonyi recently proved a similar decomposition theorem for the -free d-graphs. They showed that each -free d-graph can be obtained from the d-graphs with only two non-empty chromatic components by successive substitutions. This theorem is based on results by Gallai, Lovász, Cameron and Edmonds. We obtain some new applications of these results.     

Can you cover your shadows?

A subsetX of thed-dimensional Euclidean space ^d can cover its shadows inR ^d , if every orthogonal projection ofX onto a (d–1)-dimensional linear subspace of ^d is contained in some congruent copy ofX. Whereas every two-dimensional convex discC R ^d has this property, no (d–1)-polytope does, provided thatd>-4.     

Line Transversals in Large <Emphasis Type="Italic">T</Emphasis>(3)- and <Emphasis Type="Italic">T</Emphasis>(4)-Families of Congruent Discs

A family of closed discs is said to have property T(k) if to every subset of at most k discs there belongs a common line transversal. A family of discs is said to be d-disjoint, d≥1, if the mutual distance between the centers of the discs is larger than d. It is known that a d-disjoint T(3)-family ℱ of unit diameter discs has a line transversal if . Similarly, a d-disjoint T(4)-family has a line transversal if . Both results are sharp in d, i.e., they do not hold for smaller values of d. The main result of this paper is that while the above lower bounds on d cannot be relaxed in general, some reduction of d can be compensated by imposing a proper d-dependent lower bound on the size of the family in both cases.     

Inexpensive d‐dimensional matchings

Suppose that independent U(0, 1) weights are assigned to the ${d\choose 2}n^{2}$ edges of the complete d‐partite graph with n vertices in each of the d maximal independent sets. Then the expected weight of the minimum‐weight perfect d‐dimensional matching is at least $\frac{3}{16}n^{1-(2/d)}$. We describe a randomized algorithm that finds a perfect d‐dimensional matching whose expected weight is at most 5d³n^1?(2/d)+d¹⁵ for all d≥3 and n≥1. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 50–58, 2002