Es fácil ver que en los grafos bipartitos libres de triángulos máximos (n vértices), el grado máximo es al menos $\lceil n/2 \rceil$ . ¿Qué pasa con los gráficos mtf en general? ¿Debe haber siempre algún vértice de alto grado? Antes de lanzarme con los dos pies, ¿hay alguna razón obvia por la que no pueda haber una constante absoluta $c$ tal que para cada mtf $G$ , $\Delta(G) > cn$ ? ¿Un contraejemplo práctico de c = 1/4?
Respuestas
¿Demasiados anuncios?
Hay una secuencia de Kneser gráficos, la generalización de la Petersen gráfico, que consta de un contraejemplo.
Deje $k \ge 1$ ser un número entero y deje $G$ ser un grafo cuyos vértices son subconjuntos de tamaño $k$$\{1,2,\ldots,3k-1\}$. Conecta dos vértices $A$ $B$ por una arista si son disjuntos como subconjuntos. A continuación, $G$ no tiene triángulos, porque no hay espacio para tres subconjuntos disjuntos. Por otro lado, si $A$ $B$ no están conectados por una arista, es decir, que no son disjuntas, hay espacio para un tercer set $C$ que es disjunta de dos de ellos. Por lo tanto si quiere agregar cualquier borde de la $(A,B)$ este gráfico $G$, se forma un triángulo con $(A,C)$$(B,C)$.
Ahora vamos a contar vértices y aristas. El gráfico de $G$ $\binom{3k-1}{k}$ vértices, y cada vértice tiene $\binom{2k-1}{k}$ bordes. QED
(Es el gráfico de Petersen al $k=2$.)
Esto se debe en parte plagiar a los de David perspicaz respuesta de abajo, pero no puedo resistir un anexo a sus comentarios. En el papel, El triángulo de proceso, Tom Bohman simplifica la construcción de Kim que David de la cites. Él hace una máxima triángulo de libre gráfico en $n$ vértices en el uso más simple plausible método: El azar algoritmo voraz. El resultado es un gráfico que es estadísticamente muy predecible. Su número de independencia es casi siempre $\Theta(\sqrt{n \log n})$, y por lo tanto también lo es su máximo de valencia. Su promedio de valencia también está en la misma clase. Usted puede hacer fácilmente gráficos como este sí mismo con un simple programa de ordenador y ver sus propiedades. Es irónico, pero un tema común, que un muy aleatorio simple algoritmo es más eficiente que un altamente simétrica de la construcción, tales como la Kneser gráficos.
Como explica David, se obtiene una inmediata inferior límite máximo de valencia $\Omega(n^{1/2})$ para cualquier gráfico de diámetro 2 o incluso radio 2. El Kneser gráficos anteriores tienen valence $O(n^\alpha)$$\alpha = \log_{27/4}(4) \approx 0.726$. Así que el Kim-Bohman resultado es mucho más fuerte, y es por eso que señaló Kim papel.
De hecho, este resultado se cierra un círculo para mí. Un triángulo de libre gráfico en $n$ vértices es también un tipo de "diseño de embalaje", en la que cada triple de vértices sólo tiene espacio para dos bordes. El documento original que presentó el azar algoritmo voraz en el tema de los diseños de los empaques es por Gordon, Kuperberg, Patashnik, y Spencer. En ese papel, nos quedamos mirando los diseños de los empaques en el extremo opuesto, por ejemplo, la elección de tripletas de puntos con una muestra aleatoria de algoritmo voraz de tal manera que ningún borde está contenida en más de una triple. (El papel dice que abarcan diseños, pero en nuestro extremo de la asymptotics, que son casi los mismos que los diseños de los empaques.) Es el mismo altamente predecible fenómeno en ambos extremos. Una de las ideas que en este papel era simplificar un aficionado de la construcción el uso de "Rödl nibbles" al azar algoritmo voraz. Bohman es hacer la misma cosa (pero con mucho más fuerte asymptotics que en nuestro estudio), porque Kim también utiliza Rödl nibbles.
Flow
Puntos
14132
Una máxima del triángulo de libre gráfico tiene un diámetro de dos, por lo que su anchura de árbol de expansión tiene un vértice con un número de niños que es, al menos, proporcional a $\sqrt n$.
Tengo la sensación de que debería ser posible cocinar una coincidencia de $O(\sqrt n)$ límite superior en el grado máximo, mediante la incidencia de los gráficos de los puntos y líneas en un plano proyectivo, pero que no acaba de funcionar: es el triángulo libre (y bipartito), tiene su grado máximo $O(\sqrt n)$, y evita la adición de más punto a punto o de línea de la línea de los bordes, pero no es un obstáculo para añadir más puntos de la línea de los bordes.
(Editar para agregar, después de Greg dejó un comentario en una versión anterior de esta respuesta): Ver el Kim 1995 referencia de http://en.wikipedia.org/wiki/Triangle-free_graph:
Kim, J. H. (1995), "El número de Ramsey $R(3,t)$ tiene un orden de magnitud de $\frac{t^2}{\log t}$", al Azar de Algoritmos y Estructuras de las 7: 173-207 .
Él describe la construcción de un triángulo de libre gráfico en el que cada conjunto independiente tiene el tamaño de $O(\sqrt{n\log n})$. Si uno hace el gráfico máxima, esto no aumentar el tamaño de sus conjuntos independientes. Pero en un triángulo de libre gráfico, los vecinos de cada vértice forman un conjunto independiente, por lo que el maximalized versión de Kim gráfico tiene un grado $O(\sqrt{n\log n})$.
