Publication

Cocircuit Graphs and Efficient Orientation Reconstruction in Oriented Matroids

Komei Fukuda
2001
Journal Articles

Abstract

We consider the cocircuit graph GM of an oriented matroid M, which is the 1-skeleton of the cell complex formed by the span of the cocircuits of M. As a result of Cordovil, Fukuda, and Guedes de Oliveira, the isomorphism class of M is not determined by GM, but it is determined if M is uniform and the vertices in GM are paired if they are associated to negative cocircuits; furthermore the reorientation class of an oriented matroid M with rank(M) 2 is determined by GM if every vertex in GM is labeled by the zero support of the associated cocircuit. In this paper we show that the isomorphism class of a uniform oriented matroid is determined by the cocircuit graph, and we present polynomial algorithms which provide constructive proofs to all these results. Furthermore it is shown that the correctness of the input of the algorithms can be verified in polynomial time.

Official source

https://infoscience.epfl.ch/entities/publication/68e9499b-c8c0-41dc-9592-970e516c8b12

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Komei Fukuda
2001
Journal Articles

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/68e9499b-c8c0-41dc-9592-970e516c8b12

About this result

Related concepts (31)

Matroid

In combinatorics, a branch of mathematics, a matroid ˈmeɪtrɔɪd is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite simple matroid is equivalent to a geometric lattice.

Oriented matroid

An oriented matroid is a mathematical structure that abstracts the properties of directed graphs, vector arrangements over ordered fields, and hyperplane arrangements over ordered fields. In comparison, an ordinary (i.e., non-oriented) matroid abstracts the dependence properties that are common both to graphs, which are not necessarily directed, and to arrangements of vectors over fields, which are not necessarily ordered. All oriented matroids have an underlying matroid.

Graphic matroid

In the mathematical theory of matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co-graphic matroids or bond matroids. A matroid that is both graphic and co-graphic is sometimes called a planar matroid (but this should not be confused with matroids of rank 3, which generalize planar point configurations); these are exactly the graphic matroids formed from planar graphs.

Related publications (11)

Cocircuit Graphs and Efficient Orientation Reconstruction in Oriented Matroids

Chat with Graph Search

Algorithm Discovery With LLMs: Evolutionary Search Meets Reinforcement Learning

MATHICSE Technical Report : Low-rank approximation in the Frobenius norm by column and row subset selection

A Tale of Two Quasi-Polynomial Algorithms