Matroid - Matroid

Em combinatória , uma filial de matemática , uma matróide / m eɪ t r ɔɪ d / é uma estrutura que resumos e generaliza a noção de independência linear em espaços vector . Existem muitas maneiras equivalentes de definir uma matróide axiomaticamente , sendo a mais significativa em termos de: conjuntos independentes; bases ou circuitos; funções de classificação; operadores de fechamento; e conjuntos fechados ou apartamentos. Na linguagem de conjuntos parcialmente ordenados , um matróide finito é equivalente a uma rede geométrica .

A teoria dos matroides se baseia amplamente na terminologia da álgebra linear e da teoria dos grafos , principalmente porque é a abstração de várias noções de importância central nesses campos. Matroids encontraram aplicações em geometria , topologia , otimização combinatória , teoria de redes e teoria de codificação .

Definição

Existem muitas maneiras equivalentes ( criptomórficas ) de definir uma matróide (finita).

Conjuntos independentes

Em termos de independência, um finito matróides é um par , onde é um conjunto finito (chamado de set solo ) e é uma família de subconjuntos de (chamados os conjuntos independentes ) com as seguintes propriedades: ${\ displaystyle M}$${\ displaystyle (E, {\ mathcal {I}})}$${\ displaystyle E}$${\ displaystyle {\ mathcal {I}}}$${\ displaystyle E}$

(I1) O conjunto vazio é independente, ou seja ,. Como alternativa, pelo menos um subconjunto de é independente, ou seja ,.${\ displaystyle \ emptyset \ in {\ mathcal {I}}}$${\ displaystyle E}$${\ displaystyle {\ mathcal {I}} \ neq \ emptyset}$

(I2) Cada subconjunto de um conjunto independente é independente, ou seja, para cada um , se então . Isso às vezes é chamado de propriedade hereditária ou propriedade fechada para baixo .${\ displaystyle A '\ subseteq A \ subseteq E}$${\ displaystyle A \ in {\ mathcal {I}}}$${\ displaystyle A '\ in {\ mathcal {I}}}$

(I3) Se e são dois conjuntos independentes (ou seja, cada conjunto é independente) e tem mais elementos do que , então existe tal que está em . Isso às vezes é chamado de propriedade de aumento ou propriedade de troca de conjunto independente .${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle x \ in A \ barra invertida B}$${\ displaystyle B \ cup \ {x \}}$${\ displaystyle {\ mathcal {I}}}$

As duas primeiras propriedades definem uma estrutura combinatória conhecida como sistema de independência (ou complexo simplicial abstrato ).

Bases e circuitos

Um subconjunto do conjunto básico que não é independente é chamado de dependente . Um conjunto independente máximo - isto é, um conjunto independente que se torna dependente da adição de qualquer elemento de - é chamado de base para a matróide. Um circuito em uma matróide é um subconjunto dependente mínimo de - isto é, um conjunto dependente cujos subconjuntos próprios são todos independentes. A terminologia surge porque os circuitos dos matróides gráficos são ciclos nos gráficos correspondentes. ${\ displaystyle E}$${\ displaystyle E}$${\ displaystyle M}$${\ displaystyle E}$

Os conjuntos dependentes, as bases ou os circuitos de uma matróide caracterizam a matróide completamente: um conjunto é independente se e somente se não for dependente, se e somente se for um subconjunto de uma base, e se e somente se for não contém um circuito. Cada uma das coleções de conjuntos dependentes, de bases e de circuitos possui propriedades simples que podem ser tomadas como axiomas para uma matróide. Por exemplo, pode-se definir uma matróide como um par , onde é um conjunto finito como antes e é uma coleção de subconjuntos de , chamados "bases", com as seguintes propriedades: ${\ displaystyle M}$${\ displaystyle (E, {\ mathcal {B}})}$${\ displaystyle E}$${\ displaystyle {\ mathcal {B}}}$${\ displaystyle E}$

(B1) não está vazio.${\ displaystyle {\ mathcal {B}}}$

(B2) Se e são membros distintos de e , então existe um elemento tal que . Essa propriedade é chamada de propriedade de troca de base .${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle {\ mathcal {B}}}$${\ displaystyle a \ in A \ setminus B}$${\ displaystyle b \ in B \ setminus A}$${\ displaystyle (A \ setminus \ {a \}) \ cup \ {b \} \ in {\ mathcal {B}}}$

Segue-se da propriedade de troca de base que nenhum membro da pode ser um subconjunto apropriado de outro. ${\ displaystyle {\ mathcal {B}}}$

Funções de classificação

É um resultado básico da teoria da matróide, diretamente análogo a um teorema de bases semelhante na álgebra linear , que quaisquer duas bases de uma matróide têm o mesmo número de elementos. Esse número é chamado de classificação de  . Se for um matroide ligado e for um subconjunto de , então um matroide on pode ser definido considerando um subconjunto de como independente se e somente se for independente em . Isso nos permite falar sobre submatroides e sobre a classificação de qualquer subconjunto de . A classificação de um subconjunto é dada pela função de classificação da matróide, que possui as seguintes propriedades: ${\ displaystyle M}$${\ displaystyle M}$${\ displaystyle M}$${\ displaystyle E}$${\ displaystyle A}$${\ displaystyle E}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle M}$${\ displaystyle E}$${\ displaystyle A}$ ${\ displaystyle r (A)}$

• O valor da função de classificação é sempre um número inteiro não negativo .
• Para qualquer subconjunto , temos .${\ displaystyle A \ subset E}$${\ displaystyle r (A) \ leq | A |}$
• Para quaisquer dois subconjuntos , temos: . Ou seja, a classificação é uma função submodular .${\ displaystyle A, B \ subset E}$${\ displaystyle r (A \ cup B) + r (A \ cap B) \ leq r (A) + r (B)}$
• Para qualquer conjunto e elemento , temos: . Da primeira desigualdade segue-se de forma mais geral que, se , então . Ou seja, a classificação é uma função monotônica .${\ displaystyle A}$${\ displaystyle x}$${\ displaystyle r (A) \ leq r (A \ cup \ {x \}) \ leq r (A) +1}$${\ displaystyle A \ subseteq B \ subseteq E}$${\ displaystyle r (A) \ leq r (B) \ leq r (E)}$

