Parameters for which the Griesmer bound is not sharp

We prove for a large class of parameters t and r that a multiset of at most tθ_d-k+rθ_d-k-2 points in PG(d,q) that blocks every k-dimensional subspace at least t times must contain a sum of t subspaces of codimension k.We use our results to identify a class of parameters for linear codes for which the Griesmer bound is not sharp. Our theorem generalizes the non-existence results from Maruta [On the achievement of the Griesmer bound, Des. Codes Cryptogr. 12 (1997) 83-87] and Klein [On codes meeting the Griesmer bound, Discrete Math. 274 (2004) 289-297].     

A weighted version of a result of Hamada on minihypers and on linear codes meeting the Griesmer bound

Minihypers were introduced by Hamada to investigate linear codes meeting the Griesmer bound. Hamada (Bull Osaka Women’s Univ 24:1–47, 1985; Discrete Math 116:229–268, 1993) characterized the non-weighted minihypers having parameters , with k−1 > λ₁ > λ₂ > ... > λ _h ≥ 0, as the union of a λ₁-dimensional space, λ₂-dimensional space, ..., λ _h -dimensional space, which all are pairwise disjoint. We present in this article a weighted version of this result. We prove that a weighted -minihyper , with k−1 > λ₁ > λ₂ > ... > λ _h ≥ 0, is a sum of a λ₁-dimensional space, λ₂-dimensional space, ..., and λ _h -dimensional space. This research was supported by the Project Combined algorithmic and theoretical study of combinatorial structures between the Fund for Scientific Research Flanders-Belgium (FWO-Flanders) and the Bulgarian Academy of Sciences. This research is also part of the FWO-Flanders project nr. G.0317.06 Linear codes and cryptography.     

Blocking sets and semifields

We find a relationship between semifield spreads of PG(3,q), small Rédei minimal blocking sets of PG(2,q²), disjoint from a Baer subline of a Rédei line, and translation ovoids of the hermitian surface H(3,q²).     

Proof of a conjecture of Metsch

In this paper we prove a conjecture of Metsch about the maximum number of lines intersecting a pointset in PG(2,q), presented at the conference “Combinatorics 2002”. As a consequence, we give a short proof of the famous Jamison, Brouwer and Schrijver bound on the size of the smallest affine blocking set in AG(2,q).     

Small weight codewords in the codes arising from Desarguesian projective planes

We study codewords of small weight in the codes arising from Desarguesian projective planes. We first of all improve the results of K. Chouinard on codewords of small weight in the codes arising from PG(2, p), p prime. Chouinard characterized all the codewords up to weight 2p in these codes. Using a particular basis for this code, described by Moorhouse, we characterize all the codewords of weight up to 2p + (p−1)/2 if p ≥ 11. We then study the codes arising from . In particular, for q ₀ = p prime, p ≥ 7, we prove that the codes have no codewords with weight in the interval [q + 2, 2q − 1]. Finally, for the codes of PG(2, q), q = p ^h , p prime, h ≥ 4, we present a discrete spectrum for the weights of codewords with weights in the interval [q + 2, 2q − 1]. In particular, we exclude all weights in the interval [3q/2, 2q − 1]. Geertrui Van de Voorde research is supported by the Institute for the Promotion of Innovation through Science and Technology in Flanders (IWT-Vlaanderen) Joost Winne was supported by the Fund for Scientific Research - Flanders (Belgium).     

On the code generated by the incidence matrix of points and hyperplanes in <Emphasis Type=Italic>PG</Emphasis>(<Emphasis Type=Italic>n</Emphasis>,<Emphasis Type=Italic>q</Emphasis>) and its dual

In this paper, we study the p-ary linear code C(PG(n,q)), q = p ^h , p prime, h ≥ 1, generated by the incidence matrix of points and hyperplanes of a Desarguesian projective space PG(n,q), and its dual code. We link the codewords of small weight of this code to blocking sets with respect to lines in PG(n,q) and we exclude all possible codewords arising from small linear blocking sets. We also look at the dual code of C(PG(n,q)) and we prove that finding the minimum weight of the dual code can be reduced to finding the minimum weight of the dual code of points and lines in PG(2,q). We present an improved upper bound on this minimum weight and we show that we can drop the divisibility condition on the weight of the codewords in Sachar’s lower bound (Geom Dedicata 8:407–415, 1979). G. Van de Voorde’s research was supported by the Institute for the Promotion of Innovation through Science and Technology in Flanders (IWT-Vlaanderen).     

