共查询到20条相似文献,搜索用时 93 毫秒
1.
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. 相似文献
2.
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. 相似文献
3.
Hiroshi Suzuki 《Graphs and Combinatorics》1991,7(4):363-375
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. 相似文献
4.
B. V. Dekster 《Acta Mathematica Hungarica》2000,86(4):343-358
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
We prove then that regular d-simplexes in M
d
can be constructed as freely as in E
d
. In fact, a more general theorem dealing with simplexes sufficiently close to regular ones has been proved.This result can be applied to finite-dimensional subspaces of an infinite-dimensional Banach space X. It is known that, for any d 2 and any > 0, the space X has a d-dimensional subspace M
d
with (M
d
) 1 + . Under a proper selection of , the condition (M
d
) 1(d) above holds which guarantees the existence of regular d-simplexes in M
d
X. 相似文献
5.
Klaus Metsch 《Designs, Codes and Cryptography》2005,34(2-3):339-360
Given a hermitian variety H(d,q2) and an integer k (d–1)/2, a blocking set with respect to k-subspaces is a set of points of H(d,q2) that meets all k-subspaces of H(d,q2). If H(d,q2) is naturally embedded in PG(d,q2), then linear examples for such a blocking set are the ones that lie in a subspace of codimension k of PG(d,q2). 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,q2) 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 相似文献
6.
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. 相似文献
7.
Z. Füredi 《Discrete and Computational Geometry》1986,1(1):315-319
LetC
d
be the set of vertices of ad-dimensional cube,C
d
={(x
1, ...,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. 相似文献
8.
On the geometry of random Cantor sets and fractal percolation 总被引:1,自引:0,他引:1
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,(9) (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,(4) who studied the special case whend=2. 相似文献
9.
Mowaffaq Hajja 《Results in Mathematics》2006,49(3-4):237-263
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. 相似文献
10.
E. P. Golubeva 《Journal of Mathematical Sciences》2004,122(6):3600-3602
Let (d) be the least solution of the Pellian equation x
2-dy
2 = 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. 相似文献
11.
Satoshi Yoshiara 《Journal of Algebraic Combinatorics》2004,19(1):5-23
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
i, using the Veronesean, observed first by Thas and van Maldeghem (Proposition 7). Another construction using caps is given as well (Proposition 10). 相似文献
12.
P. Gabriel L. A. Nazarova A. V. Roiter V. V. Sergeichuk D. Vossieck 《Ukrainian Mathematical Journal》1993,45(3):335-372
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[Bd]-module structures onR
d, and Md is a canonical Bk k[Bd]-module supported by k[Bd]d. Further, say that an affine subscheme of Bd isclass true if the functor Fgn X Md k[B] X induces an injection between the sets of isomorphism classes of indecomposable finite-dimensional modules over k[] andB. If Bd contains a class-true plane for somed, then the schemes Be contain class-true subschemes of arbitrary dimensions. Otherwise, each Bd 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. 相似文献
13.
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. 相似文献
14.
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. 相似文献
15.
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
. 相似文献
16.
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 polygonspn, dof length 2nwithd(n)→∞ is asymptoticallywherer=r(n, d) is the unique solution ofr coth r=2n/d−1andb(r)=d(r coth r−r2/sinh2 r). The convergence is uniform over alld?ω(n) for any functionω(n)→∞. Whendis constant the exponential is replaced with (1−d−1)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. 相似文献
17.
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 P4, 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={v1,…,vn}. 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. 相似文献
18.
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. 相似文献
19.
Aladar Heppes 《Discrete and Computational Geometry》2008,40(2):312-318
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. 相似文献
20.
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 5d3n1?(2/d)+d15 for all d≥3 and n≥1. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 50–58, 2002 相似文献