Essas propriedades podem ser usadas como uma das definições alternativas de uma matróide finita: se satisfaz essas propriedades, então os conjuntos independentes de uma matróide over podem ser definidos como os subconjuntos de com . Na linguagem dos conjuntos parcialmente ordenados , tal estrutura matróide é equivalente à rede geométrica cujos elementos são os subconjuntos , parcialmente ordenados por inclusão. ${\ displaystyle (E, r)}$${\ displaystyle E}$${\ displaystyle A}$${\ displaystyle E}$${\ displaystyle r (A) = | A |}$${\ displaystyle A \ subset M}$

A diferença é chamada de nulidade do subconjunto . É o número mínimo de elementos que devem ser removidos para obter um conjunto independente. A nulidade de em é chamada de nulidade de . A diferença às vezes é chamada de corank do subconjunto . ${\ displaystyle | A | -r (A)}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle E}$${\ displaystyle M}$${\ displaystyle M}$${\ displaystyle r (E) -r (A)}$${\ displaystyle A}$

Operadores de fechamento

Let ser uma matróide em um conjunto finito , com função de classificação como acima. O fechamento (ou extensão ) de um subconjunto de é o conjunto ${\ displaystyle M}$${\ displaystyle E}$${\ displaystyle r}$${\ displaystyle \ operatorname {cl} (A)}$${\ displaystyle A}$${\ displaystyle E}$

${\ displaystyle \ operatorname {cl} (A) = {\ Bigl \ {} x \ in E \ mid r (A) = r {\ bigl (} A \ cup \ {x \} {\ bigr)} {\ Bigr \}}}$.

Isso define um operador de fechamento onde denota o conjunto de energia , com as seguintes propriedades: ${\ displaystyle \ operatorname {cl}: {\ mathcal {P}} (E) \ to {\ mathcal {P}} (E)}$${\ displaystyle {\ mathcal {P}}}$

• Para todos os subconjuntos de , .${\ displaystyle X}$${\ displaystyle E}$${\ displaystyle X \ subseteq \ operatorname {cl} (X)}$
• Para todos os subconjuntos de , .${\ displaystyle X}$${\ displaystyle E}$${\ displaystyle \ operatorname {cl} (X) = \ operatorname {cl} (\ operatorname {cl} (X))}$
• Para todos os subconjuntos e de com , .${\ displaystyle X}$${\ displaystyle Y}$${\ displaystyle E}$${\ displaystyle X \ subseteq Y}$${\ displaystyle \ operatorname {cl} (X) \ subseteq \ operatorname {cl} (Y)}$
• Para todos os elementos , e de e todos os subconjuntos de , se então .${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle E}$${\ displaystyle Y}$${\ displaystyle E}$${\ displaystyle a \ in \ operatorname {cl} (Y \ cup \ {b \}) \ setminus \ operatorname {cl} (Y)}$${\ displaystyle b \ in \ operatorname {cl} (Y \ cup \ {a \}) \ setminus \ operatorname {cl} (Y)}$

As três primeiras dessas propriedades são as propriedades de definição de um operador de fechamento. A quarta é às vezes chamada de propriedade de troca Mac Lane - Steinitz . Essas propriedades podem ser tomadas como outra definição de matróide: toda função que obedece a essas propriedades determina uma matróide. ${\ displaystyle \ operatorname {cl}: {\ mathcal {P}} (E) \ to {\ mathcal {P}} (E)}$

Apartamentos

Um conjunto cujo fechamento é igual a si mesmo é dito fechado , ou um plano ou subespaço da matróide. Um conjunto é fechado se for máximo para sua classificação, o que significa que a adição de qualquer outro elemento ao conjunto aumentaria a classificação. Os conjuntos fechados de um matroide são caracterizados por uma propriedade de partição de cobertura:

• Todo o conjunto de pontos está fechado.${\ displaystyle E}$
• Se e forem apartamentos, então é um apartamento.${\ displaystyle S}$${\ displaystyle T}$${\ displaystyle S \ cap T}$
• Se for um apartamento, então cada elemento de está precisamente em um dos apartamentos que cobrem (o que significa que contém corretamente, mas não há nenhum plano entre e ).${\ displaystyle S}$${\ displaystyle E \ setminus S}$${\ displaystyle T}$ ${\ displaystyle S}$${\ displaystyle T}$${\ displaystyle S}$${\ displaystyle U}$${\ displaystyle S}$${\ displaystyle T}$

A classe de todos os apartamentos, parcialmente ordenados por inclusão de conjunto, forma uma estrutura matróide . Por outro lado, cada rede matroide forma uma matroide sobre seu conjunto de átomos sob o seguinte operador de fechamento: para um conjunto de átomos com junção , ${\ displaystyle {\ mathcal {L}} (M)}$${\ displaystyle L}$${\ displaystyle E}$${\ displaystyle S}$${\ displaystyle \ bigvee S}$

${\ displaystyle \ operatorname {cl} (S) = \ {x \ in E \ mid x \ leq \ bigvee S \}}$.

Os planos desta matróide correspondem um a um com os elementos da rede; o plano correspondente ao elemento de rede é o conjunto ${\ displaystyle y}$

${\ displaystyle \ {x \ in E \ mid x \ leq y \}}$.

Assim, a rede de apartamentos deste matróide é naturalmente isomórfica a  . ${\ displaystyle L}$

Hiperplanos

Em uma matróide de classificação , um plano de classificação é chamado de hiperplano . (Os hiperplanos também são chamados de coatoms ou copoints .) Esses são os apartamentos adequados máximos; ou seja, o único superconjunto de um hiperplano que também é plano é o conjunto de todos os elementos da matróide. Uma definição equivalente é que um coatom é um subconjunto de E que não abrange M , mas tal que adicionar qualquer outro elemento a ele cria um conjunto de abrangência. ${\ displaystyle r}$${\ displaystyle r-1}$${\ displaystyle E}$

A família de hiperplanos de uma matróide tem as seguintes propriedades, que podem ser consideradas mais uma axiomatização de matróides: ${\ displaystyle {\ mathcal {H}}}$

• Não existem conjuntos distintos e em com . Ou seja, os hiperplanos formam uma família Sperner .${\ displaystyle X}$${\ displaystyle Y}$${\ displaystyle {\ mathcal {H}}}$${\ displaystyle X \ subseteq Y}$
• Para cada e distinto com , existe com .${\ displaystyle x \ in E}$${\ displaystyle Y, Z \ in {\ mathcal {H}}}$${\ displaystyle x \ notin Y \ cup Z}$${\ displaystyle X \ in {\ mathcal {H}}}$${\ displaystyle (Y \ cap Z) \ cup \ {x \} \ subseteq X}$

Graphoids

