A Hamada type characterization of the classical geometric designs

The dimension of a combinatorial design ${{\mathcal D}}$ over a finite field F = GF(q) was defined in (Tonchev, Des Codes Cryptogr 17:121–128, 1999) as the minimum dimension of a linear code over F that contains the blocks of ${{\mathcal D}}$ as supports of nonzero codewords. There it was proved that, for any prime power q and any integer n ≥ 2, the dimension over F of a design ${{\mathcal D}}$ that has the same parameters as the complement of a classical point-hyperplane design PG _n-1(n, q) or AG _n-1(n, q) is greater than or equal to n + 1, with equality if and only if ${{\mathcal D}}$ is isomorphic to the complement of the classical design. It is the aim of the present paper to generalize this Hamada type characterization of the classical point-hyperplane designs in terms of associated codes over F = GF(q) to a characterization of all classical geometric designs PG _d (n, q), where 1 ≤ d ≤ n ? 1, in terms of associated codes defined over some extension field E?=?GF(q ^t ) of F. In the affine case, we conjecture an analogous result and reduce this to a purely geometric conjecture concerning the embedding of simple designs with the parameters of AG _d (n, q) into PG(n, q). We settle this problem in the affirmative and thus obtain a Hamada type characterization of AG _d (n, q) for d = 1 and for d > (n ? 2)/2.     

On complexity of three-dimensional hyperbolic manifolds with geodesic boundary

The nonintersecting classes ? _p,q are defined, with p, q ?? ? and p ?? q ?? 1, of orientable hyperbolic 3-manifolds with geodesic boundary. If M ?? ? _p,q , then the complexity c(M) and the Euler characteristic ??(M) of M are related by the formula c(M) = p???(M). The classes ? _q,q , q ?? 1, and ?_2,1 are known to contain infinite series of manifolds for each of which the exact values of complexity were found. There is given an infinite series of manifolds from ?_3,1 and obtained exact values of complexity for these manifolds. The method of proof is based on calculating the ?-invariants of manifolds.     

An Erd?s-Gallai Theorem for Matroids

Erdős and Gallai showed that for any simple graph with n vertices and circumference c it holds that | E(G) | ￡ \frac12(n - 1)c{{{\mid}{E(G)}{\mid} \leq {\frac{1}{2}}(n - 1)c}}. We extend this theorem to simple binary matroids having no F ₇-minor by showing that for such a matroid M with circumference c(M) ≥  3 it holds that | E(M) | ￡ \frac12r(M)c(M){{{\mid}{E(M)}{\mid} \leq {\frac{1}{2}}r(M)c(M)}}.     

The Einstein-Kähler metric on the third Cartan-Hartogs domain

In this paper we discuss the Einstein-Kahler metric on the third Cartan-Hartogs domain Y111（n, q; K）. Firstly we get the complete Einstein Kahler metric with explicit form on Y111（n, q; K） in the case of K=q/2 ＋ 1/q-1. Secondly we obtain the holomorphic sectional curvature under this metric and get the sharp estimate for this holomorphic curvature. Finally we prove that the complete Einstein-Kahler metric is equivalent to the Bergman metric on Y111（n, q; K） in case of K=q/2＋1/q-1.     

Configurations in projective planes and quadrilateral-star Ramsey numbers

Some classes of configurations in projective planes with polarity are constructed. As the main result, lower bounds for the Ramsey numbers r(n)=r(C₄;K_1,n) are derived from these geometric structures, which improve some bounds due to Parsons about 30 years ago, and also yield a new class of optimal values: r(q²-2q+1)=q²-q+1 whenever q is a power of 2. Moreover, the constructions also imply a known result on C₄-K_1,n bipartite Ramsey numbers.     

On the semiproportional character conjecture in groups Sp<Subscript>4</Subscript>(<Emphasis Type="Italic">q</Emphasis>)

Previously, the author made the following conjecture: if a finite group has two semiproportional irreducible characters φ and ψ, then φ(1) = ψ(1). In the present paper, a new confirmation of the conjecture is obtained. Namely, the conjecture is verified for symplectic groups Sp₄(q) and PSp₄(q).     

Diameters of finite upper half plane graphs

