Matroid representation of clique complexes

In this paper, we approach the quality of a greedy algorithm for the maximum weighted clique problem from the viewpoint of matroid theory. More precisely, we consider the clique complex of a graph (the collection of all cliques of the graph) which is also called a flag complex, and investigate the minimum number k such that the clique complex of a given graph can be represented as the intersection of k matroids. This number k can be regarded as a measure of “how complex a graph is with respect to the maximum weighted clique problem” since a greedy algorithm is a k-approximation algorithm for this problem. For any k>0, we characterize graphs whose clique complexes can be represented as the intersection of k matroids. As a consequence, we can see that the class of clique complexes is the same as the class of the intersections of partition matroids. Moreover, we determine how many matroids are necessary and sufficient for the representation of all graphs with n vertices. This number turns out to be n-1. Other related investigations are also given.     

Symplectic Matroids

A symplectic matroid is a collection B of k-element subsets of J = {1, 2, ..., n, 1*, 2*, ...; n*}, each of which contains not both of i and i* for every i n, and which has the additional property that for any linear ordering of J such that i j implies j* i* and i j* implies j i* for all i, j n, B has a member which dominates element-wise every other member of B. Symplectic matroids are a special case of Coxeter matroids, namely the case where the Coxeter group is the hyperoctahedral group, the group of symmetries of the n-cube. In this paper we develop the basic properties of symplectic matroids in a largely self-contained and elementary fashion. Many of these results are analogous to results for ordinary matroids (which are Coxeter matroids for the symmetric group), yet most are not generalizable to arbitrary Coxeter matroids. For example, representable symplectic matroids arise from totally isotropic subspaces of a symplectic space very similarly to the way in which representable ordinary matroids arise from a subspace of a vector space. We also examine Lagrangian matroids, which are the special case of symplectic matroids where k = n, and which are equivalent to Bouchet's symmetric matroids or 2-matroids.     

Harmonic conjugation in harmonic matroids

We study a generalization of the concept of harmonic conjugation from projective geometry and full algebraic matroids to a larger class of matroids called harmonic matroids. We use harmonic conjugation to construct a projective plane of prime order in harmonic matroids without using the axioms of projective geometry. As a particular case we have a combinatorial construction of a projective plane of prime order in full algebraic matroids.     

Linear approximation of approximately biorthogonality preserving maps

We investigate linear properties of mappings from a bounded domain of an n-dimensional normed space into another n-dimensional normed space such that the image of some almost biorthogonal system is almost biorthogonal. In this way we generalize a result of the author on stability of orthogonality in Euclidean spaces.     

Modified linear dependence and the capacity of a cyclic graph

In 1956 Shannon raised a problem in information theory, which amounts to this geometric question: How many n-dimensional cubes of width 2 can be packed in the n-dimensional torus described by the nth power of the cyclic group C_m? The present paper examines this question in the special circumstance that the set of centers of the cubes form a subgroup—that is, a lattice packing. In this case, the machinery of vector spaces is available when m is a prime. This approach introduces a modified definition of linear independence, obtains some known results with its aid, and suggests a promising direction for future computation and theory. The paper concludes by showing that, in return, combinatorial information can yield results about finite vector spaces.     

The multidimensional cube recurrence

We introduce a recurrence which we term the multidimensional cube recurrence, generalizing the octahedron recurrence studied by Propp, Fomin and Zelevinsky, Speyer, and Fock and Goncharov and the three-dimensional cube recurrence studied by Fomin and Zelevinsky, and Carroll and Speyer. The states of this recurrence are indexed by tilings of a polygon with rhombi, and the variables in the recurrence are indexed by vertices of these tilings. We travel from one state of the recurrence to another by performing elementary flips. We show that the values of the recurrence are independent of the order in which we perform the flips; this proof involves nontrivial combinatorial results about rhombus tilings which may be of independent interest. We then show that the multidimensional cube recurrence exhibits the Laurent phenomenon - any variable is given by a Laurent polynomial in the other variables. We recognize a special case of the multidimensional cube recurrence as giving explicit equations for the isotropic Grassmannians IG(n−1,2n). Finally, we describe a tropical version of the multidimensional cube recurrence and show that, like the tropical octahedron recurrence, it propagates certain linear inequalities.     

