Ronald Graham - Ronald Graham

Ronald Graham
Ronald graham writing.jpg
Graham em 1998
Nascer
Ronald Lewis Graham

( 1935-10-31 )31 de outubro de 1935
Faleceu 6 de julho de 2020 (06-07-2020)(com 84 anos)
San Diego , Califórnia, EUA
Alma mater
Conhecido por
Cônjuge (s) Fan Chung (casado em 1983)
Prêmios
Carreira científica
Campos
Instituições
Tese Sobre somas finitas de números racionais  (1962)
Orientador de doutorado Derrick Henry Lehmer

Ronald Lewis Graham (31 de outubro de 1935 - 6 de julho de 2020) foi um matemático americano creditado pela American Mathematical Society como "um dos principais arquitetos do rápido desenvolvimento mundial da matemática discreta nos últimos anos". Ele foi presidente da American Mathematical Society e da Mathematical Association of America , e suas honras incluíram o Prêmio Leroy P. Steele pelo conjunto de sua obra e eleição para a Academia Nacional de Ciências .

Depois de se formar na University of California, Berkeley , Graham trabalhou por muitos anos no Bell Labs e mais tarde na University of California, San Diego . Ele fez um trabalho importante em teoria de escalonamento , geometria computacional , teoria de Ramsey e quase-aleatoriedade , e muitos tópicos em matemática foram nomeados em sua homenagem. Ele publicou seis livros e cerca de 400 artigos, e teve quase 200 co-autores, incluindo muitos trabalhos em colaboração com sua esposa Fan Chung e com Paul Erdős .

Graham apareceu em Ripley Believe It or Not! por ser não apenas "um dos maiores matemáticos do mundo", mas também um trampolinista e malabarista talentoso. Ele serviu como presidente da Associação Internacional de Malabaristas .

Biografia

Graham nasceu em Taft, Califórnia , em 31 de outubro de 1935; seu pai era um trabalhador de campo de petróleo e mais tarde marinha mercante. Apesar do interesse posterior de Graham pela ginástica, ele era pequeno e não atlético. Ele cresceu mudando-se com frequência entre a Califórnia e a Geórgia, pulando várias séries da escola nessas mudanças e nunca ficando em nenhuma escola por mais de um ano. Quando adolescente, mudou-se para a Flórida com sua mãe, agora divorciada, onde estudou, mas não concluiu o ensino médio. Em vez disso, aos 15 anos, ele ganhou uma bolsa da Fundação Ford para a Universidade de Chicago , onde aprendeu ginástica, mas não fez cursos de matemática.

Depois de três anos, quando sua bolsa expirou, ele se mudou para a Universidade da Califórnia, Berkeley , oficialmente como estudante de engenharia elétrica, mas também estudando teoria dos números com Derrick Henry Lehmer , e ganhando o título de campeão de trampolim do estado da Califórnia. Ele se alistou na Força Aérea dos Estados Unidos em 1955, quando atingiu a idade de elegibilidade, deixou Berkeley sem se formar e foi trabalhar em Fairbanks, Alasca , onde finalmente concluiu o bacharelado em física em 1959 na Universidade do Alasca Fairbanks . Retornando à Universidade da Califórnia, Berkeley para estudos de pós-graduação, ele recebeu seu Ph.D. em matemática em 1962. Sua dissertação, orientada por Lehmer, foi On Finite Sums of Rational Numbers . Enquanto estudante de pós-graduação, ele se sustentava se apresentando na cama elástica de um circo e se casou com Nancy Young, uma estudante de matemática em Berkeley; eles tiveram dois filhos.

Ronald Graham, sua esposa Fan Chung e Paul Erdős , Japão 1986