Let GF(q) be a finite field of q elements. Let G denote the group of matrices M(x, y) = (^{y x}_{0 1}) over GF(q) with y ≠ 0. Fix an irreducible polynomial For each a ϵ GF(q), let X_a be the graph whose vertices are the q² − q elements of G, with two vertices M(x, y), M(v, w) joined by an edge if and only if The graphs X_a with a ϵ/ {0, t² − 4n} are (q + 1)-regular connected graphs which have received recent attention, as they've been shown to be Ramanujan graphs. We determine the diameter of these graphs X_a. © 1996 John Wiley & Sons, Inc.     

Near-MDS codes arising from algebraic curves

Every elliptic quartic Γ₄ of PG(3,q) with nGF(q)-rational points provides a near-MDS code C of length n and dimension 4 such that the collineation group of Γ₄ is isomorphic to the automorphism group of C. In this paper we assume that GF(q) has characteristic p>3. We classify the linear collineation groups of PG(3,q) which can preserve an elliptic quartic of PG(3,q). Also, we prove for q?113 that if the j-invariant of Γ₄ does not disappear, then C cannot be extended in a natural way by adding a point of PG(3,q) to Γ₄.     

On Maximum-sized k-Regular Matroids

 Let k be an integer exceeding one. The class of k-regular matroids is a generalization of the classes of regular and near-regular matroids. A simple rank-r regular matroid has the maximum number of points if and only if it is isomorphic to M(K _r+1), the cycle matroid of the complete graph on r+1 vertices. A simple rank-r near-regular matroid has the maximum number of points if and only if it is isomorphic to the simplification of , that is, the simplification of the matroid obtained, geometrically, by freely adding a point to a 3-point line of M(K _r+2) and then contracting this point. This paper determines the maximum number of points that a simple rank-r k-regular matroid can have and determines all such matroids having this number. With one exception, there is exactly one such matroid. This matroid is isomorphic to the simplification of , that is, the simplification of the matroid obtained, geometrically, by freely adding k independent points to a flat of M(K _r+k+1) isomorphic to M(K _k+2) and then contracting each of these points. Revised: July 27, 1998     

A Note on MDS Codes, <Emphasis Type="Italic">n</Emphasis>-Arcs and Complete Designs

A generalized incidence matrix of a design over GF(q) is any matrix obtained from the (0, 1)-incidence matrix by replacing ones with nonzero elements from GF(q). The dimension d _q of a design D over GF(q) is defined as the minimum value of the q-rank of a generalized incidence matrix of D. It is proved that the dimension d _q of the complete design on n points having as blocks all w-subsets, is greater that or equal to n ? w + 1, and the equality d _q = n ? w + 1 holds if and only if there exists an [n, n ? w + 1, w] MDS code over GF(q), or equivalently, an n-arc in PG(w ? 2, q).     

Thompson’s conjecture for Lie type groups E 7(q)

In this article, we prove a conjecture of Thompson for an infinite class of simple groups of Lie type E ₇(q). More precisely, we show that every finite group G with the properties Z(G) = 1 and cs(G) = cs(E ₇(q)) is necessarily isomorphic to E ₇(q), where cs(G) and Z(G) are the set of lengths of conjugacy classes of G and the center of G respectively.     

Properly coloured Hamiltonian cycles in edge-coloured complete graphs

Let K ^c _n be an edge-coloured complete graph on n vertices. Let Δ_mon(K^c _n) denote the largest number of edges of the same colour incident with a vertex of K^c _n. A properly coloured cycleis a cycle such that no two adjacent edges have the same colour. In 1976, BollobÁs and Erd?s[6] conjectured that every K^c _n with Δ_mon(K^c _n)<?n/2?contains a properly coloured Hamiltonian cycle. In this paper, we show that for any ε>0, there exists an integer n₀ such that every K^c _n with Δ_mon(K^c _n)<(1/2–ε)n and n≥n₀ contains a properly coloured Hamiltonian cycle. This improves a result of Alon and Gutin [1]. Hence, the conjecture of BollobÁs and Erd?s is true asymptotically.     

Character tables of the association schemes coming from the action of G 2(q) on hyperplanes of type O 6 ε (q)