A matroid invariant via the K-theory of the Grassmannian

Let G(d,n) denote the Grassmannian of d-planes in Cn and let T be the torus n(C^∗)/diag(C^∗) which acts on G(d,n). Let x be a point of G(d,n) and let be the closure of the T-orbit through x. Then the class of the structure sheaf of in the K-theory of G(d,n) depends only on which Plücker coordinates of x are nonzero - combinatorial data known as the matroid of x. In this paper, we will define a certain map of additive groups from K^○(G(d,n)) to Z[t]. Letting gx(t) denote the image of , gx behaves nicely under the standard constructions of matroid theory, such as direct sum, two-sum, duality and series and parallel extensions. We use this invariant to prove bounds on the complexity of Kapranov's Lie complexes [M. Kapranov, Chow quotients of Grassmannians I, Adv. Soviet Math. 16 (2) (1993) 29-110], Hacking, Keel and Tevelev's very stable pairs [P. Hacking, S. Keel, E. Tevelev, Compactification of the moduli space of hyperplane arrangements, J. Algebraic Geom. 15 (2006) 657-680] and the author's tropical linear spaces when they are realizable in characteristic zero [D. Speyer, Tropical linear spaces, SIAM J. Discrete Math. 22 (4) (2008) 1527-1558]. Namely, in characteristic zero, a Lie complex or the underlying (d−1)-dimensional scheme of a very stable pair can have at most strata of dimensions n−i and d−i, respectively. This prove the author's f-vector conjecture, from [D. Speyer, Tropical linear spaces, SIAM J. Discrete Math. 22 (4) (2008) 1527-1558], in the case of a tropical linear space realizable in characteristic 0.     

Minimal non-orientable matroids in a projective plane

We construct a new family of minimal non-orientable matroids of rank three. Some of these matroids embed in Desarguesian projective planes. This answers a question of Ziegler: for every prime power q, find a minimal non-orientable submatroid of the projective plane over the q-element field.     

Bases in semilinear spaces over join-semirings

This paper investigates the cardinality of a basis in semilinear spaces of n-dimensional vectors over join-semirings. First, it introduces the notion of an irredundant decomposition of an element in a join-semiring, then discusses the cardinality of a basis and proves that the cardinality of each basis is n if and only if the multiplicative identity element 1 is join-irreducible. If 1 is not a join-irreducible element then each basis need not have the same number of elements in semilinear spaces of n-dimensional vectors over join-semirings. This gives an answer to an open problem raised by Di Nola et al. in their work [Algebraic analysis of fuzzy systems, Fuzzy Sets and Systems 158 (2007) 1-22].     

On linear spaces and matroids of arbitrary cardinality

In this paper, we study linear spaces of arbitrary finite dimension on some (possibly infinite) set. We interpret linear spaces as simple matroids and study the problem of erecting some linear space of dimension n to some linear space of dimension n + 1 if possible. Several examples of some such erections are studied; in particular, one of these erections is computed within some infinite iteration process.Dedicated to the memory of Gian-Carlo Rota     

Infinite matroids in graphs

It has recently been shown that infinite matroids can be axiomatized in a way that is very similar to finite matroids and permits duality. This was previously thought impossible, since finitary infinite matroids must have non-finitary duals.In this paper we illustrate the new theory by exhibiting its implications for the cycle and bond matroids of infinite graphs. We also describe their algebraic cycle matroids, those whose circuits are the finite cycles and double rays, and determine their duals. Finally, we give a sufficient condition for a matroid to be representable in a sense adapted to infinite matroids. Which graphic matroids are representable in this sense remains an open question.     

基于覆盖上近似算子的拟阵结构及其关系

