¿Interpretación categórica de los matroides?

Question

Es la primera vez que escribo, pero hace mucho tiempo que estoy aquí. Tengo una pregunta muy básica que me ha estado molestando durante algún tiempo. En concreto, no estoy seguro de cuál es la definición "correcta" de teoría de la categoría de un matroide. La única definición que conozco implica un fuerte uso de la teoría de conjuntos, y es un poco torpe:

Dado un conjunto $E$ , a matroide $\mathcal{I} \subseteq 2^E$ es una colección no vacía de subconjuntos que satisfacen los siguientes axiomas:

1. (Herencia) Si $X \in \mathcal{I}$ et $X' \subset X$ entonces $X' \in \mathcal{I}$ .

2. (Intercambio) Si $X, Y \in \mathcal{I}$ et $|X| > |Y|$ entonces existe algún $b \in X \backslash Y$ tal que $Y \cup \{ b \} \in \mathcal{I}$ .

Dado que tanto las categorías como los matroides se introdujeron más o menos al mismo tiempo y ambos fueron estudiados por MacLane, es lógico que alguien debería haber pensado en esto antes. También es obvio, a partir del axioma de la Herencia, que cada matroide es una categoría, ya que la relación de contención es reflexiva y transitiva. La segunda propiedad es un poco más difícil de modelar, ya que no estoy seguro de cómo deshacerse de los feos operadores de elemento / cardinalidad.

En la solución óptima, sería bueno deshacerse del conjunto $E$ completamente, y en su lugar ver la interpretación específica del matroide abstracto como un functor de $\mathcal{I} \to 2^E$ la red de conjuntos de potencia. Esto también sugeriría una interpretación functorial de las aplicaciones de la teoría de grafos y del álgebra lineal de los matroides. Tengo la firme sospecha de que alguien ya lo ha hecho, pero tengo grandes dificultades para encontrar referencias. (Por supuesto, también puedo estar totalmente equivocado aquí...)

Answer 1

Si entiendo bien su pregunta, creo que el problema sigue abierto. Es decir, si dejamos que $\mathcal{M}$ sea la categoría de los matroides (simples), donde los morfismos están dados por los mapas fuertes, entonces todavía está abierto cómo describir $\mathcal{M}$ por un buen conjunto de axiomas. Sin embargo, se han hecho progresos parciales en este papel .

Answer 2

El siguiente artículo relacionado fue publicado recientemente:

Heunen, C. y Patta, V., La categoría de los matroides , Appl Categor Struct (2018) 26: 205. https://doi.org/10.1007/s10485-017-9490-2

En la sección 9, los autores dan una caracterización categórica de los matroides basada en la "caracterización del algoritmo codicioso"; a grandes rasgos, la optimidad del algoritmo codicioso para todas las funciones de peso posibles se codifica como la propiedad de que los límites de ciertos diagramas son todos iguales. El artículo también comienza con una buena discusión de las diversas propiedades de la categoría de matroides y mapas fuertes mencionadas en la respuesta de Tony Huynh.

Answer 3

He llegado a la conclusión de que mucha de la estructura matemática de los conjuntos (por ejemplo, las construcciones) puede definirse mediante (combinaciones de) relaciones

$ (1) \quad S_X^F\subset F(X)\times X^{I} $

para algún conjunto subyacente X, algún functor $F$ : Rel $\rightarrow$ Rel y algún conjunto $I$ .

Ejemplos:

• Los magmas (monoides, grupos,...) se definen mediante funciones $S\subset X^2\times X$ .
• Los gráficos se definen mediante relaciones $S\subset X\times X$ .
• Los espacios métricos pueden definirse mediante relaciones $S\subset (\mathbb{R}\times X)\times X$ , donde $((r,x),x')\in S\Leftrightarrow d(x,x')=r$ . O mejor: a través de $d(x,x')\le r$ ya que la categoría Met tienen retracciones como morfismos.
• Los espacios topológicos pueden ser definidos por $S\subset 2^X\times X$ , donde $(M,x)\in S\Leftrightarrow x\in M\in\tau$ o por el cierre $x\in \overline M$ .
• Los espacios uniformes podrían definirse mediante relaciones $S\subset 2^{X\times X}\times X^2$ , donde $(U,(x,y))\in S \Leftrightarrow (x,y)$ es U-close. ( Wikipedia )

(Ver ¿Se puede caracterizar cualquier construcción como una relación? )

Esto funciona para cualquier construcción que conozco e incluso parece haber una regla general para generar los morfismos entre las construcciones, mostrada por el diagrama (en general no conmutativo, si las relaciones no son funciones) de conjuntos y relaciones: $\require{AMScd}$ \begin{CD} F(X) @>F(f)>> F(Y)\\ @V S_X^F V V(2) @VV S_Y^F V\\ X^{I} @>>f^{I}> Y^{I} \end{CD} $(2)\quad (\phi_X,\phi_Y)\in F(f)\Rightarrow [(\phi_X,(x_i)_I)\in S_X^F \Rightarrow (\phi_Y,((f(x_i))_I)\in S_Y^F]$ .

Ejemplo: Si $I=1$ , $F$ es el functor (contravariante) definido como $2^X\overset{2^f}\longrightarrow 2^Y$ , donde $ (M,M')\in 2^f\Leftrightarrow M=f^{-1}(M')$ y $S_X^F$ se define como $(M,x)\in S_X^{F}\Leftrightarrow x\in \overline{M}$ .

Entonces, debido a $(2)$ :

$M=f^{-1}(M')\Rightarrow (x\in \overline{M}\Rightarrow f(x)\in \overline{M\,'})$ Así que $x\in \overline{f^{-1}(M\,')}\Rightarrow f(x)\in \overline{M\,'}$ . (Continuidad).

En el caso de los matroides $(X,\mathcal I)$ Veo dos posibilidades que encajan en mi esquema:

1. $(A,x)\in S\Leftrightarrow x\in A\in\mathcal I$ que da una condición para los morfismos $f^{-1}(A')\in\mathcal I\Rightarrow A'\in\mathcal I'$ ;
2. $(A,x)\in S\Leftrightarrow x\in cl(A)$ que da la condición $r(f^{-1}(A'))=r(f^{-1}(A')\cup\{x\})\Rightarrow r(A')=r(A'\cup\{f(x)\})$ , donde $cl(A)=\{x\in X|r(A)=r(A\cup\{x\})\}$ et $r$ es la función de rango.

Me parece que la primera definición de un morfismo es más natural, dado el esquema, ya que el axioma de intercambio no tiene que afectar a la forma del morfismo más de lo que la asociatividad afecta a la forma del homomorfismo de grupo. Así que mi principal candidato es:

Una función $f:X\rightarrow X'$ , donde $(X,\mathcal I)$ y $(X',\mathcal I')$ son matroides, es un morfismo si se cumple para cualquier conjunto $A'\subseteq X'$ que $f^{-1}(A')\in\mathcal I \Rightarrow A'\in\mathcal I'$ .

No pretendo que esta sea la respuesta y no puedo evaluar el resultado por falta de experiencia en matroides, pero esto es lo que obtuve del esquema empírico.

Answer 4

Antes de intentar categorizar los Matroides, debemos tener en cuenta la totalidad de sus propiedades estructurales.

La clase de los Matroides es la intersección de la clase de los Greedoides con la clase de los sistemas de Independencia (es decir, Hereditarios). Si abstraemos los conjuntos independientes como puntos de un poset finito, los sistemas de Independencia son simplemente Downsets. Los Greedoides tienen una descripción más complicada. Si podemos formar una categoría de sub-conjuntos de estas clases, entonces puede ser un camino a seguir.

Sin embargo, la categorización de los sistemas de independencia (E, I) es ya un reto interesante: no sólo tienen los isomorfismos habituales que asignan elementos a elementos (E1->E2), sino que también tienen criptomorfismos (si se me permite robar y acotar la aplicación de un término), generados por las operaciones duales (complementarias) (c) y bloqueadoras (b), que conmutan con los isomorfismos. Dado que c y b son involuciones en sistemas de independencia, los criptomorfismos son invertibles y, por tanto, preservan la estructura, pero lo hacen de una manera no evidente. El mapa del conjunto de bases al conjunto de circuitos es uno de estos criptomorfismos; su inverso asigna el conjunto de bases al conjunto de hiperplanos.

Estos criptomorfismos son operaciones de mapeo de conjuntos a conjuntos, no de elementos a elementos, por lo que son isomorfismos de orden superior en teoría de conjuntos. ¿Cuál es el mejor modelo de teoría de categorías para esto? Dado que estos mapas están bien definidos en la clase de todos los sistemas de independencia, ¿se describen mejor como funtores? Si es así, ¿puede la teoría de categorías Deducir ¿se trata de una categoría? Si no es así, ¿es necesario subsumir la teoría de las categorías en un instrumento más potente de abstracción matemática?

Pero si la teoría de las categorías puede deducir b y c, ¿podemos utilizarla para descubrir operaciones criptomórficas distintas de las generadas por {b, c}?