Minty (1966) definiu um grafoide como um triplo no qual e são classes de subconjuntos não vazios de tais que ${\ displaystyle (L, C, D)}$${\ displaystyle C}$${\ displaystyle D}$${\ displaystyle L}$

• nenhum elemento de (chamado de "circuito") contém outro,${\ displaystyle C}$
• nenhum elemento de (chamado de "cocircuito") contém outro,${\ displaystyle D}$
• não set in e set in intersect em exatamente um elemento, e${\ displaystyle C}$${\ displaystyle D}$
• sempre que for representado como a união disjunta de subconjuntos com (um conjunto singleton), então existe um tal que ou existe tal que${\ displaystyle L}$${\ displaystyle R, G, B}$${\ displaystyle G = \ {g \}}$${\ displaystyle X \ in C}$${\ displaystyle g \ in X \ subseteq R \ cup G}$${\ displaystyle Y \ in D}$${\ displaystyle g \ in Y \ subseteq B \ cup G.}$

Ele provou que existe uma matróide para a qual é a classe dos circuitos e é a classe dos cocircuitos. Por outro lado, se e são as classes de circuito e cocircuito de um matróide com conjunto de solo , então é um grafóide. Assim, grafoides dão uma axiomatização criptomórfica autodupla de matróides. ${\ displaystyle C}$${\ displaystyle D}$${\ displaystyle C}$${\ displaystyle D}$${\ displaystyle M}$${\ displaystyle E}$${\ displaystyle (E, C, D)}$

Exemplos

Matroide grátis

Deixe ser um conjunto finito. O conjunto de todos os subconjuntos de satisfaz a definição de uma matróide. Ela é chamada de matróides livre mais . ${\ displaystyle E}$${\ displaystyle E}$${\ displaystyle E}$

Matróides uniformes

Let Ser um conjunto finito e um número natural . Pode-se definir uma matroide tomando como base cada subconjunto de elementos de . Isso é conhecido como a matróide uniforme de classificação . Um matroide uniforme com classificação e com elementos é denotado . Todos os matróides uniformes de classificação pelo menos 2 são simples (ver § Terminologia adicional ). O matróide uniforme de posto 2 em pontos é chamado de - linha de ponto . Uma matróide é uniforme se e somente se não tiver circuitos de tamanho menor que um mais a fila da matróide. As somas diretas de matróides uniformes são chamadas de matróides de partição . ${\ displaystyle E}$${\ displaystyle k}$${\ displaystyle E}$${\ displaystyle k}$${\ displaystyle E}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle U_ {k, n}}$${\ displaystyle n}$${\ displaystyle n}$

Na matróide uniforme , cada elemento é um loop (um elemento que não pertence a nenhum conjunto independente), e na matróide uniforme , cada elemento é um coloop (um elemento que pertence a todas as bases). A soma direta das matróides desses dois tipos é uma partição matróide em que cada elemento é um loop ou um coloop; é chamada de matróide discreta . Uma definição equivalente de uma matróide discreta é uma matróide na qual todo subconjunto próprio e não vazio do conjunto básico é um separador. ${\ displaystyle U_ {0, n}}$${\ displaystyle U_ {n, n}}$${\ displaystyle E}$

Matroids de álgebra linear

A teoria dos matroides desenvolveu-se principalmente a partir de um exame profundo das propriedades de independência e dimensão em espaços vetoriais. Existem duas maneiras de apresentar as matróides definidas desta forma:

• Se for qualquer subconjunto finito de um espaço vetorial , então podemos definir uma matróide on tomando os conjuntos independentes de como sendo os subconjuntos linearmente independentes de . A validade dos axiomas de conjuntos independentes para esta matróide segue do lema da troca de Steinitz . Se for uma matróide que pode ser definida desta forma, dizemos que o conjunto representa . Matroids deste tipo são chamados de matróides vetoriais . Um exemplo importante de uma matróide definida desta forma é a matróide Fano, uma matróide de nível três derivada do plano de Fano , uma geometria finita com sete pontos (os sete elementos da matróide) e sete linhas (os próprios planos não triviais do matroide). É uma matróide linear cujos elementos podem ser descritos como os sete pontos diferentes de zero em um espaço vetorial tridimensional sobre o corpo finito GF (2) . No entanto, não é possível fornecer uma representação semelhante para a matróide Fano usando os números reais no lugar de GF (2).${\ displaystyle E}$ ${\ displaystyle V}$${\ displaystyle M}$${\ displaystyle E}$${\ displaystyle M}$${\ displaystyle E}$${\ displaystyle M}$${\ displaystyle E}$ ${\ displaystyle M}$
• Uma matriz com entradas em um campo dá origem a uma matróide em seu conjunto de colunas. Os conjuntos dependentes de colunas na matróide são aqueles que são linearmente dependentes como vetores. Esta matróide é chamada de matróide de coluna de , e diz-se que representa . Por exemplo, a matróide Fano pode ser representada desta forma como uma matriz 3 × 7 (0,1) . Matróides de coluna são apenas matróides vetoriais com outro nome, mas muitas vezes há razões para favorecer a representação de matriz. (Há uma diferença técnica: uma matróide de coluna pode ter elementos distintos que são o mesmo vetor, mas uma matróide vetorial, conforme definido acima, não. Normalmente essa diferença é insignificante e pode ser ignorada, mas deixando ser um conjunto múltiplo de vetores traz o duas definições em acordo completo.)${\ displaystyle A}$${\ displaystyle M}$${\ displaystyle A}$${\ displaystyle A}$ ${\ displaystyle M}$${\ displaystyle E}$

Uma matróide que equivale a uma matróide vetorial, embora possa ser apresentada de forma diferente, é chamada de representável ou linear . Se é equivalente a um vetor matróide sobre um campo , então dizemos que é representável sobre ; em particular, é real-representável se for representável sobre os números reais. Por exemplo, embora um matroide gráfico (veja abaixo) seja apresentado em termos de um gráfico, ele também pode ser representado por vetores em qualquer campo. Um problema básico na teoria das matroides é caracterizar as matroides que podem ser representadas em um determinado campo ; A conjectura de Rota descreve uma caracterização possível para cada campo finito . Os principais resultados até agora são caracterizações de matróides binários (aqueles representáveis ​​sobre GF (2)) devido a Tutte (1950s), de matróides ternários (representáveis ​​sobre o campo de 3 elementos) devido a Reid e Bixby, e separadamente a Seymour (1970s ), e de matróides quaternários (representáveis ​​no campo de 4 elementos) devido a Geelen, Gerards e Kapoor (2000). Esta é uma área muito aberta. ${\ displaystyle M}$ ${\ displaystyle F}$${\ displaystyle M}$ ${\ displaystyle F}$${\ displaystyle M}$${\ displaystyle F}$

