Results 121 to 130 of about 4,343 (225)
On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem
Klaus showed that the Oriented Matroid Complementarity Problem (OMCP) can be solved by a reduction to the problem of sink-finding in a unique sink orientation (USO) if the input is promised to be given by a non-degenerate extension of a P-matroid.
Borzechowski, Michaela, Weber, Simon
core +2 more sources
Orthogonal matroids over tracts
Forum of Mathematics, SigmaWe generalize Baker–Bowler’s theory of matroids over tracts to orthogonal matroids, define orthogonal matroids with coefficients in tracts in terms of Wick functions, orthogonal signatures, circuit sets and orthogonal vector sets, and establish basic ...
Tong Jin, Donggyu Kim
doaj +1 more source
Matroid matching with Dilworth truncation
, 2008 Let H = (V, E) be a hypergraph and let k ≥ 1 and l ≥ 0 be fixed integers. Let M be the matroid with ground-set E s.t. a set F ⊆ E is independent if and only if each X ⊆ V with k|X | − l ≥ 0 spans at most k|X | − l hyperedges of F. We prove that if H is
Makai, Márton, Márton Makai
core +1 more source
Semi-streaming algorithms for submodular matroid intersection. [PDF]
Math Program, 2023 Garg P, Jordan L, Svensson O.
europepmc +1 more source
Discrete Mathematics, 1983 AbstractThe purpose of this note is to prove an identity for generalized Tutte-Grothendieck invariants, at least two special cases of which have already proved to be of considerable use. In addition, one of these special cases is used to strengthen results of Lindström on the critical exponent of a representable matroid and the chromatic number of a ...
openaire +2 more sources
Characterizations of Convex spaces and Anti-matroids via Derived Operators
Open Mathematics, 2019 In this paper we use the notion of derived sets to study convex spaces. By axiomatizing the derived sets on convex spaces, we define c-derived operators and restricted c-derived operators. Results show that convex structures can be characterized in terms
Chen Fanhong, Shen Chong
doaj +1 more source
CONTRIBUTIONS TO ALGORITHMIC MATROID PROBLEMS
, 2015 In this thesis, we obtain several algorithms for problems related to matroids, a structure that generalizes the concept of linear independence in a vector space and an acyclic subgraph structure in a graph.
Huang, Jinyu
core
A matroid port is a clutter (antichain of sets) determined by the collection of circuits of a matroid that contain a fixed point. We study the problem of determining matroid ports all whose elements have the same size h.
Martí Farré, Jaume +1 more
core +1 more source
Journal of Combinatorial Theory, Series BGraphings serve as limit objects for bounded-degree graphs. We define the ``cycle matroid'' of a graphing as a submodular setfunction, with values in [0,1], which generalizes (up to normalization) the cycle matroid of finite graphs. We prove that for a Benjamini--Schramm convergent sequence of graphs, the total rank, normalized by the number of nodes ...
openaire +2 more sources