$n \times n$ entramado gráfico con derivadas parciales acotadas por $1$ $n$ valores iguales.

Question

Yo una vez demostrado que esta pregunta hace muchos años, pero ahora se me han olvidado por completo de cómo lo hice yo. Recuerdo que siendo un divertido problema y no me importaría ver una prueba de nuevo, con la probabilidad de ser mucho más elegante de lo que mi propia prueba

The problem:

Deje $G$ ser un típico $n \times n$ cuadrícula o un cuadrado entramado gráfico. Deje $f : G \rightarrow \mathbb{Z}$ ser una función en los vértices tal que $|f(v) - f(w)| \leq 1$ si $v$ $w$ son adyacentes. Muestran que, al menos, $n$ de los vértices tienen el mismo $f$-valor.

Aside for those interested in Go:

Recuerdo que mi prueba utilizado algunas reducciones, donde terminó demostrando que los grupos en Ir con la menor cantidad de libertades por la cantidad de piedras invertido son aquellos que están aglutinadas en la esquina. Ahora no tengo idea de cómo esto se relaciona con el problema por lo que, si usted puede ver lo que yo estaba pensando en el momento, sería bueno saber.

Further questions that I find interesting:

Lo siento si abierta la discusión no es lo que este sitio es acerca, sólo algunos otros pensamientos que tuve después de escribir esto. Me preguntaba acerca de qué podemos decir acerca de otros gráficos, para satisfacer esta acotado a diferencia de la propiedad. El más conectado un gráfico, el mayor de la necesidad de mayor cantidad de igualdad de $f$-de valores que tiene que ser es. $K_n$ han $\lceil n/2\rceil $ igual $f$-valores. ¿Hay alguna norma de propiedad de un gráfico se pueden utilizar para determinar este número? ¿Qué acerca de otras dimensiones superiores celosías cuadrados?

Gracias.

Answer 1

Aha, creo que recordar cómo la prueba se va. He aquí un bosquejo de la idea:

Deje $g(c) = |S_c|$ donde $S_c = \{v \in V : f(v) \leq c\}$

Ahora desde $g$ es creciente y $g(-\infty) = 0$$g(\infty) = n^2$, hay algunos $i$ tal que $g(i) < \frac{n(n+1)}{2} + 1$ $g(i+1) \geq \frac{n(n+1)}{2}$

Supongamos que no se puede encontrar el $n$ vértices con el mismo $f$-valor,$g(i+1)-g(i)<n$. Esto significa que $\frac{n(n+1)}{2} - n \leq g(i) < \frac{n(n+1)}{2}$.

Entonces, para demostrar que cualquier subconjunto de a $g(i)$ vértices puede tener al menos $n$ vecinos al $g(i)$ está restringido a este rango. Aquí es donde he utilizado la mala idea de la forma en Ir y se dio cuenta de que la menor cantidad de vecinos se producen cuando todos estos vértices son agrupada en una esquina. Hay un par de trucos para mostrar esta última parte, permitiendo que varias de las operaciones que no aumente el prójimo tamaño y, finalmente, tirando todo a la esquina superior izquierda.

Este método podría tal vez el trabajo en general. Encontrar el mayor $n$ sobre todos los valores de $n$ $m$ para el cual se cumple lo siguiente: $n \leq \displaystyle\min_{U\subseteq G, m-n \leq |U| < m}|N(U)|$.