Uma matróide regular é uma matróide representável em todos os campos possíveis. A matroide Vámos é o exemplo mais simples de uma matroide que não é representável em nenhum campo.

Matroids da teoria dos grafos

Uma segunda fonte original para a teoria das matróides é a teoria dos grafos .

Todo grafo finito (ou multigrafo ) dá origem a uma matróide da seguinte maneira: tome como o conjunto de todas as arestas em e considere um conjunto de arestas independente se e somente se for uma floresta ; isto é, se não contiver um ciclo simples . Então é chamado de ciclo matroide . Matroids derivados desta forma são matróides gráficos . Nem todo matroide é gráfico, mas todos os matroides em três elementos são gráficos. Cada matroide gráfico é regular. ${\ displaystyle G}$${\ displaystyle M (G)}$${\ displaystyle E}$${\ displaystyle G}$${\ displaystyle M (G)}$

Outros matroides em gráficos foram descobertos posteriormente:

• A matróide bicircular de um gráfico é definida chamando um conjunto de arestas independentes se cada subconjunto conectado contiver no máximo um ciclo.
• Em qualquer gráfico direcionado ou não direcionado, sejam e sejam dois conjuntos distintos de vértices. No conjunto , defina um subconjunto para ser independente se houver | | caminhos separados do vértice de para . Isso define um matroide chamado gammóide : um gammóide estrito é aquele para o qual o conjunto é todo o conjunto de vértices .${\ displaystyle G}$${\ displaystyle E}$${\ displaystyle F}$${\ displaystyle E}$${\ displaystyle U}$${\ displaystyle U}$${\ displaystyle F}$${\ displaystyle U}$${\ displaystyle E}$${\ displaystyle E}$${\ displaystyle G}$
• Em um gráfico bipartido , pode-se formar uma matróide em que os elementos são vértices de um lado da bipartição e os subconjuntos independentes são conjuntos de pontos finais de correspondências do gráfico. Isso é chamado de matróide transversal e é um caso especial de gammóide. As matróides transversais são as matróides duplas dos gammoides estritos.${\ displaystyle G = (U, V, E)}$${\ displaystyle U}$
• As matróides gráficas foram generalizadas para matróides a partir de gráficos com sinais , gráficos de ganho e gráficos tendenciosos . Um gráfico com uma classe linear distinta de ciclos, conhecido como "gráfico enviesado" , tem duas matróides, conhecidas como matróide de quadro e matróide de sustentação do gráfico tendencioso. Se cada ciclo pertence à classe distinta, essas matróides coincidem com o ciclo matróide de . Se nenhum ciclo for distinguido, a estrutura matróide é a matróide bicircular de . Um grafo assinado, cujas arestas são rotuladas por sinais, e um grafo de ganho, que é um grafo cujas arestas são rotuladas de forma orientável a partir de um grupo, cada um dá origem a um gráfico enviesado e, portanto, tem matróides de estrutura e elevação.${\ displaystyle G}$${\ displaystyle B}$${\ displaystyle (G, B)}$${\ displaystyle G}$${\ displaystyle G}$
• Os gráficos de Laman formam as bases da matróide de rigidez bidimensional , uma matróide definida na teoria da rigidez estrutural .
• Let Ser um gráfico conectado e ser seu conjunto de arestas. Deixe ser a coleção de subconjuntos de tal que ainda está conectado. Então , cujo conjunto de elementos é e com sua classe de conjuntos independentes, está uma matróide chamada matróide de ligação de . A função de classificação é o número ciclomático do subgráfico induzido no subconjunto de arestas , que é igual ao número de arestas fora de uma floresta máxima desse subgráfico, e também o número de ciclos independentes nele.${\ displaystyle G}$${\ displaystyle E}$${\ displaystyle I}$${\ displaystyle F}$${\ displaystyle E}$${\ displaystyle GF}$${\ displaystyle M ^ {*} (G)}$${\ displaystyle E}$${\ displaystyle I}$${\ displaystyle G}$${\ displaystyle r (F)}$${\ displaystyle F}$

Matroids de extensões de campo

Uma terceira fonte original da teoria matróide é a teoria de campo .

Uma extensão de um campo dá origem a uma matróide. Suponha e sejam campos contendo . Seja qualquer subconjunto finito de . Defina um subconjunto de como independente algebricamente se o campo de extensão tiver grau de transcendência igual a . ${\ displaystyle F}$${\ displaystyle K}$${\ displaystyle K}$${\ displaystyle F}$${\ displaystyle E}$${\ displaystyle K}$${\ displaystyle S}$${\ displaystyle E}$${\ displaystyle F (S)}$${\ displaystyle | S |}$

Uma matróide que é equivalente a uma matróide desse tipo é chamada de matróide algébrica . O problema de caracterizar matróides algébricos é extremamente difícil; pouco se sabe sobre isso. A Vámos matroide é um exemplo de matroide que não é algébrica.

Construções básicas

Existem algumas maneiras padrão de fazer novas matróides a partir das antigas.

Dualidade

Se M é uma matróide finita, podemos definir a ortogonal ou matróides dupla M *, tendo o mesmo conjunto subjacente e chamar um conjunto de base em M * se e somente se seu complemento é uma base em M . Não é difícil verificar que M * é um matróide e que a dupla de M * é M .

O dual pode ser descrito igualmente bem em termos de outras maneiras de definir uma matróide. Por exemplo:

• Um conjunto é independente em M * se e somente se os seus vãos complemento M .
• Um conjunto é um circuito de H * se e apenas se o seu complemento é um coatom em H .
• A função de classificação do dual é .${\ displaystyle r ^ {*} (S) = | S | -r (M) + r \ left (E \ setminus S \ right)}$

De acordo com uma versão matróide do teorema de Kuratowski , o dual de uma matróide gráfica M é uma matróide gráfica se e somente se M for a matróide de um gráfico planar . Neste caso, a dupla de H é o matróide do grafo dual de L . A dupla de um vector matróide representável ao longo de um determinado campo F também é representável através F . O dual de uma matróide transversal é um gammóide estrito e vice-versa.

Exemplo

A matróide de ciclo de um gráfico é a matróide dupla de sua matróide de ligação.

Menores

