共查询到20条相似文献,搜索用时 15 毫秒
1.
A set of vectors is k-independent if all its subsets with no more than k elements are linearly independent. We obtain a result concerning the maximal possible cardinality Ind
q
(n, k) of a k-independent set of vectors in the n-dimensional vector space F
q
n
over the finite field F
q
of order q. Namely, we give a necessary and sufficient condition for Ind
q
(n, k) = n + 1. We conclude with some pertinent remarks re applications of our results to codes, graphs and hypercubes. 相似文献
2.
《代数通讯》2013,41(5):2095-2140
Abstract We construct an associative algebra A k and show that there is a representation of A k on V ?k , where V is the natural 2n-dimensional representation of the Lie superalgebra 𝔭(n). We prove that A k is the full centralizer of 𝔭(n) on V ?k , thereby obtaining a “Schur-Weyl duality” for the Lie superalgebra 𝔭(n). This result is used to understand the representation theory of the Lie superalgebra 𝔭(n). In particular, using A k we decompose the tensor space V ?k , for k = 2 or 3, and show that V ?k is not completely reducible for any k ≥ 2. 相似文献
3.
Elena Couselo Santos González Victor Markov Consuelo Martínez Alexander Nechaev 《Linear algebra and its applications》2010,433(2):356-364
We continue here the research on (quasi)group codes over (quasi)group rings. We give some constructions of [n,n-3,3]q-codes over Fq for n=2q and n=3q. These codes are linearly optimal, i.e. have maximal dimension among linear codes having a given length and distance. Although codes with such parameters are known, our main results state that we can construct such codes as (left) group codes. In the paper we use a construction of Reed-Solomon codes as ideals of the group ring FqG where G is an elementary abelian group of order q. 相似文献
4.
Li Fenggao 《高校应用数学学报(英文版)》2003,18(2):223-229
Let AG(n, F
q) be the n-dimensional affine space over F
q, where F
q is a finite field with q elements. Denote by Γ
(m) the graph induced by m-flats of AG(n, F
q). For any two adjacent vertices E and F of
is studied. In particular, sizes of maximal cliques in Γ
(m) are determined and it is shown that Γ
(m) is not edge-regular when m<n−1.
Supported by the National Natural Science Foundation of China (19571024) and Hunan Provincial Department of Education (02C512). 相似文献
5.
J. Haglund 《Advances in Mathematics》2003,175(2):319-334
We introduce the distribution function Fn(q,t) of a pair of statistics on Catalan words and conjecture Fn(q,t) equals Garsia and Haiman's q,t-Catalan sequence Cn(q,t), which they defined as a sum of rational functions. We show that Fn,s(q,t), defined as the sum of these statistics restricted to Catalan words ending in s ones, satisfies a recurrence relation. As a corollary we are able to verify that Fn(q,t)=Cn(q,t) when t=1/q. We also show the partial symmetry relation Fn(q,1)=Fn(1,q). By modifying a proof of Haiman of a q-Lagrange inversion formula based on results of Garsia and Gessel, we obtain a q-analogue of the general Lagrange inversion formula which involves Catalan words grouped according to the number of ones at the end of the word. 相似文献
6.
Ping Sun 《Quaestiones Mathematicae》2019,42(2):165-179
In this paper we consider the enumeration of three kinds of standard Young tableaux (SYT) of truncated shapes by use of the method of multiple integrals. A product formula for the number of truncated shapes of the form (nm, n ? r)\δk–1 is given, which implies that the number of SYT of truncated shape (n2, 1)\(1) is the number of level steps in all 2-Motzkin paths. The number of SYT with three rows truncated by some boxes ((n + k)3)\(k) is discussed. Furthermore, the integral representation of the number of SYT of truncated shape (nm)\(3, 2) is derived, which implies a simple formula of the number of SYT of truncated shape (nn)\(3, 2). 相似文献
7.
What is the maximum possible number, f3(n), of vectors of length n over {0,1,2} such that the Hamming distance between every two is even? What is the maximum possible number, g3(n), of vectors in {0,1,2}n such that the Hamming distance between every two is odd? We investigate these questions, and more general ones, by studying
Xor powers of graphs, focusing on their independence number and clique number, and by introducing two new parameters of a
graph G. Both parameters denote limits of series of either clique numbers or independence numbers of the Xor powers of G (normalized appropriately), and while both limits exist, one of the series grows exponentially as the power tends to infinity,
while the other grows linearly. As a special case, it follows that f3(n) = Θ(2n) whereas g3(n)=Θ(n).
* Research supported in part by a USA-Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva
Center for Geometry at Tel Aviv University.
† Research partially supported by a Charles Clore Foundation Fellowship. 相似文献
8.
Sapna Jain 《Discrete Mathematics》2008,308(9):1489-1499
R.T. Chien and D.T. Tang [On definition of a burst, IBM J. Res. Develop. 9 (1965) 292-293] introduced the concept of Chien and Tang bursts (CT bursts) for classical coding systems where codes are subsets (or subspaces) of the space , the space of all n-tuples with entries from a finite field Fq. In this paper, we extend the notion of CT bursts for array coding systems where array codes are subsets (or subspaces) of the space Matm×s(Fq), the linear space of all m×s matrices with entries from a finite field Fq, endowed with a non-Hamming metric [M.Yu. Rosenbloom, M.A. Tsfasman, Codes for m-metric, Problems Inform. Transmission 33 (1997) 45-52]. We also obtain some bounds on the parameters of array codes for the detection and correction of CT burst errors. 相似文献
9.
This paper deals with the problem of constructing superregular matrices that lead to MDP convolutional codes. These matrices are a type of lower block triangular Toeplitz matrices with the property that all the square submatrices that can possibly be nonsingular due to the lower block triangular structure are nonsingular. We present a new class of matrices that are superregular over a sufficiently large finite field F. Such construction works for any given choice of characteristic of the field F and code parameters (n,k,δ) such that (n−k)|δ. We also discuss the size of F needed so that the proposed matrices are superregular. 相似文献
10.
In this paper, we study the numbers D
n,k
which are defined as the number of permutations σ of the symmetric group S
n
such that σ has no cycles of length j for j ≤ k. In the case k = 1, D
n,1 is simply the number of derangements of an n-element set. As such, we shall call the numbers D
n,k
generalized derangement numbers. Garsia and Remmel [4] defined some natural q-analogues of D
n,1, denoted by D
n,1(q), which give rise to natural q-analogues of the two classical recursions of the number of derangements. The method of Garsia and Remmel can be easily extended
to give natural p, q-analogues D
n,1(p, q) which satisfy natural p, q-analogues of the two classical recursions for the number of derangements. In [4], Garsia and Remmel also suggested an approach
to define q-analogues of the numbers D
n,k
. In this paper, we show that their ideas can be extended to give a p, q-analogue of the generalized derangements numbers. Again there are two classical recursions for eneralized derangement numbers.
However, the p, q-analogues of the two classical recursions are not as straightforward when k ≥ 2.
Partially supported by NSF grant DMS 0400507. 相似文献
11.
Intersection theorems with geometric consequences 总被引:3,自引:0,他引:3
In this paper we prove that ifℱ is a family ofk-subsets of ann-set, μ0, μ1, ..., μs are distinct residues modp (p is a prime) such thatk ≡ μ0 (modp) and forF ≠ F′ ≠ℱ we have |F ∩F′| ≡ μi (modp) for somei, 1 ≦i≦s, then |ℱ|≦(
s
n
).
As a consequence we show that ifR
n
is covered bym sets withm<(1+o(1)) (1.2)
n
then there is one set within which all the distances are realised.
It is left open whether the same conclusion holds for compositep. 相似文献
12.
We introduce and solve a natural geometrical extremal
problem. For the set E
(n,w) = {x
n
{0,1}
n
:
x
n
has
w ones } of vertices of
weight w in the unit cube of
n
we determine M (n,k,w)
max{|U
k
n
E(n,w)|:U
k
n
is a
k-dimensional subspace of
n
. We also present an extension to multi-sets and explain a
connection to a higher dimensional Erds–Moser type
problem. 相似文献
13.
Dhruv Mubayi 《Journal of Combinatorial Theory, Series A》2005,111(1):106-110
Given positive integers n,k,t, with 2?k?n, and t<2k, let m(n,k,t) be the minimum size of a family F of (nonempty distinct) subsets of [n] such that every k-subset of [n] contains at least t members of F, and every (k-1)-subset of [n] contains at most t-1 members of F. For fixed k and t, we determine the order of magnitude of m(n,k,t). We also consider related Turán numbers T?r(n,k,t) and Tr(n,k,t), where T?r(n,k,t) (Tr(n,k,t)) denotes the minimum size of a family such that every k-subset of [n] contains at least t members of F. We prove that T?r(n,k,t)=(1+o(1))Tr(n,k,t) for fixed r,k,t with and n→∞. 相似文献
14.
Extending MDS Codes 总被引:1,自引:0,他引:1
T. L. Alderson 《Annals of Combinatorics》2005,9(2):125-135
A q-ary (n, k)-MDS code, linear or not, satisfies n ≤ q + k − 1. A code meeting this bound is said to have maximum length. Using purely combinatorial methods we show that an MDS code with n = q + k − 2 can be uniquely extended to a maximum length code if and only if q is even. This result is best possible in the sense that there is, for example, a non-extendable 4-ary (5, 4)-MDS code. It may be that the proof of our result is as interesting as the result itself. We provide a simple necessary and sufficient condition
for code extendability. In future work, this condition might be suitably modified to give an extendability condition for arbitrary (shorter) MDS codes.Received December 1, 2003 相似文献
15.
We explore properties of edge colorings of graphs dened
by set intersections. An edge coloring of a graph
G with vertex set
V ={1,2, . . . ,
n} is called
transitive if one can
associate sets F
1,F
2, . .
.,F
n
to vertices of G so that for
any two edges ij,kl E(G), the color of
ij and
kl is the same if and only if
F
i
F
j
= F
k
F
l
. The term
transitive refers to a
natural partial order on the color set of these
colorings.We prove a canonical Ramsey type result for transitive
colorings of complete graphs which is equivalent to a stronger
form of a conjecture of A. Sali on hypergraphs. This—through the
reduction of Sali—shows that the dimension of
n-element lattices is
o(n) as conjectured by Füredi and
Kahn.The proof relies on concepts and results which seem to
have independent interest. One of them is a generalization of
the induced matching lemma of Ruzsa and Szemerédi for transitive
colorings. * Research supported in part by OTKA Grant
T029074. 相似文献
16.
V. B. Mnukhin 《Acta Appl Math》1992,29(1-2):83-117
Let (G, W) be a permutation group on a finite set W = {w
1,..., w
n}. We consider the natural action of G on the set of all subsets of W. Let h
0, h
1,..., h
N
be the orbits of this action. For each i, 1 i N, there exists k, 1 k n, such that h
i
is a set of k-element subsets of W. In this case h
i is called a symmetrized k-orbit of the group (G, W) or simply a k-orbit. With a k-orbit h
i
we associate a multiset H(h
i
) = % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGGipm0dc9vqaqpepu0xbbG8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyykJeoaaa!3690!\[\langle \]h
i
(1), h
i
(2),..., h
i
(k)% MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGGipm0dc9vqaqpepu0xbbG8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyOkJepaaa!36A1!\[\rangle \] of its (k – 1)-suborbits. Orbits h
i
and h
j
are called equivalent if H(h
i
) = H(h
j
). An orbit is reconstructible if it is equivalent to itself only. The paper concerns the k-orbit reconstruction problem and its connections with different problems in combinatorics. The technique developed is based on the notion of orbit and co-orbit algebras associated with a given permutation group (G, W). 相似文献
17.
Raphael Loewy 《Linear and Multilinear Algebra》2013,61(4):355-382
Let k and n be positive integers such that kn. Let Sn (F) denote the space of all n×n symmetric matrices over the field F with char F≠2. A subspace L of Sn (F) is said to be a k-subspace if rank Ak for every A?L. Now suppose that k is even, and write k=2r. We say a k∥-subspace of Sn (F) is decomposable if there exists in Fn a subspace W of dimension n?r such that xtAx=0 for every x?W A?L. We show here, under some mild assumptions on k n and F, that every k∥-subspace of Sn (F) of sufficiently large dimension must be decomposable. This is an analogue of a result obtained by Atkinson and Lloyd for corresponding subspaces of Fm,n . 相似文献
18.
Joel Friedman 《Combinatorica》1993,13(2):235-239
In this paper we give an explicit construction ofn×n matrices over finite fields which are somewhat rigid, in that if we change at mostk entries in each row, its rank remains at leastCn(log
q
k)/k, whereq is the size of the field andC is an absolute constant. Our matrices satisfy a somewhat stronger property, we will explain and call strong rigidity. We introduce and briefly discuss strong rigidity, because it is in a sense a simpler property and may be easier to use in giving explicit construction.This paper was written while on leave from Princeton, at the Hebrew University. The author wishes to acknowledge the National Science Foundation for supporting this research in part under PYI grant CCR-8858788, and a grant from the program of Medium and Long Term Research at Foreign Centers of Excellence. 相似文献
19.
ZhaoHaixing LiuRuying ZhangShenggui 《高校应用数学学报(英文版)》2004,19(1):116-124
For a graph G,P(G,λ)denotes the chromatic polynomial of G. Two graphs G and H are said to be chromatically equivalent,denoted by G-H,if P(G,λ)=p(H,λ). Let[G]= {H|H-G}. If [G]={G},then G is said to be chromatically unique. For a complete 5-partite graph G with 5n vertices, define θ(G)=(a(G,6)-2^n 1-2^n-1 5)/2n-2,where a(G,6) denotes the number of 6-independent partitions of G. In this paper, the authors show that θ(G)≥0 and determine all graphs with θ(G)= 0, 1, 2, 5/2, 7/2, 4, 17/4. By using these results the chromaticity of 5-partite graphs of the form G-S with θ(G)=0,1,2,5/2,7/2,4,17/4 is investigated,where S is a set of edges of G. Many new chromatically unique 5-partite graphs are obtained. 相似文献
20.
Consider the set of all proper edge-colourings of a graph G with n colours. Among all such colourings, the minimum length of a longest two-coloured cycle is denoted L(n, G). The problem of understanding L(n, G) was posed by Häggkvist in 1978 and, specifically, L(n, K n,n ) has received recent attention. Here we construct, for each prime power q ≥ 8, an edge-colouring of K n,n with n colours having all two-coloured cycles of length ≤ 2q 2, for integers n in a set of density 1 ? 3/(q ? 1). One consequence is that L(n, K n,n ) is bounded above by a polylogarithmic function of n, whereas the best known general upper bound was previously 2n ? 4. 相似文献