Diferencia entre revisiones de «Combinatoria»
Contenido eliminado Contenido añadido
→Teoría de grafos: Corregí error ortográfico Etiquetas: Edición desde móvil Edición vía web móvil |
→Combinatoria extrema: Ortografía Etiquetas: Edición desde móvil Edición vía web móvil |
||
Línea 73:
La teoría del matroide abstrae parte de la geometría. Estudia las propiedades de conjuntos (generalmente, conjuntos finitos) de vectores en un espacio vectorial que no dependen de los coeficientes particulares en una relación de dependencia lineal. No sólo la estructura sino también las propiedades enumerativas pertenecen a la teoría del matroide. La teoría del matroide fue introducida por Hassler Whitney y estudiada como parte de la teoría del orden. Ahora es un campo de estudio independiente con una serie de conexiones con otras partes de la combinatoria.
===Combinatoria extrema===
La combinatoria extrema estudia las preguntas extremas sobre los sistemas de conjuntos. Los tipos de preguntas abordadas en este caso son sobre el mayor grafo posible que satisface ciertas propiedades. Por ejemplo, el mayor grafo libre de triángulos en 2n vértices es un grafo bipartito completo Kn, n. A menudo es demasiado difícil incluso para encontrar la respuesta extrema f (n) exactamente y sólo se puede dar una estimación asintótica. La teoría de Ramsey es otra parte de la combinatoria extrema. Indica que cualquier configuración suficientemente grande contendrá algún tipo de orden. Es una generalización avanzada del principio del palomar.
===Combinatoria probabilística===
En la combinatoria probabilística, las preguntas son del tipo siguiente: ¿cuál es la probabilidad de una cierta propiedad para un objeto aleatorio discreto, tal como un grafo al azar? Por ejemplo, ¿cuál es el número promedio de triángulos en un grafo al azar? Los métodos probabilísticos también se utilizan para determinar la existencia de objetos combinatorios con ciertas propiedades prescritas (para las cuales pueden ser difíciles de encontrar ejemplos explícitos), simplemente observando que la probabilidad de seleccionar aleatoriamente un objeto con esas propiedades es mayor que 0. Este enfoque (a menudo referido como el método probabilístico) demostró ser altamente eficaz en aplicaciones a la combinatoria extremal y a la teoría de los grafos. Un área estrechamente relacionada es el estudio de cadenas de Markov finitas, especialmente en objetos combinatorios. Aquí también se utilizan herramientas probabilísticas para estimar el tiempo de mezclado.
| |||