Se M é uma matróide com conjunto de elementos E , e S é um subconjunto de E , a restrição de M a S , escrita M  | S , é a matróide no conjunto S cujos conjuntos independentes são os conjuntos independentes de H que estão contidos em S . Seus circuitos são os circuitos de M que estão contidos em S e sua função Rank é a de M restrito aos subconjuntos de S . Em álgebra linear, isto corresponde a restringir ao subespaço gerado pelos vectores em S . De forma equivalente, se T = M - S pode ser denominado o deleção de T , escrito M \ T ou M - t . Os submatróides de M são precisamente o resultado de uma seqüência de deleções: a ordem é irrelevante.

A dupla operação de restrição é a contração. Se T é um subconjunto de E , a contração de M por T , escrita M / T , é a matróide no conjunto subjacente E - T cuja função de classificação é Na álgebra linear, isso corresponde a olhar para o espaço quociente pelo espaço linear gerado pelos vectores em T , juntamente com as imagens dos vectores em E - t . ${\ displaystyle r '(A) = r (A \ cup T) -r (T).}$

Um matróide N que é obtido a partir de H por uma sequência de operações de restrição e de contracção é chamado um menor de M . Dizemos que M contém N como menor . Muitas famílias importantes de matróides podem ser caracterizadas pelas matróides mínimas menores que não pertencem à família; estes são chamados de menores proibidos ou excluídos .

Somas e uniões

Deixe- H ser um matróide com um conjunto subjacente dos elementos E , e deixá- N ser um outro matróide sobre um conjunto subjacente F . A soma directa de matróides M e N é o matróide cujo conjunto subjacente é a união disjuntos de E e F , e cujos conjuntos independentes são as uniões disjuntos de um conjunto independente de H , com um conjunto independente de N .

A união de M e N é o matróide cujo conjunto subjacente é a união (não união disjuntos) de E e F , e cujos conjuntos independentes são aqueles que são subconjuntos da união de um conjunto independente em M e um em N . Normalmente, o termo "união" é aplicado quando E = F , mas essa suposição não é essencial. Se E e F são disjuntos, a união é a soma direta.

Terminologia adicional

Deixe- H ser um matróide com um conjunto subjacente dos elementos E .

• E pode ser chamado o conjunto de chão de M . Seus elementos podem ser chamados os pontos de M .
• Um subconjunto de E abrange M se o seu fecho é E . Um conjunto é dito para abranger um conjunto fechado K se o seu fecho é K .
• A circunferência de uma matróide é o tamanho de seu menor circuito ou conjunto dependente.
• Um elemento que forma um circuito de elemento único de M é chamado de loop . Equivalentemente, um elemento é um loop se não pertencer a nenhuma base.
• Um elemento que não pertence a nenhum circuito é chamado de coloop ou istmo . Equivalentemente, um elemento é um coloop se pertencer a todas as bases. Loop e coloops são mutuamente duais.
• Se um conjunto de dois elementos { f, g } é um circuito de M , em seguida, f e g são paralelo em H .
• Um matroide é denominado simples se não possuir circuitos compostos por 1 ou 2 elementos. Ou seja, não tem loops e nem elementos paralelos. O termo geometria combinatória também é usado. Um simples matróide obtido a partir de outro matróide M , suprimindo todos os laços e a supressão de um elemento a partir de cada circuito de 2 até elemento sem circuitos de 2 elementos permanecer é denominada uma simplificação de M . Uma matróide é co-simples se sua matróide dupla for simples.
• A união de circuitos é às vezes chamado de ciclo de M . Um ciclo é, portanto, o complemento de um plano da matróide dual. (Este uso entra em conflito com o significado comum de "ciclo" na teoria dos grafos.)
• Um separador de M é um subconjunto S de E tal que . Um separador próprio ou não trivial é um separador que não é E nem o conjunto vazio. Um separador irredutível é um separador que não contém nenhum outro separador não vazio. Os separadores irredutíveis particionar o conjunto terreno E .${\ displaystyle r (S) + r (ES) = r (M)}$
• Uma matróide que não pode ser escrita como a soma direta de duas matróides não vazias, ou equivalentemente que não possui separadores apropriados, é chamada conectada ou irredutível . Um matroid é conectado se e somente se seu dual estiver conectado.
• A submatroid irredutível máximo de M é chamado de um componente de M . Um componente é a restrição de M a um separador irredutível e, ao contrário, a restrição de M a um separador irredutível é um componente. Um separador é uma união de componentes.
• Uma matróide M é chamada de matróide de quadro se ela, ou uma matróide que a contém, tem uma base tal que todos os pontos de M estão contidos nas linhas que unem pares de elementos de base.
• Uma matróide é chamada de matróide de pavimentação se todos os seus circuitos tiverem tamanho pelo menos igual à sua categoria.
• O politopo matróide é o casco convexo dos vetores indicadores das bases de .${\ displaystyle P_ {M}}$${\ displaystyle M}$

Algoritmos

Algoritmo ganancioso

Uma matróide ponderada é uma matróide juntamente com uma função de seus elementos para os números reais não negativos . O peso de um subconjunto de elementos é definido como a soma dos pesos dos elementos no subconjunto. O algoritmo guloso pode ser usado para encontrar uma base de peso máximo da matróide, começando do conjunto vazio e adicionando repetidamente um elemento por vez, em cada etapa escolhendo um elemento de peso máximo entre os elementos cuja adição preservaria a independência do conjunto aumentado. Este algoritmo não precisa saber nada sobre os detalhes da definição da matroide, desde que tenha acesso à matroide por meio de um oráculo de independência , uma sub-rotina para testar se um conjunto é independente.

Este algoritmo de otimização pode ser usado para caracterizar matróides: se uma família F de conjuntos, fechada sob toma de subconjuntos, tem a propriedade de que, não importa como os conjuntos são ponderados, o algoritmo guloso encontra um conjunto de peso máximo na família, então F deve ser a família de conjuntos independentes de uma matróide.

A noção de matroide foi generalizada para permitir outros tipos de conjuntos nos quais um algoritmo guloso fornece soluções ótimas; veja incorporação greedoid e matroid para mais informações.

Particionamento de Matroid

O problema de particionamento da matroide é particionar os elementos de uma matroide no menor número possível de conjuntos independentes, e o problema de empacotamento da matroide é encontrar tantos conjuntos de extensão disjuntos quanto possível. Ambos podem ser resolvidos em tempo polinomial e podem ser generalizados para o problema de calcular a classificação ou encontrar um conjunto independente em uma soma matróide.

Interseção de matroid

A interseção de duas ou mais matróides é a família de conjuntos que são simultaneamente independentes em cada uma das matróides. O problema de encontrar o maior conjunto, ou o conjunto máximo ponderado, na interseção de dois matróides pode ser encontrado em tempo polinomial e fornece uma solução para muitos outros problemas importantes de otimização combinatória. Por exemplo, a correspondência máxima em grafos bipartidos pode ser expressa como um problema de interseção de duas matróides de partição . No entanto, encontrar o maior conjunto em uma interseção de três ou mais matróides é NP-completo .

Software Matroid

Dois sistemas autônomos para cálculos com matróides são Kingan's Oid e Hlineny Macek . Ambos são pacotes de código aberto. "Oid" é um sistema de software interativo extensível para experimentos com matroids. "Macek" é um sistema de software especializado com ferramentas e rotinas para cálculos combinatórios razoavelmente eficientes com matróides representáveis.

Ambos os sistemas de software de matemática de código aberto SAGE e Macaulay2 contêm pacotes matroid.

Invariantes polinomiais

Existem dois polinómios especialmente significativos associados a um matróide finito H no conjunto de chão E . Cada um é um invariante matroide , o que significa que matroids isomorphic têm o mesmo polinômio.

Polinômio característico

O polinômio característico de M (que às vezes é chamado de polinômio cromático , embora não conte as cores), é definido como

${\ displaystyle p_ {M} (\ lambda): = \ sum _ {S \ subseteq E} (- 1) ^ {| S |} \ lambda ^ {r (M) -r (S)},}$

ou de forma equivalente (contanto que o conjunto vazio seja fechado em M ) como

${\ displaystyle p_ {M} (\ lambda): = \ sum _ {A} \ mu (\ emptyset, A) \ lambda ^ {r (M) -r (A)} \,}$

onde μ denota a função de Möbius da rede geométrica da matróide e a soma é assumida por todos os apartamentos A da matróide.

Quando M é o ciclo matróide M ( G ) de um gráfico G , o polinômio característico é uma ligeira transformação do polinômio cromático , que é dado por χ _G  (λ) = λ ^c p _{M ( G )}  (λ), onde c é o número de componentes ligados de L .

Quando M é o vínculo matróide M * ( L ) de um gráfico G , o polinomial característica é igual ao polinómio fluxo de L .

Quando M é a matróide M ( A ) de um arranjo A de hiperplanos lineares em R ⁿ (ou F ⁿ onde F é qualquer campo), o polinômio característico do arranjo é dado por p _A  (λ) = λ ^{n - r ( M )} p _{M ( A )}  (λ).

Invariante beta

O invariante beta de um matróide, introduzido por Crapo (1967), pode ser expresso em termos do polinômio característico p como uma avaliação do derivado

${\ displaystyle \ beta (M) = (- 1) ^ {r (M) -1} p_ {M} '(1) \}$

ou diretamente como

${\ displaystyle \ beta (M) = (- 1) ^ {r (M)} \ sum _ {X \ subseteq E} (- 1) ^ {| X |} r (X) \.}$

O invariante beta é não negativo e é zero se e somente se M estiver desconectado, ou vazio, ou um loop. Caso contrário, ele depende apenas da rede de apartamentos de M . Se M não tem loops e coloops, então β ( M ) = β ( M ^∗ ).

Polinômio de Tutte

O polinômio Tutte de um matróide, T _M  ( x , y ), generaliza o polinômio característico para duas variáveis. Isso dá a ele mais interpretações combinatórias e também dá a propriedade de dualidade

${\ displaystyle T_ {M ^ {*}} (x, y) = T_ {M} (y, x),}$

o que implica uma série de dualidades entre propriedades de M e propriedades de M  *. Uma definição do polinômio de Tutte é

${\ displaystyle T_ {M} (x, y) = \ sum _ {S \ subseteq E} (x-1) ^ {r (M) -r (S)} (y-1) ^ {| S | - r (S)}.}$

Isso expressa o polinômio de Tutte como uma avaliação da nulidade de corank ou polinômio gerador de classificação ,

${\ displaystyle R_ {M} (u, v) = \ sum _ {S \ subseteq E} u ^ {r (M) -r (S)} v ^ {| S | -r (S)}.}$

A partir desta definição é fácil ver que o polinômio característico é, até um fator simples, uma avaliação de T _M , especificamente,

${\ displaystyle p_ {M} (\ lambda) = (- 1) ^ {r (M)} T_ {M} (1- \ lambda, 0).}$

Outra definição é em termos de atividades internas e externas e somatório de bases, refletindo o fato de que T (1,1) é o número de bases. Isso, que soma menos subconjuntos, mas tem termos mais complicados, era a definição original de Tutte.

Existe uma definição adicional em termos de recursão por deleção e contração. A identidade deleção-contração é

${\ displaystyle F (M) = F (Me) + F (M / e)}$quando não é um loop nem um coloop.${\ displaystyle e}$

Um invariante de matróides (ou seja, uma função que assume o mesmo valor em matróides isomórficos) satisfazendo esta recursão e a condição multiplicativa

${\ displaystyle F (M \ oplus M ') = F (M) F (M')}$

é considerado um invariante de Tutte-Grothendieck . O polinômio de Tutte é o invariante mais geral; isto é, o polinômio de Tutte é um invariante de Tutte-Grothendieck e cada invariante é uma avaliação do polinômio de Tutte.

O polinômio Tutte T _G   de um gráfico é o polinômio Tutte T _{M ( G )} de seu ciclo matróide.

Matroides infinitas

A teoria das matróides infinitas é muito mais complicada do que a das matróides finitas e constitui um assunto próprio. Por muito tempo, uma das dificuldades foi que havia muitas definições razoáveis ​​e úteis, nenhuma das quais parecia capturar todos os aspectos importantes da teoria matróide finita. Por exemplo, parecia ser difícil ter bases, circuitos e dualidade juntos em uma noção de matróides infinitas.

A definição mais simples de uma matróide infinita é exigir uma classificação finita ; ou seja, a classificação de E é finita. Esta teoria é semelhante à das matróides finitas, exceto pela falha da dualidade devido ao fato de que o dual de uma matróide infinita de classificação finita não tem classificação finita. As matróides de classificação finita incluem quaisquer subconjuntos de espaços vetoriais de dimensão finita e de extensões de campo de grau de transcendência finito .

A próxima generalização infinita mais simples são os matróides finitários. Uma matróide é finitária se tem a propriedade de

${\ displaystyle x \ in \ operatorname {cl} (Y) \ Leftrightarrow (\ existe Y '\ subseteq Y) Y' {\ text {é finito e}} x \ in \ operatorname {cl} (Y ').}$

Equivalentemente, cada conjunto dependente contém um conjunto dependente finito. Os exemplos são a dependência linear de subconjuntos arbitrários de espaços vetoriais de dimensão infinita (mas não dependências infinitas como nos espaços de Hilbert e Banach ) e dependência algébrica em subconjuntos arbitrários de extensões de campo de grau de transcendência possivelmente infinito. Novamente, a classe da matróide finitária não é autodual, porque a dupla de uma matróide finitária não é finitária. Os matróides finitos finitos são estudados na teoria dos modelos , um ramo da lógica matemática com fortes ligações com a álgebra .

No final dos anos 1960, os teóricos das matróides pediram uma noção mais geral que compartilhasse os diferentes aspectos das matróides finitas e generalizasse sua dualidade. Muitas noções de matróides infinitas foram definidas em resposta a este desafio, mas a questão permaneceu aberta. Uma das abordagens examinadas por DA Higgs tornou-se conhecida como B-matroids e foi estudada por Higgs, Oxley e outros nas décadas de 1960 e 1970. De acordo com um resultado recente de Bruhn, Diestel e Kriesell et al. ( 2013 ), ele resolve o problema: chegando à mesma noção de forma independente, eles forneceram cinco sistemas equivalentes de axioma - em termos de independência, bases, circuitos, fechamento e classificação. A dualidade das matróides B generaliza dualidades que podem ser observadas em gráficos infinitos.

Os axiomas de independência são os seguintes:

1. O conjunto vazio é independente.
2. Cada subconjunto de um conjunto independente é independente.
3. Para cada nonmaximal (sob inclusão conjunto) conjunto independente que e máxima conjunto independente J , há de tal forma que é independente.${\ displaystyle x \ in J \ setminus I}$${\ displaystyle I \ cup \ {x \}}$
4. Para cada subconjunto X do espaço de base, cada subconjunto independente I de X pode ser estendido para um subconjunto independente máxima de X .

Com esses axiomas, cada matróide tem um dual.

História

A teoria da matroid foi introduzida por Hassler Whitney  ( 1935 ). Também foi descoberto de forma independente por Takeo Nakasawa , cujo trabalho foi esquecido por muitos anos ( Nishimura & Kuroda 2009 ).

Em seu artigo seminal, Whitney forneceu dois axiomas para a independência e definiu qualquer estrutura aderente a esses axiomas como "matróides". (Embora talvez estivesse implícito, ele não incluiu um axioma que exigisse que pelo menos um subconjunto fosse independente.) Sua observação principal foi que esses axiomas fornecem uma abstração de "independência" comum a gráficos e matrizes. Por causa disso, muitos dos termos usados ​​na teoria matróide se assemelham aos termos de seus conceitos análogos na álgebra linear ou na teoria dos grafos .

Quase imediatamente após Whitney escrever pela primeira vez sobre matróides, um importante artigo foi escrito por Saunders Mac Lane  ( 1936 ) sobre a relação de matróides com a geometria projetiva . Um ano depois, BL van der Waerden  ( 1937 ) notou semelhanças entre a dependência algébrica e linear em seu clássico livro de Álgebra Moderna.

Na década de 1940, Richard Rado desenvolveu mais teoria sob o nome de "sistemas de independência" com um olhar para a teoria transversal , onde seu nome ainda é usado algumas vezes.

Na década de 1950, WT Tutte se tornou a figura mais importante na teoria matróide, posição que manteve por muitos anos. Suas contribuições foram abundantes, incluindo a caracterização de matróides binários , regulares e gráficos por menores excluídos ; o teorema da representabilidade matróide regular; a teoria dos grupos em cadeia e suas matróides; e as ferramentas que ele usou para provar muitos de seus resultados, o "teorema do caminho" e o " teorema da homotopia de Tutte " (ver, por exemplo, Tutte 1965 ), que são tão complexos que teóricos posteriores tiveram muito trabalho para eliminar a necessidade de usar -los em provas. (Um bom exemplo é a prova curta de AMH Gerards ( 1989 ) da caracterização de matróides regulares por Tutte.)

Henry Crapo  ( 1969 ) e Thomas Brylawski  ( 1972 ) generalizaram para o "dicromato" de Tutte, um polinômio gráfico agora conhecido como polinômio de Tutte (nomeado por Crapo). Seu trabalho foi recentemente (especialmente na década de 2000) seguido por uma enxurrada de papéis - embora não tantos quanto no polinômio de Tutte de um gráfico.

Em 1976, Dominic Welsh publicou o primeiro livro abrangente sobre a teoria matróide.

O teorema de decomposição de Paul Seymour para matróides regulares ( 1980 ) foi o trabalho mais significativo e influente do final dos anos 1970 e 1980. Outra contribuição fundamental, de Kahn & Kung (1982) , mostrou porque as geometrias projetivas e as geometrias de Dowling desempenham um papel tão importante na teoria matróide.

Nessa época, havia muitos outros contribuintes importantes, mas não se deve deixar de mencionar a extensão de Geoff Whittle para matróides ternários da caracterização de Tutte dos matróides binários que são representáveis ​​sobre os racionais ( Whittle 1995 ), talvez a maior contribuição individual dos anos 1990 . No período atual (desde cerca de 2000), o Matroid Minors Project de Jim Geelen , Gerards, Whittle e outros, que tenta duplicar para matróides representáveis ​​em um campo finito o sucesso do Projeto Robertson – Seymour Graph Minors (ver Robertson –Seymour teorema ), produziu avanços substanciais na teoria da estrutura de matróides. Muitos outros também contribuíram para essa parte da teoria matróide, que (nas primeiras e segundas décadas do século 21) está florescendo.

Pesquisadores

Os matemáticos que foram os pioneiros no estudo das matróides incluem Takeo Nakasawa , Saunders Mac Lane , Richard Rado , WT Tutte , BL van der Waerden e Hassler Whitney . Outros contribuidores importantes incluem Jack Edmonds , Jim Geelen , Eugene Lawler , László Lovász , Gian-Carlo Rota , PD Seymour e Dominic Welsh .

Veja também

• Antimatróide
• Coxeter matroide
• Matroide orientado
• Pré-geometria (teoria do modelo)
• Polimatróide
• Greedoid

Notas

Referências

• Bruhn, Henning; Diestel, Reinhard; Kriesell, Matthias; Pendavingh, Rudi; Wollan, Paul (2013), "Axioms for infinite matroids", Advances in Mathematics , 239 : 18–46, arXiv : 1003.3919 , doi : 10.1016 / j.aim.2013.01.011 , MR  3045140 , S2CID  10436077.
• Bryant, Victor; Perfect, Hazel (1980), Independence Theory in Combinatorics , Londres e Nova York: Chapman and Hall, ISBN 978-0-412-22430-0.
• Brylawski, Thomas H. (1972), "A decomposition for combinatorial geometries", Transactions of the American Mathematical Society , 171 : 235-282, doi : 10.2307 / 1996381 , JSTOR  1996381.
• Crapo, Henry H. (1969), "The Tutte polynomial", Aequationes Mathematicae , 3 (3): 211–229, doi : 10.1007 / BF01817442 , S2CID  119602825.
• Crapo, Henry H .; Rota, Gian-Carlo (1970), On the Foundations of Combinatorial Theory: Combinatorial Geometries , Cambridge, Mass .: MIT Press, ISBN 978-0-262-53016-3, MR  0290980.
• Geelen, Jim; Gerards, AMH; Whittle, Geoff (2007), "Towards a matroid-minor structure theory", em Grimmett, Geoffrey; et al. (eds.), Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh , Oxford Lecture Series in Mathematics and its Applications, 34 , Oxford: Oxford University Press, pp. 72-82.
• Gerards, AMH (1989), "Uma curta prova da caracterização de Tutte de matrizes totalmente unimodulares", Linear Algebra and Its Applications , 114/115: 207-212, doi : 10.1016 / 0024-3795 (89) 90461-8.
• Kahn, Jeff; Kung, Joseph PS (1982), "Varieties of combinatorial geometries", Transactions of the American Mathematical Society , 271 (2): 485–499, doi : 10.2307 / 1998894 , JSTOR  1998894.
• Kingan, Robert; Kingan, Sandra (2005), "A software system for matroids", Graphs and Discovery , DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 287-296.
• Kung, Joseph PS, ed. (1986), A Source Book in Matroid Theory , Boston: Birkhäuser, doi : 10.1007 / 978-1-4684-9199-9 , ISBN 978-0-8176-3173-4, MR  0890330.
• Mac Lane, Saunders (1936), "Algumas interpretações da dependência linear abstrata em termos de geometria projetiva", American Journal of Mathematics , 58 (1): 236-240, doi : 10.2307 / 2371070 , JSTOR  2371070.
• Minty, George J. (1966), "Sobre os fundamentos axiomáticos das teorias de gráficos lineares dirigidos, redes elétricas e programação de rede", Journal of Mathematics and Mechanics , 15 : 485-520, MR  0188102.
• Nishimura, Hirokazu; Kuroda, Susumu, eds. (2009), Um matemático perdido, Takeo Nakasawa. O pai esquecido da teoria matróide , Basel: Birkhäuser Verlag, doi : 10.1007 / 978-3-7643-8573-6 , ISBN 978-3-7643-8572-9, MR  2516551 , Zbl  1163.01001.
• Oxley, James (1992), Matroid Theory , Oxford: Oxford University Press, ISBN 978-0-19-853563-8, MR  1207587 , Zbl  0784.05002.
• Recski, András (1989), Matroid Theory and its Applications in Electric Network Theory and in Statics , Algorithms and Combinatorics, 6 , Berlin e Budapest: Springer-Verlag e Akademiai Kiado, doi : 10.1007 / 978-3-662-22143-3 , ISBN 978-3-540-15285-9, MR  1027839.
• Sapozhenko, AA (2001) [1994], "Matroid" , Encyclopedia of Mathematics , EMS Press
• Seymour, Paul D. (1980), "Decomposition of regular matroids", Journal of Combinatorial Theory, Series B , 28 (3): 305-359, doi : 10.1016 / 0095-8956 (80) 90075-1 , hdl : 10338 .dmlcz / 101946 , Zbl  0443.05027.
• Truemper, Klaus (1992), Matroid Decomposition , Boston: Academic Press, ISBN 978-0-12-701225-4, MR  1170126.
• Tutte, WT (1959), "Matroids and graphs", Transactions of the American Mathematical Society , 90 (3): 527–552, doi : 10.2307 / 1993185 , JSTOR  1993185 , MR  0101527.
• Tutte, WT (1965), "Lectures on matroids", Journal of Research of the National Bureau of Standards Section B , 69 : 1-47.
• Tutte, WT (1971), Introdução à teoria de matróides , Métodos Analíticos e Computacionais Modernos em Ciências e Matemática, 37 , Nova York: American Elsevier Publishing Company, Zbl  0231.05027.
• Vámos, Peter (1978), "O axioma perdido da teoria matróide está perdido para sempre", Journal of the London Mathematical Society , 18 (3): 403–408, doi : 10.1112 / jlms / s2-18.3.403.
• van der Waerden, BL (1937), Moderne Algebra.
• Welsh, DJA (1976), Matroid Theory , LMS Monographs, 8 , Academic Press, ISBN 978-0-12-744050-7, Zbl  0343.05002.
• White, Neil, ed. (1986), Theory of Matroids , Encyclopedia of Mathematics and its Applications, 26 , Cambridge: Cambridge University Press, ISBN 978-0-521-30937-0, Zbl  0579.00001.
• White, Neil, ed. (1987), Combinatorial geometries , Encyclopedia of Mathematics and its Applications, 29 , Cambridge: Cambridge University Press , ISBN 978-0-521-33339-9, Zbl  0626.00007
• White, Neil, ed. (1992), Matroid Applications , Encyclopedia of Mathematics and its Applications, 40 , Cambridge: Cambridge University Press, ISBN 978-0-521-38165-9, Zbl  0742.00052.
• Whitney, Hassler (1935), "On the abstract properties of linear dependence", American Journal of Mathematics , 57 (3): 509-533, doi : 10.2307 / 2371182 , hdl : 10338.dmlcz / 100694 , JSTOR  2371182 , MR  1507091. Reimpresso em Kung (1986) , pp. 55-79.
• Whittle, Geoff (1995), "A caracterização das matróides representáveis ​​sobre GF (3) e os racionais", Journal of Combinatorial Theory, Series B , 65 (2): 222-261, doi : 10.1006 / jctb.1995.1052.

links externos

• "Matroid" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Kingan, Sandra: Teoria da Matroid . Uma grande bibliografia de artigos matroid, software matroid e links.
• Locke, SC: Greedy Algorithms .
• Pagano, Steven R.: Matroids and Signed Graphs .
• Mark Hubenthal: Um breve olhar sobre os matroids ( PDF ) (contém provas para as declarações deste artigo)
• James Oxley: O que é uma matroide? (PDF)
• Neil White: aplicativos para Matroid