Após completar seu doutorado, Graham foi trabalhar em 1962 na Bell Labs e mais tarde como Diretor de Ciências da Informação da AT&T Labs , ambas em New Jersey . Em 1963, em uma conferência no Colorado, ele conheceu o prolífico matemático húngaro Paul Erdős (1913–1996), que se tornou um amigo próximo e frequente colaborador de pesquisa. Graham ficou decepcionado ao ser espancado no pingue-pongue por Erdős, então já na meia-idade; ele voltou para New Jersey determinado a melhorar seu jogo, e eventualmente se tornou o campeão do Bell Labs e ganhou um título estadual no jogo. Graham mais tarde popularizou o conceito de número Erdős , uma medida de distância de Erdős na rede de colaboração de matemáticos; seus muitos trabalhos com Erdős incluem dois livros de problemas em aberto e o artigo póstumo final de Erdős. Graham se divorciou na década de 1970; em 1983 ele se casou com seu colega da Bell Labs e co-autor frequente, Fan Chung .

Enquanto estava no Bell Labs, Graham também assumiu um cargo na Rutgers University como Professor da Universidade de Ciências Matemáticas em 1986, e serviu como presidente da American Mathematical Society de 1993 a 1994. Ele se tornou Cientista Chefe dos laboratórios em 1995. Ele se aposentou da AT&T em 1999, após 37 anos de serviço lá, e mudou-se para a University of California, San Diego (UCSD), como Irwin and Joan Jacobs Endowed Professor of Computer and Information Science. Na UCSD, ele também se tornou cientista-chefe do Instituto de Telecomunicações e Tecnologia da Informação da Califórnia . Em 2003-04, ele foi presidente da Mathematical Association of America .

Graham morreu de bronquiectasia em 6 de julho de 2020, aos 84 anos, em La Jolla , Califórnia.

Contribuições

Graham fez contribuições importantes em várias áreas da matemática e da ciência da computação teórica. Ele publicou cerca de 400 artigos, um quarto deles com Chung, e seis livros, incluindo Concrete Mathematics com Donald Knuth e Oren Patashnik . O Projeto Número Erdős o lista como tendo cerca de 200 co-autores. Ele foi o orientador de doutorado de nove alunos, um de cada na City University of New York e da Rutgers University enquanto estava no Bell Labs, e sete na UC San Diego.

Tópicos notáveis ​​em matemática com o nome de Graham incluem o problema Erdős – Graham nas frações egípcias , o teorema de Graham – Rothschild na teoria de Ramsey de palavras paramétricas e o número de Graham derivado dele, o teorema de Graham – Pollak e a conjectura de seixos de Graham na teoria dos grafos , o Algoritmo de Coffman – Graham para programação aproximada e desenho gráfico, e o algoritmo de varredura de Graham para cascos convexos . Ele também começou o estudo de sequências livres de primos , o problema dos triplos booleanos pitagóricos , o maior pequeno polígono e o empacotamento quadrado em um quadrado .

Graham foi um dos contribuintes das publicações de GW Peck , uma colaboração matemática pseudônima nomeada pelas iniciais de seus membros, com Graham como o "G".

Teoria dos Números

A tese de doutorado de Graham foi na teoria dos números , em frações egípcias , assim como o problema Erdős-Graham sobre se cada partição dos inteiros em classes finitas tem uma classe cujos recíprocos somam um. Uma prova foi publicada por Ernie Croot em 2003. Outro dos artigos de Graham sobre frações egípcias foi publicado em 2015 com Steve Butler e (quase 20 anos postumamente) Erdős; foi o último dos artigos de Erdős a ser publicado, tornando Butler seu 512º co-autor.

Em um artigo de 1964, Graham iniciou o estudo das sequências livres nobres observando que existem sequências de números, definidas pela mesma relação de recorrência dos números de Fibonacci , em que nenhum dos elementos da sequência é primo. O desafio de construir mais sequências desse tipo foi mais tarde assumido por Donald Knuth e outros. O livro de Graham de 1980 com Erdős, resultados antigos e novos na teoria dos números combinatória, fornece uma coleção de problemas abertos de uma ampla gama de subáreas dentro da teoria dos números.

