On the Gorensteinness of broken circuit complexes and Orlik–Terao ideals

It is proved that the broken circuit complex of an ordered matroid is Gorenstein if and only if it is a complete intersection. Several characterizations for a matroid that admits such an order are then given, with particular interest in the h-vector of broken circuit complexes of the matroid. As an application, we prove that the Orlik–Terao algebra of a hyperplane arrangement is Gorenstein if and only if it is a complete intersection. Interestingly, our result shows that the complete intersection property (and hence the Gorensteinness as well) of the Orlik–Terao algebra can be determined from the last two nonzero entries of its h-vector.     

The max-flow min-cut property of two-dimensional affine convex geometries

In a matroid, (X,e) is a rooted circuit if X is a set not containing element e and X∪{e} is a circuit. We call X a broken circuit of e. A broken circuit clutter is the collection of broken circuits of a fixed element. Seymour [The matroids with the max-flow min-cut property, J. Combinatorial Theory B 23 (1977) 189-222] proved that a broken circuit clutter of a binary matroid has the max-flow min-cut property if and only if it does not contain a minor isomorphic to Q₆. We shall present an analogue of this result in affine convex geometries. Precisely, we shall show that a broken circuit clutter of an element e in a convex geometry arising from two-dimensional point configuration has the max-flow min-cut property if and only if the configuration has no subset forming a ‘Pentagon’ configuration with center e.Firstly we introduce the notion of closed set systems. This leads to a common generalization of rooted circuits both of matroids and convex geometries (antimatroids). We further study some properties of affine convex geometries and their broken circuit clutters.     

Chords and disjoint paths in matroids

A chord of a circuit C of a matroid M on E is a cell e ? S\C such that C spans e. Menger's theorem gives necessary and sufficient conditions for a cell of a graphic matroid to be a chord of some circuit. We extend this result to a large class of matroids and find all minimal counterexamples. The theorem is used to obtain results on disjoint paths and to characterize a class of matroid sums.     

Transversal theory and F-products

We characterize the matroid dual to a transversal matroid. We also show that Richard Rado's condition for the existence of an independent transversal can be weakened.     

Matroids with a unique non-common circuit containing a fixed element

In this paper, we define a matroid operation that generalizes the circuit-hyperplane relaxation. This operation is used to characterize when a pair of connected matroids over the same ground set have exactly one non-common circuit containing a fixed element.     

The biased graphs whose matroids are binary

A biased graph Φ consists of a graph and a class of distinguished polygons such that no theta subgraph contains exactly two distinguished polygons. There are three matroids naturally associated with Φ: the bias matroid G(Φ), the lift matroid L(Φ), and the complete lift L₀(Φ). We characterize those Φ for which any of these matroids is binary.     

The circuit basis in binary matroids

The concept of a circuit basis for a matroid is introduced, as an algorithmically rapid way of determining several characteristics of a given matroid. It is used to give a short search for planarity in graphs, and also to begin the answer to a question of G.-C. Rota about “dependency among dependencies.” A circuit basis for a matroid is a least set of circuits which will generate all the circuits of the matroid by repeated use of symmetric differences of cells.     

The Euler circuit theorem for binary matroids

It is proved that, if M is a binary matroid, then every cocircuit of M has even cardinality if and only if M can be obtained by contracting some other binary matroid M⁺ onto a single circuit. This is the natural analog of the Euler circuit theorem for graphs. It is also proved that every coloop-free matroid can be obtained by contracting some other matroid (not in general binary) onto a single circuit.     

On the intersections of circuits and cocircuits in matroids

Seymour has shown that a matroid has a triad, that is, a 3-element set which is the intersection of a circuit and a cocircuit, if and only if it is non-binary. In this paper we determine precisely when a matroidM has a quad, a 4-element set which is the intersection of a circuit and a cocircuit. We also show that this will occur ifM has a circuit and a cocircuit meeting in more than four elements. In addition, we prove that if a 3-connected matroid has a quad, then every pair of elements is in a quad. The corresponding result for triads was proved by Seymour.     

On the number of circuit–cocircuit reversal classes of an oriented matroid

The first author introduced the circuit–cocircuit reversal system of an oriented matroid, and showed that when the underlying matroid is regular, the cardinalities of such system and its variations are equal to special evaluations of the Tutte polynomial (e.g., the total number of circuit–cocircuit reversal classes equals $t(M;1,1)$, the number of bases of the matroid). By relating these classes to activity classes studied by the first author and Las Vergnas, we give an alternative proof of the above results and a proof of the converse statements that these equalities fail whenever the underlying matroid is not regular. Hence we extend the above results to an equivalence of matroidal properties, thereby giving a new characterization of regular matroids.     

Characterizing binary simplical matroids

In an earlier paper we defined a class of matroids whose circuit are combinatorial generalizations of simple polytopes; these matroids are the binary analogue of the simplical geometrics of Crapo and Rota. Here we find necessary and sufficient conditions for a matroid to be isomorphic to such a binary simplical matroid.     

Ideal secret sharing schemes whose minimal qualified subsets have at most three participants

One of the main open problems in secret sharing is the characterization of the access structures of ideal secret sharing schemes. Brickell and Davenport proved that every one of these ideal access structures is related in a certain way to a unique matroid. Specifically, they are matroid ports. In addition to the search of general results, this difficult open problem has been studied in previous works for several families of access structures. In this paper we do the same for access structures with rank 3, that is, structures whose minimal qualified subsets have at most three participants. We completely characterize and classify the rank-3 access structures that are matroid ports. We prove that all access structures with rank three that are ports of matroids greater than 3 are ideal. After the results in this paper, the only open problem in the characterization of the ideal access structures with rank three is to characterize the rank-3 matroids that can be represented by an ideal secret sharing scheme. A previous version of this paper appeared in Fifth Conference on Security and Cryptography for Networks, SCN 2006, Lecture Notes in Computer Science 4116 (2006) 201–215.     

