共查询到20条相似文献,搜索用时 46 毫秒
1.
An ‐star is a complete bipartite graph . An ‐star system of order , is a partition of the edges of the complete graph into ‐stars. An ‐star system is said to be ‐colourable if its vertex set can be partitioned into sets (called colour classes) such that no ‐star is monochromatic. The system is ‐chromatic if is ‐colourable but is not ‐colourable. If every ‐colouring of an ‐star system can be obtained from some ‐colouring by a permutation of the colours, we say that the system is uniquely ‐colourable. In this paper, we first show that for any integer , there exists a ‐chromatic 3‐star system of order for all sufficiently large admissible . Next, we generalize this result for ‐star systems for any . We show that for all and , there exists a ‐chromatic ‐star system of order for all sufficiently large such that (mod ). Finally, we prove that for all and , there exists a uniquely ‐chromatic ‐star system of order for all sufficiently large such that (mod ). 相似文献
2.
3.
The ‐rank of a Steiner triple system (STS) is the dimension of the linear span of the set of characteristic vectors of blocks of , over GF . We derive a formula for the number of different STSs of order and given ‐rank , , and a formula for the number of STSs of order and given ‐rank , . Also, we prove that there are no STSs of ‐rank smaller than and, at the same time, ‐rank smaller than . Our results extend previous study on enumerating STSs according to the rank of their codes, mainly by Tonchev, V.A. Zinoviev, and D.V. Zinoviev for the binary case and by Jungnickel and Tonchev for the ternary case. 相似文献
4.
Xiande Zhang 《组合设计杂志》2020,28(7):509-524
An ‐ary ‐radius sequence is a finite sequence of elements taken from an alphabet of size in which any two distinct elements occur within distance of each other somewhere in the sequence. The study of constructing short ‐radius sequences was motivated by some problems occurring in large data transfer. Let be the shortest length of any ‐ary ‐radius sequence. We show that the conjecture by Bondy et al is true for , and determine the exact values of for new infinitely many . Further, we investigate new sequences which we call ‐difference, as they are related to ‐radius sequences and seem to be interesting in themselves. Finally, we answer a question about the optimal length of packing and covering analogs of universal cycles proposed by D?bski et al. 相似文献
5.
In this paper we relate ‐designs to a forbidden configuration problem in extremal set theory. Let denote a column of 1's on top of 0's. Let denote the matrix consisting of rows of 1's and rows of 0's. We consider extremal problems for matrices avoiding certain submatrices. Let be a (0, 1)‐matrix forbidding any submatrix . Assume is ‐rowed and only columns of sum are allowed to be repeated. Assume that has the maximum number of columns subject to the given restrictions. Assume is sufficiently large. Then has each column of sum and exactly once and, given the appropriate divisibility condition, the columns of sum correspond to a ‐design with block size and parameter . The proof derives a basic upper bound on the number of columns of by a pigeonhole argument and then a careful argument, for large m, reduces the bound by a substantial amount down to the value given by design‐based constructions. We extend in a few directions. 相似文献
6.
Due to the applications in network coding, subspace codes and designs have received many attentions. Suppose that and is an ‐dimensional space over the finite field . A ‐spread is a ‐set of ‐dimensional subspaces of such that each nonzero vector is contained in exactly one element of it. A partial ‐parallelism in is a set of pairwise disjoint ‐spreads. As the number of ‐dimensional subspaces in is , there are at most spreads in a partial ‐parallelism. By studying the independence numbers of Cayley graphs associated to a special type of partial ‐parallelisms in , we obtain new lower bounds for partial ‐parallelisms. In particular, we show that there exist at least pairwise disjoint ‐spreads in . 相似文献
7.
Let be a finite set with elements, called points and be a family of subsets of , called blocks. A pair is called ‐design whenever and
- 1. for all ;
- 2. for all , and not all are equal.
8.
We investigate how Legendre ‐array pairs are related to several different perfect binary ‐array families. In particular we study the relations between Legendre ‐array pairs, Sidelnikov‐Lempel‐Cohn‐Eastman ‐arrays, Yamada‐Pott ‐array pairs, Ding‐Helleseth‐Martinsen ‐arrays, Yamada ‐arrays, Szekeres ‐array pairs, Paley ‐array pairs, and Baumert ‐array pairs. Our work also solves one of the two open problems posed by Ding. Moreover, we provide several computer search‐based existence and nonexistence results regarding Legendre ‐array pairs. Finally, by using cyclotomic cosets, we provide a previously unknown Legendre ‐array pair. 相似文献
9.
Janne I. Kokkala Karen Meagher Reza Naserasr Kari J. Nurmela Patric R. J.
stergrd Brett Stevens 《组合设计杂志》2020,28(1):5-24
A covering array of strength is an array of symbols from an alphabet of size such that in every subarray, every ‐tuple occurs in at least one row. A covering array is optimal if it has the smallest possible for given , , and , and uniform if every symbol occurs or times in every column. Before this paper, the only known optimal covering arrays for were orthogonal arrays, covering arrays with constructed from Sperner's Theorem and the Erd?s‐Ko‐Rado Theorem, and 11 other parameter sets with and . In all these cases, there is a uniform covering array with the optimal size. It has been conjectured that there exists a uniform covering array of optimal size for all parameters. In this paper, a new lower bound as well as structural constraints for small uniform strength‐2 covering arrays is given. Moreover, covering arrays with small parameters are studied computationally. The size of an optimal strength‐2 covering array with and is now known for 21 parameter sets. Our constructive results continue to support the conjecture. 相似文献
10.
11.
In this paper, we study the existence problem for cyclic ‐cycle decompositions of the graph , the complete multipartite graph with parts of size , and give necessary and sufficient conditions for their existence in the case that . 相似文献
12.
Fu and Mishima [J. Combin. Des. 10 (2002), pp. 116–125] have utilized the extended Skolem sequence to prove that there exists a 1‐rotationally resolvable ‐cycle system of if and only if (mod ). In this paper, the existence of a cyclically near‐resolvable ‐cycle system is discussed, and it is shown that there exists a cyclically near‐resolvable ‐cycle system of if and only if (mod ). 相似文献
13.
An oriented tetrahedron defined on four vertices is a set of four cyclic triples with the property that any ordered pair of vertices is contained in exactly one of the cyclic triples. A tetrahedral quadruple system of order with index , denoted by , is a pair , where is an ‐set and is a set of oriented tetrahedra (blocks) such that every cyclic triple on is contained in exactly members of . A is pure if there do not exist two blocks with the same vertex set. When , the spectrum of a pure TQS has been completely determined by Ji. In this paper, we show that there exists a pure if and only if and . A corollary is that a simple also exists if and only if and . 相似文献
14.
The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. Recently, Lagrangian densities of hypergraphs and Turán numbers of their extensions have been studied actively. However, determining the Lagrangian density of a hypergraph is not an easy task even for a “simple” hypergraph. For example, to determine the Lagrangian density of is equivalent to determine the Turán density of (a long standing conjecture of Turán). Hefetz and Keevash studied the Lagrangian density of the 3‐uniform matching of size 2. Pikhurko determined the Lagrangian density of a 4‐uniform tight path of length 2 and this led to confirm the conjecture of Frankl and Füredi on the Turán number of the ‐uniform generalized triangle for the case . It is natural and interesting to consider Lagrangian densities of other “basic” hypergraphs. In this paper, we determine the Lagrangian densities for a class of 3‐uniform linear forests. For positive integers and , let be the disjoint union of a 3‐uniform linear path of length and pairwise disjoint edges. In this paper, we determine the Lagrangian densities of for any and or 3. Applying a modified version of Pikhurko's transference argument used by Brandt, Irwin, and Jiang, we obtain the Turán numbers of their extensions. 相似文献
15.
Michael Braun 《组合设计杂志》2019,27(11):682-687
An ‐arc in is a set of points such that each line contains at most of the selected points. It is well known that ‐arcs in correspond to projective linear codes. Let denote the maximal number of points for which an ‐arc in exists. In this paper we obtain improved lower bounds on by explicitly constructing ‐arcs. Some of the constructed ‐arcs correspond to linear codes meeting the Griesmer bound. All results are obtained by integer linear programming. 相似文献
16.
17.
A Deza graph with parameters is a ‐regular graph on vertices in which the number of common neighbors of two distinct vertices takes one of the following values: or , where . In the previous papers Deza graphs with were characterized. In this paper, we characterize Deza graphs with . 相似文献
18.
19.
Let be a fixed prime power and let denote a vector space of dimension over the Galois field with elements. A subspace partition (also called “vector space partition”) of is a collection of subspaces of with the property that every nonzero element of appears in exactly one of these subspaces. Given positive integers such that , we say a subspace partition of has type if it is composed of subspaces of dimension and subspaces of dimension . Let . In this paper, we prove that if divides , then one can (algebraically) construct every possible subspace partition of of type whenever , where and . Our construction allows us to sequentially reconfigure batches of subspaces of dimension into batches of subspaces of dimension . In particular, this accounts for all numerically allowed subspace partition types of under some additional conditions, for example, when . 相似文献
20.
A partial difference set in a finite group satisfying and corresponds to an undirected strongly regular Cayley graph . While the case when is abelian has been thoroughly studied, there are comparatively few results when is nonabelian. In this paper, we provide restrictions on the parameters of a partial difference set that apply to both abelian and nonabelian groups and are especially effective in groups with a nontrivial center. In particular, these results apply to ‐groups, and we are able to rule out the existence of partial difference sets in many instances. 相似文献