Teoria de Ramsey

O teorema de Graham-Rothschild na teoria de Ramsey foi publicado por Graham e Bruce Rothschild em 1971 e aplica a teoria de Ramsey a cubos combinatórios em combinatória de palavras . Graham deu um grande número como limite superior para uma instância desse teorema, agora conhecido como número de Graham , que foi listado no Livro de Recordes do Guinness como o maior número já usado em uma prova matemática, embora desde então tenha sido superado por números ainda maiores, como TREE (3) .

Graham ofereceu um prêmio monetário pela solução do problema dos triplos booleanos pitagóricos , outro problema da teoria de Ramsey; o prêmio foi reivindicado em 2016. Graham também publicou dois livros sobre a teoria de Ramsey.

Teoria dos grafos

Partição das arestas do grafo completo em cinco subgráficos bipartidos completos, de acordo com o teorema de Graham-Pollak

O teorema de Graham-Pollak , que Graham publicou com Henry O. Pollak em dois artigos em 1971 e 1972, afirma que se as arestas de um gráfico -vertex completo são particionadas em subgráficos bipartidos completos , então pelo menos subgrafos são necessários. Graham e Pollak forneceram uma prova simples usando álgebra linear ; apesar da natureza combinatória da declaração e múltiplas publicações de provas alternativas desde seu trabalho, todas as provas conhecidas requerem álgebra linear.

Logo após o início da pesquisa em gráficos quase aleatórios com o trabalho de Andrew Thomason, Graham publicou em 1989 um resultado com Chung e RM Wilson que foi chamado de "teorema fundamental dos gráficos quase aleatórios", afirmando que muitas definições diferentes desses gráficos são equivalentes.

A conjectura contundente de Graham , que apareceu em um artigo de Chung em 1989, diz respeito ao número crescente de produtos cartesianos dos gráficos . Em 2019, ele permanece sem solução.

Algoritmos de embalagem, programação e aproximação

O trabalho inicial de Graham sobre a programação de job shop introduziu a razão de aproximação do pior caso no estudo de algoritmos de aproximação e lançou as bases para o desenvolvimento posterior de análise competitiva de algoritmos online . Este trabalho foi mais tarde reconhecido como importante também para a teoria do empacotamento de lixo , uma área em que Graham trabalhou mais tarde de forma mais explícita.

O algoritmo Coffman – Graham , que Graham publicou com Edward G. Coffman Jr. em 1972, fornece um algoritmo ideal para o escalonamento de duas máquinas e um algoritmo de aproximação garantido para um número maior de máquinas. Também foi aplicado no desenho de gráfico em camadas .

Em um artigo de pesquisa sobre agendamento de artigos publicado em 1979, Graham e seus co-autores introduziram uma notação de três símbolos para classificar problemas de agendamento teórico de acordo com o sistema de máquinas em que eles devem ser executados, as características das tarefas e recursos, como requisitos para sincronização ou não interrupção, e a medida de desempenho a ser otimizada. Esta classificação às vezes é chamada de "notação de Graham" ou "notação de Graham".

Geometria discreta e computacional

O algoritmo de varredura de Graham para cascos convexos

A varredura de Graham é um algoritmo prático e amplamente usado para cascos convexos de conjuntos de pontos bidimensionais, com base na classificação dos pontos e, em seguida, inserindo-os no casco em ordem classificada. Graham publicou o algoritmo em 1972.

O maior pequeno problema de polígono pede o polígono de maior área para um determinado diâmetro. Surpreendentemente, como Graham observou, a resposta nem sempre é um polígono regular . A conjectura de Graham de 1975 sobre a forma desses polígonos foi finalmente comprovada em 2007.

