Search

We generalize the Tutte polynomial of a matroid to a morphism of matroids via the K-theory of flag varieties. We introduce two different generalizations, and demonstrate that each has its own merits, where the trade-off is between the ease of combinatorics and geometry. One generalization recovers the Las Vergnas Tutte polynomial of a morphism of matroids, which admits a corank-nullity formula and a deletion-contraction recursion. The other generalization does not, but better reflects the geometry of flag varieties.

We propose a combinatorial approach to the following strengthening of Gal's conjecture: $\gamma(\Delta)\ge \gamma(E)$ coefficientwise, where $\Delta$ is a flag homology sphere and $E\subseteq \Delta$ an induced homology sphere of codimension $1$. We provide partial evidence in favor of this approach, and prove a nontrivial nonlinear inequality that follows from the above conjecture, for boundary complexes of flag $d$-polytopes: $h_1(\Delta) h_i(\Delta) \ge (d-i+1)h_{i-1}(\Delta) + (i+1) h_{i+1}(\Delta)$ for all $0\le i\le d$., Comment: 12 pages

We construct four flag-transitive symmetric designs having 96 points, blocks of size 20, and 4 blocks on each point-pair. Moreover we prove that these are the only such designs. Our classification completes the classification of flag-transitive, point-imprimitive, symmetric designs with the (constant) number of blocks on a point-pair at most four.

This article is a contribution to the study of the automorphism groups of 2-(v,k,1) block designs. In particular we look at the unsolvable block transitive automorphism groups of 2-(v,5,1) designs and prove the following theorem. Main TheoremIf a block transitive group of automorphisms of a2-(v,5,1)design is unsolvable, then it is flag transitive.

Ehrenborg introduced a quasi-symmetric function encoding, denoted FP, for the flag f-vector of any finite, graded poset P with 0̂ and 1̂. Stanley observed that FP is a symmetric function whenever P is locally rank-symmetric and asked for conditions under which FP is Schur-positive. We provide formulas for FP for three classes of locally rank-symmetric posets: graded monoid posets, generalized posets of shuffles and noncrossing partition lattices for classical reflection groups. Our flag f-vector expressions for generalized shuffle posets and noncrossing partition lattices exhibit Schur-positivity, while graded monoid posets do not always have Schur-positive flag f-vector.Each of our flag f-vector expressions results from a poset chain decomposition. For the noncrossing partition lattices and shuffle posets, these also yield symmetric chain decompositions (by restriction to 1-chains), shellability and supersolvability results and combinatorial formulae including characteristic polynomial and zeta polynomial. Our (more complicated) flag f-vector expression for graded monoid posets involves Gröbner bases and a weighted notion of Möbius function for the poset of partitions of a multiset and related multiset intersection posets.

The flag geometry Γ=(P,L,I) of a finite projective plane Π of order s is the generalized hexagon of order (s,1) obtained from Π by putting P equal to the set of all flags of Π, by putting L equal to the set of all points and lines of Π, and where I is the natural incidence relation (inverse containment), i.e., Γ is the dual of the double of Π in the sense of H. Van Maldeghem (1998, “Generalized Polygons,” Birkhäuser Verlag, Basel). Then we say that Γ is fully and weakly embedded in the finite projective space PG(d,q) if Γ is a subgeometry of the natural point-line geometry associated with PG(d,q), if s=q, if the set of points of Γ generates PG(d,q), and if the set of points of Γ not opposite any given point of Γ does not generate PG(d,q). In two earlier papers we have shown that the dimension d of the projective space belongs to {6, 7, 8}, that the projective plane Π is Desarguesian, and we have classified the full and weak embeddings of Γ (Γ as above) in the case that there are two opposite lines L, M of Γ with the property that the subspace UL,M of PG(d,q) generated by all lines of Γ meeting either L or M has dimension 6 (which is automatically satisfied if d=6). In the present paper, we partly handle the case d=7; more precisely, we consider for d=7 the case where for all pairs (L,M) of opposite lines of Γ, the subspace UL,M has dimension 7 and where there exist four lines concurrent with L contained in a 4-dimensional subspace of PG(7,q).

