Ron L. Graham menos conocidos contribuciones significativas

Question

Ron L. Graham es tristemente ya no está con nosotros.

Fue muy prolífico y su obra se extendió por varias áreas de las matemáticas, incluyendo la teoría de grafos, geometría computacional, teoría de Ramsey, y cuasi-aleatoriedad. Su larga asociación con Paul Erdős es, por supuesto, muy bien conocido. Graham número, y Graham-Rothschild teorema, y el maravilloso libro Concreto las Matemáticas son otros bien conocidos contribuciones.

Sin embargo, algunas de sus contribuciones no podrá ser como es ampliamente conocido, pero merecen ser así. Esta pregunta es para animar a la gente a comentar sobre dichas contribuciones. Yo no estoy familiarizado con su trabajo en la programación de la teoría, por ejemplo.

Fue en trucos de magia y las matemáticas detrás de ellos y co-autor de un libro sobre esto con Persi Diaconis. Y fue en malabares, como Claude Shannon.

Edit: Gracias a @LSpice para señalar la Meta MathOverflow hilo aquí en anécdotas personales.

Answer 1

El más grande de hexágono pequeño determina el área más grande que un avión hexágono de la unidad de diámetro puede tener. (No, no es el hexágono regular!) Me encanta el título. Para más resultados en esta dirección, la búsqueda de Mossinghoff del trabajo en isodiamétricos polígonos.

Answer 2

R. L. Graham, Una de Fibonacci como la secuencia de compuesto de números, las Matemáticas de la Revista, Vol. 37, Nº 5 (Nov., 1964), pp 322-324.

Graham definidas $S(L_0,L_1)=(L_0,L_1,L_2,\dots)$ a ser una secuencia de números de la satisfacción de $L_{n+2}=L_{n+1}+L_n$ para $n=0,1,\dots$. Él encontró relativamente números primos $M,N$ tal que cada término de $S(M,N)$ es compuesto.

Answer 3

Junto con Chung, Diaconis, y Holmes, se determinó que existen significa 17.152 diferentes disposiciones de la "Stomachion" tangram rompecabezas en una plaza. A ver, aquí un buen resumen.

El rompecabezas se atribuye a Arquímedes. Hay algunas pruebas de que Arquímedes podría haber estado haciendo similar contar; después de todo, Hough enseñó a nosotros que Helenística Griegos tenían algunos relativamente sofisticados de la combinatoria.

Yo vagamente recuerdo ver un video en la década del 2000, en la cual Diaconis y Holmes voló hacia abajo para visitar Chung y Graham; los cuatro de ellos hizo el recuento de un fin de semana.

Answer 4

Tengo un punto suave de La cubierta del polinomio de un dígrafo (en co-autoría con Fan Chung), ya que fue uno de los dos papeles que motivó mi Tel. D. tesis problema. La cubierta del polinomio es una especie de dígrafo analógica del polinomio de Tutte. Más tarde se generalizó a la matriz de la cubierta del polinomio.

Una cosa buena acerca de la cubierta del polinomio es que responda a un lugar inesperado combinatoria teorema de reciprocidad. Anteriormente se conocía que la torre polinomio de una junta determina la torre polinomio de su complemento, pero la definición de la cubierta del polinomio permite que esta relación se expresa de una manera muy agradable de combinatoria manera. He continuado cosechando los beneficios de Chung y Graham insight; sólo un par de años atrás, una generalización de este teorema de la reciprocidad siempre un paso clave en un documento conjunto de la mina con Patrick Brosnan, lo que demuestra una conjetura de Shareshian y Wachs regular semisimple Hessenberg variedades.

Answer 5

El siguiente fue publicado por Stuart Margolis en mi Facebook. Espero que no me importa incluyendo ligeramente editada.

Ron Graham escribió un par de artículos en lo finito semigroups en la década de 1960 que se conoce sólo a las Rodas de la escuela de semigroups durante muchos años. Han sido redescubierta en los últimos años y están tan frescas y importantes hoy como lo fueron hace más de medio siglo.

El papel:

"En la Finita O-Simple Semigroups y la Teoría de grafos", R. Graham, MATEMÁTICO de la TEORÍA de SISTEMAS, Vol 2, NO. 4, 325-339, 1968,

fue el primer documento a evaluar de forma explícita finito 0-simple semigroups como bipartito grupo etiquetados gráficos (también llamado ganancia gráficas de voltaje, los gráficos y otros nombres). Entre los muchos resultados, tiene la hermosa teorema que clasifica finito 0-simple semigroups cuya idempotente generado subsemigroup sólo ha trivial subgrupos y idempotente generado subsemigroups de finito 0-simple semigroups en general. Por un resultado de Des FitzGerald este trabajo puede ser extendido el estudio a idempotente generado subsemigroups para todos finito semigroups.

Los resultados fueron descubiertos más tarde y dar más topológico sabor por C. H. Houghton en la década de 1970. El llamado Graham-Houghton gráfica de un 0-simple semigroup ha sido una herramienta de gran importancia en una floreciente literatura sobre idempotente generado semigroups que ha aparecido en los últimos años.

Un tratamiento de este trabajo aparece en la sección 4.13 del Rhodes-Steinberg libro, "El P-Teoría de Finito Semigroups".

El papel:

Máxima Subsemigroups de Finito Semigroups* N. GRAHAM, R. GRAHAM, Y J. RHODES, REVISTA DE TEORÍA COMBINATORIA 4, 203 a 209 (1968) hace exactamente lo que su título dice: describe la máxima subsemigroups de finito semigroups.

El papel seguía siendo en gran parte desconocido para muchos años y llega redescubierto cada tan a menudo. En los últimos años, el papel de "Cadenas de subsemigroups" por Cameron, Gadouleau, Mitchell y Peresse utiliza estos resultados para estudiar la más larga de la cadena de subsemigroups de un número finito de semigroup.