A rough set approach to the characterization of transversal matroids

Rough sets are efficient for data pre-processing during data mining. However, some important problems such as attribute reduction in rough sets are NP-hard and the algorithms required to solve them are mostly greedy ones. The transversal matroid is an important part of matroid theory, which provides well-established platforms for greedy algorithms. In this study, we investigate transversal matroids using the rough set approach. First, we construct a covering induced by a family of subsets and we propose the approximation operators and upper approximation number based on this covering. We present a sufficient condition under which a subset is a partial transversal, and also a necessary condition. Furthermore, we characterize the transversal matroid with the covering-based approximation operator and construct some types of circuits. Second, we explore the relationships between closure operators in transversal matroids and upper approximation operators based on the covering induced by a family of subsets. Finally, we study two types of axiomatic characterizations of the covering approximation operators based on the set theory and matroid theory, respectively. These results provide more methods for investigating the combination of transversal matroids with rough sets.     

Some Remarks on Korn Inequalities

A recent joint paper with Doina Cioranescu and Julia Orlik was concerned with the homogenization of a linearized elasticity problem with inclusions and cracks(see[Cioranescu, D., Damlamian, A. and Orlik, J., Homogenization via unfolding in periodic elasticity with contact on closed and open cracks, Asymptotic Analysis, 82, 2013, 201–232]). It required uniform estimates with respect to the homogenization parameter. A Korn inequality was used which involves unilateral terms on the boundaries where a nopenetration condition is imposed. In this paper, the author presents a general method to obtain many diverse Korn inequalities including the unilateral inequalities used in [Cioranescu, D., Damlamian, A. and Orlik, J., Homogenization via unfolding in periodic elasticity with contact on closed and open cracks, Asymptotic Analysis, 82, 2013, 201–232]. A preliminary version was presented in [Damlamian, A., Some unilateral Korn inequalities with application to a contact problem with inclusions, C. R. Acad. Sci. Paris, Ser. I,350, 2012, 861–865].     

Bounding the beta invariant of 3-connected matroids

The beta invariant is related to the Chromatic and Tutte Polynomials and has been studied by Crapo [4], Brylawski [2], Oxley [7] and others. Crapo [4] showed that a matroid with at least two elements is connected if and only if its beta invariant is greater than zero. Brylawski [2] showed that a connected matroid has beta invariant one if and only if M is isomorphic to a serial-parallel network. Oxley [7] characterized all matroids with beta invariant two, three and four. In this paper, we first give a best possible lower bound on the beta invariant of 3-connected matroids, then we characterize all 3-connected matroids attaining the lower bound. We also characterize all binary matroids with beta invariant 5, 6, and 7.     

Homological properties of Orlik–Solomon algebras

The Orlik–Solomon algebra of a matroid can be considered as a quotient ring over the exterior algebra E. At first, we study homological properties of E-modules as e.g., complexity, depth and regularity. In particular, we consider modules with linear injective resolutions. We apply our results to Orlik–Solomon algebras of matroids and give formulas for the complexity, depth and regularity of such rings in terms of invariants of the matroid. Moreover, we characterize those matroids whose Orlik–Solomon ideal has a linear projective resolution and compute in these cases the Betti numbers of the ideal.     

Concentration inequalities for nonlinear matroid intersection

In this work we propose new randomized rounding algorithms for matroid intersection and matroid base polytopes. We prove concentration inequalities for polynomial objective functions and constraints that has numerous applications and can be used in approximation algorithms for Minimum Quadratic Spanning Tree, Unrelated Parallel Machines Scheduling and scheduling with time windows and nonlinear objectives. We also show applications related to Constraint Satisfaction and dense polynomial optimization. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 541–571, 2015     

A note on Tutte polynomials and Orlik–Solomon algebras

Let be a (central) arrangement of hyperplanes in and the dependence matroid of the linear forms . The Orlik–Solomon algebra of a matroid is the exterior algebra on the points modulo the ideal generated by circuit boundaries. The graded algebra is isomorphic to the cohomology algebra of the manifold . The Tutte polynomial is a powerful invariant of the matroid . When is a rank 3 matroid and the θ_Hi are complexifications of real linear forms, we will prove that determines . This result partially solves a conjecture of Falk.     

Rainbow and monochromatic circuits and cocircuits in binary matroids

Given a matroid together with a coloring of its ground set, a subset of its elements is called rainbow colored if no two of its elements have the same color. We show that if an n-element rank r binary matroid M is colored with exactly r colors, then M either contains a rainbow colored circuit or a monochromatic cocircuit. As the class of binary matroids is closed under taking duals, this immediately implies that if M is colored with exactly $n?r$ colors, then M either contains a rainbow colored cocircuit or a monochromatic circuit. As a byproduct, we give a characterization of binary matroids in terms of reductions to partition matroids.Motivated by a conjecture of Bérczi, Schwarcz and Yamaguchi, we also analyze the relation between the covering number of a binary matroid and the maximum number of colors or the maximum size of a color class in any of its rainbow circuit-free colorings. For simple graphic matroids, we show that there exists a rainbow circuit-free coloring that uses each color at most twice only if the graph is $(2,3)$-sparse, that is, it is independent in the 2-dimensional rigidity matroid. Furthermore, we give a complete characterization of minimally rigid graphs admitting such a coloring.