Protectionism and blocking power indices

We study here the protectionist role of blocking coalitions in a voting game. More precisely, we first present necessary properties that a family of coalitions must satisfy in order to be the blocking family of some game and show that they are sufficient conditions too. Furthermore, a procedure to determine all games having a given blocking family is provided. With regard to uniqueness and multiplicity, (a) the blocking families that univocally determine the game are characterized by means of a separation condition, and (b) it is shown that in the nonseparating case at least three games share each nonempty blocking family, and an upper bound is given for the number of such games. Some numerical examples illustrate our results. Finally, power indices related to the blocking structure are discussed. Research partially supported by Grant SGR 2005–00651 of the Catalonia Government and Grant MTM 2006–06064 of the Education and Science Spanish Ministry and the European Regional Development Fund.     

Lower bounds for the cardinality of minimal blocking sets in projective spaces

In this paper new lower bounds for the cardinality of minimal m-blocking sets are determined. Let r₂(q) be the number such that q+r₂(q)+1 is the cardinality of the smallest non-trivial line-blocking set in a plane of order q. If B is a minimal m-blocking set in PG(n,q) that contains at most q^m+q^m−1+…+q+1+r₂(q)·(∑_i=2m−n′^m−1qⁱ) points for an integer n′ satisfying mn′2m, then the dimension of B is at most n′. If the dimension of B is n′, then the following holds. The cardinality of B equals q^m+q^m−1+…+q+1+r₂(q)(∑_i=2m−n′^m−1qⁱ). For n′=m the set B is an m-dimensional subspace and for n′=m+1 the set B is a cone with an (m−2)-dimensional vertex over a non-trivial line-blocking set of cardinality q+r₂(q)+1 in a plane skew to the vertex. This result is due to Heim (Mitt. Math. Semin. Giessen 226 (1996), 4–82). For n′>m+1 and q not a prime the number q is a square and for q16 the set B is a Baer cone. If q is odd and |B|<q^m+q^m−1+…+q+1+r₂(q)(q^m−1+q^m−2), it follows from this result that the subspace generated by B has dimension at most m+1. Furthermore we prove that in this case, if , then B is an m-dimensional subspace or a cone with an (m−2)-dimensional vertex over a non-trivial line-blocking set of cardinality q+r₂(q)+1 in a plane skew to the vertex. For q=p^3h, p7 and q not a square we show this assertion for |B|q^m+q^m−1+…+q+1+q^2/3·(q^m−1+…+1).     

On small blocking sets and their linearity

We prove that a small minimal blocking set of PG(2,q) is “very close” to be a linear blocking set over some subfield GF(pe)<GF(q). This implies that (i) a similar result holds in PG(n,q) for small minimal blocking sets with respect to k-dimensional subspaces (0?k?n) and (ii) most of the intervals in the interval-theorems of Sz?nyi and Sz?nyi-Weiner are empty.     

Large Deviations of the Finite Cluster Shape for Two-Dimensional Percolation in the Hausdorff and L1 Metric

We consider supercritical two-dimensional Bernoulli percolation. Conditionally on the event that the open cluster C containing the origin is finite, we prove that: the laws of C/N satisfy a large deviations principle with respect to the Hausdorff metric; let f(N) be a function from to such that f(N)/ln N+ and f(N)/N0 as N goes to the laws of {x ² : d(x, C)f(N)}/N satisfy a large deviations principle with respect to the L ¹ metric associated to the planer Lebesgue measure. We link the second large deviations principle with the Wulff construction.     

集合概念的扩张与完善

从集合概念的内涵出发,剖析了单值集——Cantor集合、Fuzzy集合、Rough集合、可拓集合概念的内涵;剖析了复值集——Grey集合、未确知集合、Vague集合、泛灰(UG)集合和广义泛灰(GUG)集合的内涵;从而得出广义泛灰集合是内涵最深的集合概念;它具有极强的描述能力,可以描述客观存在的一切现象,故又是外延最广的集合概念.     

Sparse and slender subsets of monoids

We generalize the notions of sparse and slender sets for an arbitrary monoid and characterize the unambiguous rational sets which are sparse or slender.