Em outra publicação de 1975, Graham e Erdős observaram que para os quadrados da unidade de embalagem em um quadrado maior com comprimentos laterais não inteiros, pode-se usar quadrados inclinados para deixar uma área descoberta que é sublinear no comprimento lateral do quadrado maior, ao contrário do óbvio embalagem com quadrados alinhados ao eixo. Klaus Roth e Bob Vaughan provaram que uma área descoberta pelo menos proporcional à raiz quadrada do comprimento lateral pode às vezes ser necessária; provar um limite estreito na área descoberta permanece um problema aberto.

Probabilidade e estatísticas

Na estatística não paramétrica , um artigo de Persi Diaconis e Graham de 1977 estudou as propriedades estatísticas da regra de Pearson , uma medida de correlação de classificação que compara duas permutações somando, sobre cada item, a distância entre as posições do item nas duas permutações. Eles compararam esta medida com outros métodos de correlação de classificação, resultando nas "desigualdades de Diaconis-Graham"

onde é a regra de Pearson, é o número de inversões entre as duas permutações (uma versão não normalizada do coeficiente de correlação de classificação de Kendall ) e é o número mínimo de trocas de dois elementos necessárias para obter uma permutação da outra.

O processo aleatório de Chung-Diaconis-Graham é um passeio aleatório no módulo de inteiros, um inteiro ímpar , no qual, em cada etapa, um dobra o número anterior e, em seguida, adiciona aleatoriamente zero , ou (módulo ). Em um artigo de 1987, Chung, Diaconis e Graham estudaram o tempo de mistura desse processo, motivado pelo estudo de geradores de números pseudo-aleatórios .

Malabarismo

Ronald Graham fazendo malabarismo com uma fonte de quatro bolas (1986)

Graham se tornou um malabarista competente aos 15 anos e tinha prática em fazer malabarismos com até seis bolas. (Embora uma foto publicada o mostre fazendo malabarismo com doze bolas, é uma imagem manipulada.) Ele ensinou Steve Mills , um vencedor repetido dos campeonatos da International Jugglers 'Association, a fazer malabarismos, e seu trabalho com Mills ajudou a inspirar Mills a desenvolver os Mills ' Padrão de malabarismo bagunça . Da mesma forma, Graham fez contribuições significativas para a teoria do malabarismo, incluindo uma sequência de publicações sobre siteswaps . Em 1972 foi eleito presidente da Associação Internacional de Malabaristas .

Premios e honras

Em 2003, Graham ganhou o Prêmio Leroy P. Steele anual da American Mathematical Society pelo conjunto de sua obra. O prêmio citou suas contribuições para a matemática discreta , sua popularização da matemática por meio de suas palestras e escritos, sua liderança no Bell Labs e seu serviço como presidente da sociedade. Ele foi um dos cinco vencedores inaugurais do Prêmio George Pólya da Sociedade de Matemática Industrial e Aplicada , compartilhando-o com os teóricos de Ramsey Klaus Leeb, Bruce Rothschild , Alfred Hales e Robert I. Jewett. Ele também foi um dos dois vencedores inaugurais da Medalha Euler do Instituto de Combinatória e suas Aplicações , sendo o outro Claude Berge .

Graham foi eleito para a National Academy of Sciences em 1985. Em 1999 foi nomeado ACM Fellow "pelas contribuições seminais para a análise de algoritmos, em particular a análise de pior caso de heurísticas, a teoria de escalonamento e geometria computacional" . Ele se tornou um Fellow da Society for Industrial and Applied Mathematics em 2009; o prêmio de bolsa citou suas "contribuições para a matemática discreta e suas aplicações". Em 2012, ele se tornou membro da American Mathematical Society .

Graham foi um palestrante convidado no Congresso Internacional de Matemáticos de 1982 (realizado em Varsóvia em 1983), falando sobre "Desenvolvimentos recentes na teoria de Ramsey". Ele foi duas vezes palestrante Josiah Willard Gibbs , em 2001 e 2015. A Mathematical Association of America concedeu-lhe o Prêmio Carl Allendoerfer por seu artigo "Steiner Trees on a Checkerboard" com Chung e Martin Gardner na Mathematics Magazine (1989), e o Lester Prêmio R. Ford por seu artigo "Um rápido tour pela geometria computacional" com Frances Yao no American Mathematical Monthly (1990). Seu livro Magical Mathematics com Persi Diaconis ganhou o Euler Book Prize .