The character tables of the commutative association schemes coming from the action of the Chevalley group G ₂(q) on the set Ω _ε of hyperplanes of type O ₆ ^ε (q) in the seven dimensional orthogonal geometry over GF(q) related to the orthogonal group O ₇(q) are constructed by modifying the character tables of the association schemes obtained from the action of O ₇(q) on Ω _ε .     

Quadratic Double Circulant Codes over Fields

A generalization of the Pless symmetry codes to different fields is presented. In particular new infinite families of self-dual codes over GF(4), GF(5), GF(7), and GF(9) are introduced. It is proven that the automorphism group of some of these codes contains the group PSL₂(q). New codes over GF(4) and GF(5), with better minimum weight than previously known codes, are given.     

To what extent is a large space of matrices not closed under product?

Let (K) be a field. Given an arbitrary linear subspace V of M_n(K) of codimension less than n-1, a classical result states that V generates the (K)-algebra M_n(K). Here, we strengthen this statement in three ways: we show that M_n(K) is spanned by the products of the form AB with (A,B)∈V²; we prove that every matrix in M_n(K) can be decomposed into a product of matrices of V; finally, when V is a linear perplane of M_n(K) and n>2, we show that every matrix in M_n(K) is a product of two elements of V.     

Factorization of Q(h(T)(x)) over a finite field where Q(x) is irreducible and h(T)(x) is linear—I

Let GF(q) be the finite field of order q, let Q(x) be an irreducible polynomial in GF(q)(x), and let h(T)(x) be a linear polynomial in GF(q)[x], where T:x→x^q. We use properties of the linear operator h(T) to give conditions for Q(h(T)(x)) to have a root of arbitrary degree k over GF(q), and we describe how to count the irreducible factors of Q(h(T)(x)) of degree k over GF(q). In addition we compare our results with those Ore which count the number of irreducible factors belonging to a linear polynomial having index k.     

On the matroids representable over GF(4)

The purpose of this note is to present a counterexample to a conjecture of Kahn and Seymour on the minor-minimal matroids not representable over GF(4).     

Fast Algorithm of Square Rooting in Some Finite Fields of Odd Characteristic

It was proved that the complexity of square root computation in the Galois field GF(3^s), s = 2^kr, is equal to O(M(2^k)M(r)k + M(r) log₂r) + 2^kkr^1+o(1), where M (n) is the complexity of multiplication of polynomials of degree n over fields of characteristics 3. The complexity of multiplication and division in the field GF(3^s) is equal to O(M(2^k)M(r)) and O(M(2^k)M(r)) + r^1+o(1), respectively. If the basis in the field GF(3^r) is determined by an irreducible binomial over GF(3) or is an optimal normal basis, then the summands 2^kkr^1+o(1) and r^1+o(1) can be omitted. For M(n) one may take n log₂nψ(n) where ψ(n) grows slower than any iteration of the logarithm. If k grow and r is fixed, than all the estimates presented here have the form O_r (M (s) log ₂s) = s (log ₂s)²ψ(s).     

On Reid's characterization of the ternary matroids

In this paper we prove a stronger version of a result of Ralph Reid characterizing the ternary matroids (i.e., the matroids representable over the field of 3 elements, GF(3)). In particular, we prove that a matroid is ternary if it has no seriesminor of type L_n for n ≥ 5 (n cells and n circuits, each of size n ? 1), and no series-minor of type $\text{L}{}_5{}^1$ (dual of L₅), BII (Fano matroid) or BI (dual of type BII). The proof we give does not assume Reid's theorem. Rather we give a direct proof based on the methods (notably the homotopy theorem) developed by Tutte for proving his characterization of regular matroids. Indeed, the steps involved in our proof closely parallel Tutte's proof, but carrying out these steps now becomes much more complicated.     

A linear-algebra problem from algebraic coding theory

Given an m×n matrix M over E=GF(q^t) and an ordered basis A={z₁,…,z_t} for field E over K=GF(q), expand each entry of M into a t×1 vector of coordinates of this entry relative to A to obtain an mt×n matrix M¹ with entries from the field K. Let r=rank(M) and r¹=rank(M¹). We show that r?r¹?min{rt,n}, and we determine the number b(m,n,r,r¹,q,t) of m×n matrices M of rank r over GF(q^t) with associated mt×n matrix M¹ of rank r¹ over GF (q).