The upper bound inequality[formula](0⩽i⩽d/2) is proved for the torich-vector of a rational convexd-dimensional polytope withnvertices. This gives nonlinear inequalities on flag vectors of rational polytopes.

We consider flag-transitive extensions of the dual Petersen graph satisfying one of the following “pathological” properties: (¬ LL ) there are pairs of collinear points incident to more than one line; (¬ T ) there are triples of collinear points not incident to the same plane. We prove that there is just one example satisfying (¬ LL ), with six points and S 6 as its automorphism group, and there are just four examples satisfying (¬ T ), with 18, 16, 32, and 32 points and groups 3 - S 6 , 2 4 - S 5 , 2 5 - S 5 , and 2 5 - A 5 , respectively. The paper is organized as follows. In Section 1 we recall some known results and we explain some motivations of our investigation. The examples we will characterize are described in Section 2. The characterization theorems are stated in Section 3 and proved in Sections 5 and 6. In Section 4 we state some lemmas, to be used in Sections 5 and 6.

The classification of generalized towers of flag-transitive circular extensions of the sporadic A7-geometry is completed by characterizing two flat geometries on 16 points, constructed in terms of the Steiner system S(24, 8, 5), as the flag-transitive circular extensions of the duals of the sporadic A7-geometry and the Neumaier geometry for A8, and then by showing the non-existence of flag-transitive circular extensions of these geometries.

New non desarguesian flag-transitive affine planes of order qn are constructed whenever n⩾3 is an odd integer and qn>27 is a prime power such that qn≡3 (mod 4).

Let P be a d-polytope. For a set of indices S = {1, i2, …, ik}, 0 ⩽ i1 < i2 < … < ik ⩽ d − 1, define a flag of type S to be a chain of faces of P of the form F1 ⊆ F2 ⊆ … ⊆ Fk, where dim Fj = ij, for every j, 1 ⩽ j ⩽ k. The flag number fs(P) is the number of flags of type S of P. Put fø = 1. The sequence (fs(P)) as S ranges over all subsets of {;0, 1, …, d−} (according to some fixed order) is called the flag vector of P.A remarkable recent theorem by Bayer and Billera asserts that the dimension of the real affine space spanned by flag vectors of d-polytopes is cd − 1, where cd is the dth Fibonacci number. We will construct a new family of d-polytopes whose flag vectors affinely span this space. As a consequence, we compute the dimensions of the affine span of flag vectors of several subclasses of d-polytopes. We show how the structure of intervals in face lattices of polytopes affects their flag numbers. Our proofs are by appropriate computations in the incidence algebra of face lattices of polytopes.We study also linear inequalities for the flag numbers and face numbers of d-polytopes, and discuss some connections with the new notion of h-vectors for arbitrary polytopes (R. Stanley, “Enumerative Combinatorics”, Vol. I, Chap. 4, Wadsworth, Monterey, CA, 1986, and Generalized h-vectors, intersection cohomology of toric varieties, and related results, in “Proceedings, Japan-USA Workshop on Commutative Algebra and Combinatorics,” to appear).

A recent paper of O'Reilly Regueiro obtained an explicit upper bound on the number of points of a flag-transitive, point-imprimitive, symmetric design in terms of the number of blocks containing two points. We improve that upper bound and give a complete list of feasible parameter sequences for such designs for which two points lie in at most ten blocks. Classifications are available for some of these parameter sequences.

For any odd prime power q, all (q2−q+1)th roots of unity clearly lie in the extension field Fq6 of the Galois field Fq of q elements. It is easily shown that none of these roots of unity have trace −2, and the only such roots of trace −3 must be primitive cube roots of unity which do not belong to Fq. Here the trace is taken from Fq6 to Fq. Computer based searching verified that indeed −2 and possibly −3 were the only values omitted from the traces of these roots of unity for all odd q⩽200. In this paper we show that this fact holds for all odd prime powers q. As an application, all odd order three-dimensional flag-transitive affine planes admitting a cyclic transitive action on the line at infinity are enumerated.