Os procedimentos da conferência Integers 2005 foram publicados como um festschrift pelo 70º aniversário de Ron Graham. Outro festschrift, decorrente de uma conferência realizada em 2015 em homenagem ao 80º aniversário de Graham, foi publicado em 2018 como o livro Connections in discrete mathematics: uma celebração do trabalho de Ron Graham .

Publicações selecionadas

Livros

B1. Resultados antigos e novos na teoria dos números combinatórios. Com Paul Erdős . Monographie 28, L'Enseignement Mathématique, 1980.
B2. Teoria de Ramsey. Com Bruce Rothschild e Joel Spencer . Wiley, 1980; 2ª ed., 1990.
B3. Rudimentos da Teoria de Ramsey. American Mathematical Society, 1981; 2ª ed., Com Steve Butler , 2015.
B4. Matemática concreta: uma base para a ciência da computação . Com Donald Knuth e Oren Patashnik . Addison-Wesley, 1989; 2ª ed., 1994.
B5. Erdős em gráficos. Seu legado de problemas não resolvidos . Com Fan Chung . AK Peters, 1998.
B6. Matemática mágica: as idéias matemáticas que animam grandes truques de mágica. Com Persi Diaconis . Princeton University Press, 2011.

Volumes editados

V1. Handbook of Combinatorics. Editado com Martin Grötschel e László Lovász . MIT Press, 1995.
V2. A matemática de Paul Erdős. Editado com Jaroslav Nešetřil . 2 volumes. Springer, 1997; 2ª ed., 2013.

Artigos