Covering-based rough sets,as a technique of granular computing,can be a useful tool for dealing with inexact,uncertain or vague knowledge in information systems.Matroids generalize linear independence in vector spaces,graph theory and provide well established platforms for greedy algorithm design.In this paper,we construct three types of matroidal structures of covering-based rough sets.Moreover,through these three types of matroids,we study the relationships among these matroids induced by six types of covering-based upper approximation operators.First,we construct three families of sets by indiscernible neighborhoods,neighborhoods and close friends,respectively.Moreover,we prove that they satisfy independent set axioms of matroids.In this way,three types of matroidal structures of covering-based rough sets are constructed.Secondly,we study some characteristics of the three types of matroid,such as dependent sets,circuits,rank function and closure.Finally,by comparing independent sets,we study relationships among these matroids induced by six types of covering-based upper approximation operators.     

Isotropic subspaces in symmetric composition algebras and Kummer subspaces in central simple algebras of degree 3

The maximal isotropic subspaces in split Cayley algebras were classified by van der Blij and Springer in Nieuw Archief voor Wiskunde VIII(3):158–169, 1960. Here we translate this classification to arbitrary composition algebras. We study intersection properties of such spaces in a symmetric composition algebra, and prove two triality results: one for two-D isotropic spaces, and another for isotropic vectors and maximal isotropic spaces. We bound the distance between isotropic spaces of various dimensions, and study the strong orthogonality relation on isotropic vectors, with its own bound on the distance. The results are used to classify maximal p-central subspaces in central simple algebras of degree p = 3. We prove various linkage properties of maximal p-central spaces and p-central elements. Analogous results are obtained for symmetric p-central elements with respect to an involution of the second kind inverting a third root of unity.     

Standard orthogonal vectors in semilinear spaces and their applications

This paper investigates the standard orthogonal vectors in semilinear spaces of n-dimensional vectors over commutative zerosumfree semirings. First, we discuss some characterizations of standard orthogonal vectors. Then as applications, we obtain some necessary and sufficient conditions that a set of vectors is a basis of a semilinear subspace which is generated by standard orthogonal vectors, prove that a set of linearly independent nonstandard orthogonal vectors cannot be orthogonalized if it has at least two nonzero vectors, and show that the analog of the Kronecker–Capelli theorem is valid for systems of equations.     

Global existence and asymptotic behavior of solutions for a semi-linear wave equation

In this paper, we investigate the initial value problem for a semi-linear wave equation in n-dimensional space. Based on the decay estimate of solutions to the corresponding linear equation, we define a set of time-weighted Sobolev spaces. Under small condition on the initial value, we prove the global existence and asymptotic behavior of the solution in the corresponding Sobolev spaces by the contraction mapping principle.     

On finite matroids with two more hyperplanes than points

One of the most interesting results about finite matroids of finite rank and generalized projective spaces is the result of Basterfield, Kelly and Green (1968/1970) (J.G. Basterfield, L.M. Kelly, A characterization of sets of n points which determine n hyperplanes, in: Proceedings of the Cambridge Philosophical Society, vol. 64, 1968, pp. 585-588; C. Greene, A rank inequality for finite geometric lattices, J. Combin Theory 9 (1970) 357-364) affirming that any matroid contains at least as many hyperplanes as points, with equality in the case of generalized projective spaces. Consequently, the goal is to characterize and classify all matroids containing more hyperplanes than points. In 1996, I obtained the classification of all finite matroids containing one more hyperplane than points. In this paper a complete classification of finite matroids with two more hyperplanes than points is obtained. Moreover, a partial contribution to the classification of those matroids containing a certain number of hyperplanes more than points is presented.     

Model-theory of vector-spaces over unspecified fields

Vector spaces over unspecified fields can be axiomatized as one-sorted structures, namely, abelian groups with the relation of parallelism. Parallelism is binary linear dependence. When equipped with the n-ary relation of linear dependence for some positive integer n, a vector-space is existentially closed if and only if it is n-dimensional over an algebraically closed field. In the signature with an n-ary predicate for linear dependence for each positive integer n, the theory of infinite-dimensional vector spaces over algebraically closed fields is the model-completion of the theory of vector spaces.