The flag geometry Γ=(P, L, I) of a finite projective plane Π of order s is the generalized hexagon of order (s, 1) obtained from Π by putting P equal to the set of all flags of Π, by putting L equal to the set of all points and lines of Π, and where I is the natural incidence relation (inverse containment), i.e., Γ is the dual of the double of Π in the sense of H. Van Maldeghem (1998, “Generalized Polygons,” Birkhäuser Verlag, Basel). Then we say that Γ is fully and weakly embedded in the finite projective space PG(d, q) if Γ is a subgeometry of the natural point-line geometry associated with PG(d, q), if s=q, if the set of points of Γ generates PG(d, q), and if the set of points of Γ not opposite any given point of Γ does not generate PG(d, q). In three earlier papers we have shown that the dimension d of the projective space belongs to {6, 7, 8}, that the projective plane Π is Desarguesian, and we have classified the full and weak embeddings of Γ (Γ as above) for d=6 and for d=7 in the case that there exists a line L of Γ and four distinct lines L1, L2, L3, L4 concurrent with Γ which generate a 4-dimensional space. In the present paper, we drop all these additional assumptions by completing the case d=7 and handling the case d=8. In particular, we find new examples for d=8 (contrary to our original conjecture (J. A. Thas and H. Van Maldeghem, Des. Codes Cryptogr.17 (1999), 97–104)). This means that we have now the complete classification of all fully and weakly embedded geometries Γ in PG(d, q), with Γ the flag geometry of a finite projective plane.

We prove that in a finite projective plane P , the thick semiovals admitting a flag-transitive group induced by Aut P are the sets of absolute points of Hermitian polarities.

Only a few classes of square order planes are known. These are generalized Andre planes (including Hall planes), flag transitive planes, Hering's planes and Walker's planes. A new class of planes of order 52r, where r is an odd natural number, is constructed and the translation complements of the corresponding planes have been determined. The translation complements divide the sets of distinguished points into 4 orbits of lengths 1, 1, 5r − 1, and 52r − 5r and it is of order 5r(5r − 1)2 if r ≠ 1. In the particular case of r = 1, the translation complement divides the set of distinguished points into two orbits of lengths 6 and 20 and it is of order 480.

Let S =(P, B, I) be a generalized quadrangle of order (q, q2), q>1, and assume that S satisfies Property (G) at the flag (x, L). If q is odd then S is the dual of a flock generalized quadrangle. This solves (a stronger version of ) a ten-year-old conjecture. We emphasize that this is a powerful theorem as Property (G) is a simple combinatorial property, while a flock generalized quadrangle is concretely described using finite fields and groups. As in several previous theorems it was assumed that the dual of the generalized quadrangle arises from a flock, this can now be replaced, in the odd case, by having Property (G) at some flag. Finally we describe a pure geometrical construction of a generalized quadrangle arising from a flock; until now there was only the construction by Knarr which only worked in the odd case.

Chari proved that if Δ is a (d - 1)-dimensional simplicial complex with a convex ear decomposition, then h0 ≤ ... ≤ h⌊d/2⌋ [M.K. Chari, Two decompositions in topological combinatorics with applications to matroid complexes, Trans. Amer. Math. Soc. 349 (1997) 3925-3943]. Nyman and Swartz raised the problem of whether or not the corresponding g-vector is an M-vector [K. Nyman, E. Swartz, Inequalities for h- and flag h-vectors of geometric lattices, Discrete Comput. Geom. 32 (2004) 533-548]. This is proved to be true by showing that the set of pairs (ω, Θ), where Θ is a l.s.o.p. for k[Δ], the face ring of Δ, and ω is a g-element for k[Δ]/Θ, is nonempty whenever the characteristic of k is zero.Finite buildings have a convex ear decomposition. These decompositions point to inequalities on the flag h-vector of such spaces similar in spirit to those examined in [K. Nyman, E. Swartz, Inequalities for h- and flag h-vectors of geometric lattices, Discrete Comput. Geom. 32 (2004) 533-548] for order complexes of geometric lattices. This also leads to connections between higher Cohen-Macaulay connectivity and conditions which insure that h0 < ... < hi for a predetermined i.

It is shown that conditions stronger in a certain sense than color-shifting cannot be placed on the class of colored complexes without changing the characterization of the flag f-vectors., Comment: 5 pages