A64. Graham, Ronald L. (1964). "Uma sequência de números compostos do tipo Fibonacci" (PDF) . Revista Matemática . 37 (5): 322–324. doi : 10.2307 / 2689243 . JSTOR  2689243 . MR  1571455 . Zbl  0125.02103 .
A66. Graham, RL (1966). "Limites para certas anomalias de multiprocessamento" (PDF) . Bell System Technical Journal . 45 (9): 1563–1581. doi : 10.1002 / j.1538-7305.1966.tb01709.x . Zbl  0168.40703 .
A69. Graham, RL (1969). "Limites em anomalias de tempo de multiprocessamento" (PDF) . SIAM Journal on Applied Mathematics . 17 (2): 416–429. doi : 10.1137 / 0117039 . MR  0249214 . Zbl  0188.23101 .
A71a. Graham, RL; Rothschild, BL (1971). "Teorema de Ramsey para conjuntos de n- parâmetros" (PDF) . Transactions of the American Mathematical Society . 159 : 257–292. doi : 10.1090 / S0002-9947-1971-0284352-8 . JSTOR  1996010 . MR  0284352 . Zbl  0233.05003 .
A71b. Graham, RL; Pollak, HO (1971). "Sobre o problema de endereçamento para comutação de loop" (PDF) . Bell System Technical Journal . 50 (8): 2495–2519. doi : 10.1002 / j.1538-7305.1971.tb02618.x . MR  0289210 . Zbl  0228.94020 .
A72a. Graham, RL; Pollak, HO (1972). "Sobre a incorporação de gráficos em cubos amassados". Teoria e aplicações de grafos (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicado à memória de JWT Youngs) (PDF) . Notas de aula em matemática. 303 . pp. 99-110. MR  0332576 . Zbl  0251.05123 .
A72b. Coffman, EG Jr .; Graham, RL (1972). "Agendamento ideal para sistemas de dois processadores" (PDF) . Acta Informatica . 1 (3): 200–213. doi : 10.1007 / bf00288685 . MR  0334913 . S2CID  40603807 . Zbl  0248.68023 .
A72c. Graham, RL (1972). "Um algoritmo eficiente para determinar a casca convexa de um conjunto planar finito" (PDF) . Cartas de processamento de informações . 1 (4): 132–133. doi : 10.1016 / 0020-0190 (72) 90045-2 . Zbl  0236.68013 .
A74. Johnson, DS ; Demers, A .; Ullman, JD ; Garey, MR ; Graham, RL (1974). "Limites de desempenho do pior caso para algoritmos de empacotamento unidimensional simples" (PDF) . SIAM Journal on Computing . 3 (4): 299–325. doi : 10.1137 / 0203025 . MR  0434396 . Zbl  0297.68028 .
A75a. Graham, RL (1975). "O maior pequeno hexágono" (PDF) . Journal of Combinatorial Theory . Series A. 18 (2): 165-170. doi : 10.1016 / 0097-3165 (75) 90004-7 . MR  0360353 . Zbl  0299.52006 .
A75b. Erdős, P .; Graham, RL (1975). "Sobre a embalagem de quadrados com quadrados iguais" (PDF) . Journal of Combinatorial Theory . Series A. 19 : 119–123. doi : 10.1016 / 0097-3165 (75) 90099-0 . MR  0370368 . Zbl  0324.05018 .
A77. Diaconis, Persi ; Graham, RL (1977). "A régua de pés de Spearman como medida de desordem". Journal of the Royal Statistical Society . 39 (2): 262–268. doi : 10.1111 / j.2517-6161.1977.tb01624.x . JSTOR  2984804 . MR  0652736 . Zbl  0375.62045 .
A79. Graham, RL; Lawler, EL ; Lenstra, JK ; Rinnooy Kan, AHG (1979). "Otimização e aproximação em sequenciamento e escalonamento determinísticos: um levantamento" (PDF) . Annals of Discrete Mathematics . 5 : 287–326. doi : 10.1016 / S0167-5060 (08) 70356-X . ISBN 9780080867670. MR  0558574 . Zbl  0411.90044 .
A84. Graham, RL (1984). "Desenvolvimentos recentes na teoria de Ramsey" (PDF) . Proceedings of the International Congress of Mathematicians, vol. 1, 2 (Varsóvia, 1983) . Varsóvia: PWN. pp. 1555–1567. MR  0804796 . Zbl  0572.05009 .
A87. Chung, FRK ; Diaconis, Persi ; Graham, RL (1987). "Caminhadas aleatórias que surgem na geração de números aleatórios" (PDF) . Annals of Probability . 15 (3): 1148–1165. doi : 10.1214 / aop / 1176992088 . JSTOR  2244046 . MR  0893921 . Zbl  0622.60016 .
A89a. Chung, FRK ; Graham, RL; Wilson, RM (1989). "Gráficos quase aleatórios" (PDF) . Combinatorica . 9 (4): 345–362. doi : 10.1007 / BF02125347 . MR  1054011 . S2CID  17166765 . Zbl  0715.05057 .
A89b. Chung, Fan ; Gardner, Martin ; Graham, Ron (1989). "Árvores de Steiner em um tabuleiro de xadrez" (PDF) . Revista Matemática . 62 (2): 83–96. doi : 10.2307 / 2690388 . JSTOR  2690388 . MR  0991536 . Zbl  0681.05018 .
A90. Graham, Ron; Yao, Frances (1990). "Um rápido tour pela geometria computacional" (PDF) . American Mathematical Monthly . 97 (8): 687–701. doi : 10.2307 / 2324575 . JSTOR  2324575 . MR  1072812 . Zbl  0712.68097 .
A15. Butler, Steve ; Erdős, Paul ; Graham, Ron (2015). "Frações egípcias com cada denominador tendo três divisores primos distintos" (PDF) . Inteiros . 15 : A51. MR  3437526 . Zbl  1393.11030 .

Referências

links externos