Motivación/intuición detrás usando álgebra lineal detrás de estos problema de combinatoria

Question

¿Cuál es la motivación detrás de usar el álgebra lineal entre estos tres problemas ?

• Un par de $(m,n)$ es llamada nice si hay un grafo dirigido con (auto borde están permitidos, pero varios borde no están permitidos) $n$ vértices tal que para cada par de vértices está conectado por exactamente $m$ caminos de longitud $2$. Demostrar $(m,n)$ es agradable iff $m \leq n$ e $\sqrt{mn} \in \mathbb{Z}$.

• Deje $S$ ser un subconjunto finito de $[0,1]$ contiene $0$ e $1$ y tales que la distancia que se produce entre parís de elementos se produce al menos dos veces, excepto por la distancia de la $1$. Demostrar que $S$ contiene sólo números racionales.

• Demostrar que $n$ distnict puntos, no todos de ellos de mentir en una línea, determinar atleast $n$ distnict líneas ?

Por "motivación", quiero decir, supongamos que usted es bueno en álgebra lineal, pero usted no sabe cómo utilizar el álgebra lineal en la combinatoria. ¿Qué tipo de estructura en el problema podría desencadenar usted que el álgebra lineal es una buena herramienta en el uso que ?

Entiendo las soluciones mediante el uso de álgebra lineal a todos estos por encima de los tres problemas, pero tengo un tiempo difícil averiguar cómo podía pensar en ellos en primer lugar - quiero decir, la transformación lineal entre espacios vectoriales y de grafo dirigido, son dos cosas completamente diferentes, ¿cómo se puede ver la conexión entre ellos ?

---

Como un ejemplo de lo que quiero decir, considerar este problema:

Deje $n$ ser un entero par. Cuántos subconjuntos del conjunto $\{1,2,\dots,n\}$ usted puede escoger si todos ellos tienen que tener impar tamaño, pero la intersección de dos cualesquiera de ellos incluso han tamaño?

Para este problema, esto por los Campos de la Medallista de Timothy Gowers da una muy buena motivación de cómo uno puede pensar en el uso de álgebra lineal (estoy queriendo este tipo de respuesta)

Si continúa experimentando de esta manera, usted va a encontrar lo mismo cada vez: si usted ha elegido menos de $n$ establece a continuación, puede elegir más, pero una vez llegas a n establece a continuación, te quedas atascado. Pero parece ser que hay una gran cantidad de libertad acerca de cómo elegir los conjuntos. Esto contrasta con muchos problemas en extremal combinatoria, donde los mejores ejemplos posibles son a menudo la única, única o hasta una cierta simetría obvia. (Un buen ejemplo de esto último: ¿cuántos subconjuntos de a$\{1,2,\dots,n\}$ se puede elegir si ninguno de sus subconjuntos es contenida en cualquiera de las otras? La única posible y de la mejor colección de juegos de todos los conjuntos de tamaño n/2.)

Existen otras circunstancias en las que usted tiene una colección de objetos, y una condición de pares $(x,y)$ de los objetos, de tal manera que (i) cada vez que usted han elegido los objetos de $x_1,x_2,\dots,x_m$ con $m<n$ hay muchas formas diferentes de elegir y tal que la condición se tiene para cada par $(x_i,y)$, y (ii) es imposible elegir más de n de ellos si cualquiera de los dos tienen que satisfacer la condición? Sí la hay: la más común es cuando los objetos son vectores en $\mathbb{R}^n$ y el estado en un par de $(x,y)$ es que x y y deben ser ortogonales. Desde ortogonalidad implica la independencia, no podemos elegir más de n vectores no nulos que son ortogonales a cada uno de los otros.

Podemos relacionar estas dos situaciones?

Answer 1

Tu pregunta tiene una respuesta en Jukna del libro Extremal Combinatoria, pero es de cinco capítulos largo (Parte III del libro) para un resumen.

Dimensionalidad es una propiedad clave que el "álgebra lineal" método hace uso de. Esencialmente álgebra lineal se puede utilizar en problemas de combinatoria donde se desea contar el número de objetos que satisfacen algún tipo de independencia de la propiedad análoga a la independencia lineal. Cuando los objetos en los problemas tienen una correspondencia uno a uno con los vectores en campos finitos o polinomios, de un determinado grado estructurado coeficientes, a continuación, estas son las sugerencias que considere el uso de álgebra lineal.