โรนัลด์ เกรแฮม
เกรแฮมในปี 1998
เกิด	โรนัลด์ ลูอิส เกรแฮม ( 31 ตุลาคม 1935 )31 ตุลาคม พ.ศ. 2478 ทาฟต์ รัฐแคลิฟอร์เนียสหรัฐอเมริกา
เสียชีวิต	6 กรกฎาคม 2563 (6 กรกฎาคม 2020)(อายุ 84 ปี) ซานดิเอโก รัฐแคลิฟอร์เนีย สหรัฐอเมริกา
อัลมา มัธยฐาน	มหาวิทยาลัยอะแลสกา แฟร์แบงค์ ส ( วิทยาศาสตรบัณฑิต ) มหาวิทยาลัยแคลิฟอร์เนีย เบิร์กลีย์ ( ปริญญาเอก )
เป็นที่รู้จักในด้าน	อัลกอริทึมคอฟฟ์แมน-เกรแฮม ปัญหา Erdős–Graham หมายเลขของเกรแฮม การสแกนของเกรแฮม ทฤษฎีบทเกรแฮม-พอลแล็ก สัญกรณ์การจัดตารางงานที่เหมาะสมที่สุด
คู่สมรส	ฟาน ชุง ​ ( ม.ค.  1983 )
รางวัล	รางวัลโปลยา (ปี 1971) สถาบันวิทยาศาสตร์แห่งชาติ (1985) รางวัลสตีล (ปี 2003)
เส้นทางอาชีพด้านวิทยาศาสตร์
ฟิลด์	คณิตศาสตร์ วิทยาการคอมพิวเตอร์
สถาบันต่างๆ	เบลล์แล็บส์ เอทีแอนด์ที แล็บส์ แคล-(ไอที) 2 ยูซีเอสดี
วิทยานิพนธ์	ว่าด้วยผลรวมจำกัดของจำนวนตรรกยะ (1962)
อาจารย์ที่ปรึกษาปริญญาเอก	เดอร์ริค เฮนรี เลห์เมอร์

โรนัลด์ ลูอิส เกรแฮม (31 ตุลาคม พ.ศ. 2478 – 6 กรกฎาคม พ.ศ. 2563) ^{[ 1 ]}เป็นนักคณิตศาสตร์ ชาวอเมริกัน ที่ได้รับการยกย่องจากสมาคมคณิตศาสตร์อเมริกันว่าเป็น "หนึ่งในสถาปนิกหลักของการพัฒนาอย่างรวดเร็วของคณิตศาสตร์เชิงดิสครีต ทั่วโลก ในช่วงไม่กี่ปีที่ผ่านมา" ^{[ 2 ]} เขาดำรงตำแหน่งประธานของทั้งสมาคมคณิตศาสตร์อเมริกันและสมาคมคณิตศาสตร์แห่งอเมริกาและเกียรติยศของเขารวมถึงรางวัลเลอรอย พี. สตีลสำหรับความสำเร็จตลอดชีวิตและการได้รับเลือกเข้าสู่สถาบัน วิทยาศาสตร์แห่งชาติ

หลังจากสำเร็จการศึกษาระดับบัณฑิตศึกษาที่มหาวิทยาลัยแคลิฟอร์เนีย เบิร์กลีย์เกรแฮมทำงานเป็นเวลาหลายปีที่เบลล์แล็บส์และต่อมาที่มหาวิทยาลัยแคลิฟอร์เนีย ซานดิเอโกเขาทำงานสำคัญในทฤษฎีการจัดตารางเวลา เรขาคณิตเชิงคำนวณทฤษฎีแรมซีย์และความสุ่มแบบกึ่งๆ [ ^{3 ] และ}มีหลายหัวข้อในคณิตศาสตร์ที่ตั้งชื่อตามเขา เขาตีพิมพ์หนังสือ 6 เล่มและบทความประมาณ 400 เรื่อง และมีผู้ร่วมเขียนเกือบ 200 คน รวมถึงงานร่วมกันมากมายกับภรรยาของเขาแฟน ชุงและกับพอล เออร์โดส

เกรแฮมได้รับการกล่าวถึงในRipley's Believe It or Not!ว่าเป็นไม่เพียงแต่ "หนึ่งในนักคณิตศาสตร์ชั้นนำของโลก" แต่ยังเป็นนักเล่นแทรมโพลีนและนักเล่นกลที่ประสบความสำเร็จอีกด้วย เขาดำรงตำแหน่งประธานสมาคมนักเล่นกลนานาชาติ^{[ 3 ] [ 4 ] [ 5 ]}

เกรแฮมเกิดที่เมืองทาฟต์ รัฐแคลิฟอร์เนียเมื่อวันที่ 31 ตุลาคม พ.ศ. 2478 ^{[ 6 ]}บิดาของเขาเป็นคนงานในบ่อน้ำมันและต่อมาเป็นกะลาสีเรือพาณิชย์ แม้ว่าเกรแฮมจะสนใจยิมนาสติกในภายหลัง แต่เขาก็ตัวเล็กและไม่แข็งแรง^{[ 7 ]}เขาเติบโตมาโดยย้ายไปมาระหว่างแคลิฟอร์เนียและจอร์เจียบ่อยครั้ง ข้ามชั้นเรียนไปหลายชั้นในระหว่างการย้ายเหล่านี้ และไม่เคยอยู่ที่โรงเรียนใดโรงเรียนหนึ่งนานเกินหนึ่งปี^{[ 1 ] [ 7 ]}ในวัยรุ่น เขาได้ย้ายไปฟลอริดากับมารดาที่หย่าร้างแล้ว ซึ่งเขาได้เข้าเรียนมัธยมปลายแต่เรียนไม่จบ ในทางกลับกัน เมื่ออายุ 15 ปี เขาได้รับ ทุนการศึกษา จากมูลนิธิฟอร์ด เพื่อเข้าเรียน ที่มหาวิทยาลัยชิคาโกซึ่งเขาได้เรียนยิมนาสติกแต่ไม่ได้เรียนวิชาคณิตศาสตร์^{[ 1 ]}

หลังจากสามปี เมื่อทุนการศึกษาของเขาหมดอายุลง เขาจึงย้ายไปที่มหาวิทยาลัยแคลิฟอร์เนีย เบิร์กลีย์โดยเป็นนักศึกษาวิศวกรรมไฟฟ้าอย่างเป็นทางการ แต่ยังศึกษาทฤษฎีจำนวนภายใต้การ ดูแลของ DH Lehmer [ ^{1 ] และ}ได้รับตำแหน่งแชมป์แทรมโพลีนของรัฐแคลิฟอร์เนีย^{[ 7 ]}เขาเข้าร่วมกองทัพอากาศสหรัฐฯในปี 1955 เมื่อถึงวัยที่มีสิทธิ์^{[ 8 ]}ออกจากเบิร์กลีย์โดยไม่มีปริญญา และประจำการอยู่ที่แฟร์แบงค์ รัฐอะแลสกาซึ่งในที่สุดเขาก็สำเร็จการศึกษาระดับปริญญาตรีสาขาฟิสิกส์ในปี 1959 ที่มหาวิทยาลัยอะแลสกา แฟร์แบงค์ [ ^{1 ] กลับ}มาที่เบิร์กลีย์เพื่อศึกษาต่อในระดับบัณฑิตศึกษา เขาได้รับปริญญาเอกสาขาคณิตศาสตร์ในปี 1962 วิทยานิพนธ์ของเขาซึ่งมี Lehmer เป็นอาจารย์ที่ปรึกษาคือ เรื่อง ผลรวม จำกัดของจำนวนตรรกยะ^{[ 9 ]}ขณะเป็นนักศึกษาปริญญาโท เขาเลี้ยงชีพด้วยการแสดงบนแทรมโพลีนในคณะละครสัตว์^{[ 8 ]}และแต่งงานกับแนนซี ยัง นักศึกษาปริญญาตรีสาขาคณิตศาสตร์ที่เบิร์กลีย์ พวกเขามีลูกสองคน^{[ 1 ]}

หลังจากสำเร็จการศึกษาระดับปริญญาเอก เกรแฮมได้ไปทำงานที่Bell Labs ในปี 1962 และต่อมาดำรงตำแหน่งผู้อำนวยการฝ่ายวิทยาศาสตร์สารสนเทศที่AT&T Labsทั้งสองแห่งอยู่ในรัฐนิวเจอร์ซีย์ในปี 1963 ในการประชุมที่รัฐโคโลราโด เขาได้พบกับนักคณิตศาสตร์ชาวฮังการีPaul Erdős (1913–1996) ^{[ 1 ]}ซึ่งต่อมากลายเป็นเพื่อนสนิทและผู้ร่วมงานวิจัยบ่อยครั้ง เกรแฮมรู้สึกผิดหวังที่พ่ายแพ้ให้กับ Erdős ในการเล่นปิงปองซึ่งในขณะนั้น Erdős มีอายุมากแล้ว เขาจึงกลับไปที่นิวเจอร์ซีย์ด้วยความมุ่งมั่นที่จะพัฒนาฝีมือ และในที่สุดก็กลายเป็นแชมป์ของ Bell Labs และได้รับรางวัลชนะเลิศระดับรัฐในเกมนี้^{[ 1 ]}ต่อมาเกรแฮมได้เผยแพร่แนวคิดของจำนวน Erdősซึ่งเป็นการวัดระยะห่างจาก Erdős ในเครือข่ายความร่วมมือของนักคณิตศาสตร์^{[ 10 ] [ 8 ]}ผลงานมากมายของเขากับ Erdős รวมถึงหนังสือสองเล่มเกี่ยวกับปัญหาที่ยังแก้ไม่ตก^{[B1] [B5]}และบทความสุดท้ายของ Erdős ที่ตีพิมพ์หลังเสียชีวิต^[A15]เกรแฮมหย่าร้างในช่วงทศวรรษ 1970 และในปี 1983 เขาแต่งงานกับแฟน ชุงเพื่อน ร่วมงานจากเบลล์แล็บส์และผู้ร่วมเขียนบทความบ่อยครั้ง ^{[ 1 ]}

ขณะอยู่ที่ Bell Labs แกรแฮมยังดำรงตำแหน่งศาสตราจารย์ด้านวิทยาศาสตร์คณิตศาสตร์ที่มหาวิทยาลัยรัตเกอร์สในปี 1986 และดำรงตำแหน่งประธานสมาคมคณิตศาสตร์อเมริกันตั้งแต่ปี 1993 ถึง 1994 เขาได้เป็นหัวหน้านักวิทยาศาสตร์ของห้องปฏิบัติการในปี 1995 ^{[ 1 ]}เขาเกษียณจาก AT&T ในปี 1999 หลังจากรับราชการมา 37 ปี^{[ 11 ]}และย้ายไปที่มหาวิทยาลัยแคลิฟอร์เนีย ซานดิเอโก (UCSD) ในตำแหน่งศาสตราจารย์ด้านวิทยาการคอมพิวเตอร์และสารสนเทศที่ได้รับทุนสนับสนุนจาก Irwin และ Joan Jacobs ^{[ 1 ] [ 8 ]}ที่ UCSD เขายังได้เป็นหัวหน้านักวิทยาศาสตร์ที่ สถาบัน เทคโนโลยีโทรคมนาคมและสารสนเทศแห่งแคลิฟอร์เนีย อีกด้วย ^{[ 8 ] [ 5 ]}ในปี 2003–04 เขาเป็นประธานสมาคมคณิตศาสตร์แห่งอเมริกา^{[ 1 ]}

เกรแฮมเสียชีวิตด้วยโรคหลอดลมโป่งพอง^{[ 12 ]}เมื่อวันที่ 6 กรกฎาคม 2020 ขณะอายุ 84 ปี ที่ลาจอลลารัฐแคลิฟอร์เนีย^{[ 6 ] [ 13 ]}

เกรแฮมมีส่วนสำคัญในหลายสาขาของคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎี เขาตีพิมพ์บทความประมาณ 400 เรื่อง โดยหนึ่งในสี่ของบทความเหล่านั้นเขียนร่วมกับชุง^{[ 14 ]}และหนังสือ 6 เล่ม รวมถึงConcrete Mathematicsร่วมกับโดนัลด์ คนูธและโอเรน ปาตาชนิก [ ^B4]โครงการ Erdős Number Project ระบุว่าเขามีผู้ร่วมเขียนเกือบ 200 คน^{[ 15 ]}เขาเป็นอาจารย์ที่ปรึกษาปริญญาเอกของนักศึกษา 9 คน โดยแต่ละคนเรียนที่City University of New YorkและRutgers Universityขณะที่เขาอยู่ที่ Bell Labs และอีก 7 คนที่ UC San Diego ^{[ 9 ]}

หัวข้อสำคัญในคณิตศาสตร์ที่ตั้งชื่อตามเกรแฮม ได้แก่ปัญหาเออร์โดส-เกรแฮมเกี่ยวกับเศษส่วนอียิปต์ ทฤษฎีบท เกรแฮม-รอธส์ไชลด์ใน ทฤษฎี คำพารามิเตอร์ของแรมซีย์และจำนวนของเกรแฮมที่ได้มาจากทฤษฎีบทนี้ทฤษฎีบทเกรแฮม-พอลแล็กและข้อสันนิษฐานการโปรยหินของเกรแฮมในทฤษฎีกราฟอัลกอริทึมคอฟฟ์แมน-เกรแฮมสำหรับการจัดตารางเวลาโดยประมาณและการวาดกราฟ และ อัลกอริทึม การสแกนของเกรแฮมสำหรับรูปทรงนูนนอกจากนี้ เขายังเริ่มต้นการศึกษาลำดับที่ไม่มีจำนวนเฉพาะปัญหาสามเหลี่ยมพีทาโกเรียนแบบบูลีนรูปหลายเหลี่ยมเล็กที่ใหญ่ที่สุดและการจัดเรียงสี่เหลี่ยมในสี่เหลี่ยม

เกรแฮมเป็นหนึ่งในผู้มีส่วนร่วมในการตีพิมพ์ของGW Peckซึ่งเป็นกลุ่มความร่วมมือทางคณิตศาสตร์ที่ใช้นามแฝง โดยตั้งชื่อตามอักษรย่อของสมาชิก และเกรแฮมเป็น "G" ^{[ 16 ]}เกรแฮมยังเขียนบทความเกี่ยวกับจำนวน Erdős โดยใช้นามแฝงว่า Tom Odda ^{[ 17 ] [ 18 ]}

วิทยานิพนธ์ปริญญาเอกของ Graham อยู่ในสาขาทฤษฎีจำนวนเกี่ยวกับเศษส่วนอียิปต์ [ ^{7 ] [ 9 ]}เช่นเดียวกับปัญหา Erdős–Grahamที่ว่า สำหรับทุกการแบ่งจำนวนเต็มออกเป็นคลาสจำนวนจำกัด คลาสใดคลาสหนึ่งจะมีคลาสย่อยจำกัดซึ่งผลรวมของส่วนกลับเท่ากับหนึ่งหรือไม่ บทพิสูจน์ได้รับการตีพิมพ์โดย^Ernie Crootในปี 2003 ^{[ 19 ]}บทความอีกฉบับหนึ่งของ Graham เกี่ยวกับเศษส่วนอียิปต์ได้รับการตีพิมพ์ในปี 2015 ร่วมกับSteve Butlerและ (เกือบ 20 ปีหลังการเสียชีวิต) Erdős ซึ่งเป็นบทความสุดท้ายของ Erdős ที่ได้รับการตีพิมพ์ ทำให้ Butler เป็นผู้ร่วมเขียนคนที่ 512 ของเขา^{[A15] [ 20 ]}

ในบทความปี 1964 เกรแฮมเริ่มศึกษาลำดับที่ไม่มีจำนวนเฉพาะโดยสังเกตว่ามีลำดับของตัวเลขที่กำหนดโดยความสัมพันธ์เวียนเกิด เดียวกัน กับจำนวนฟิโบนาชชีซึ่งไม่มีสมาชิกใดในลำดับนั้นเป็นจำนวนเฉพาะ^[A64]ความท้าทายในการสร้างลำดับดังกล่าวเพิ่มเติมได้รับการสานต่อโดยโดนัลด์ คนูธและคนอื่นๆ ในภายหลัง ^{[ 21 ]}หนังสือของเกรแฮมในปี 1980 ร่วมกับเออร์โดส เรื่องผลลัพธ์เก่าและใหม่ในทฤษฎีจำนวนเชิงการจัดเรียงให้การรวบรวมปัญหาที่ยังเปิดอยู่จากหลากหลายสาขาย่อยภายในทฤษฎีจำนวน^[B1]

ทฤษฎีบทGraham–Rothschildในทฤษฎี Ramseyได้รับการตีพิมพ์โดย Graham และBruce Rothschildในปี 1971 และประยุกต์ใช้ทฤษฎี Ramsey กับลูกบาศก์เชิงคอมบินาทอริกใน คอมบินาทอริก บนคำ^[A71a] Graham ได้ให้จำนวนมากเป็นขอบเขตบนสำหรับกรณีหนึ่งของทฤษฎีบทนี้ ซึ่งปัจจุบันรู้จักกันในชื่อจำนวนของ Grahamซึ่งได้รับการบันทึกไว้ในGuinness Book of Recordsว่าเป็นจำนวนที่ใหญ่ที่สุดที่เคยใช้ในการพิสูจน์ทางคณิตศาสตร์^{[ 22 ]}แม้ว่าหลังจากนั้นจะมีจำนวนที่มากกว่านั้นมาแซงหน้า เช่นTREE(3 ) ^{[ 23 ]}

เกรแฮมเสนอเงินรางวัลสำหรับการแก้ปัญหาสามเหลี่ยมพีทาโกเรียน บูลีน ซึ่งเป็นอีกปัญหาหนึ่งในทฤษฎีแรมซีย์ รางวัลนี้ถูกรับไปในปี 2016 ^{[ 24 ]} เกรแฮมยังได้ตีพิมพ์หนังสือสองเล่มเกี่ยวกับทฤษฎีแรมซีย์อีกด้วย^{[B2] [B3]}

ทฤษฎีบทGraham–Pollakซึ่ง Graham ได้ตีพิมพ์ร่วมกับHenry O. Pollakในเอกสารสองฉบับในปี 1971 และ 1972 ^{[A71b] [A72a]}ระบุว่า หากขอบของกราฟสมบูรณ์ที่มีจุดยอด - จุดถูกแบ่งออกเป็นกราฟย่อยแบบสองส่วนสมบูรณ์จะต้องอาศัยกราฟย่อยอย่างน้อย กราฟ Graham และ Pollak ได้ให้การพิสูจน์อย่างง่ายโดยใช้ พีชคณิตเชิงเส้นแม้ว่าข้อความดังกล่าวจะมีลักษณะเชิงการจัดเรียงและมีการตีพิมพ์การพิสูจน์ทางเลือกอื่นๆ หลายครั้งนับตั้งแต่ผลงานของพวกเขา แต่การพิสูจน์ที่ทราบทั้งหมดล้วนต้องใช้พีชคณิต เชิงเส้น ^{[ 25 ]}${\displaystyle n}$${\displaystyle n-1}$

ไม่นานหลังจากที่การวิจัยเกี่ยวกับกราฟกึ่งสุ่มเริ่มต้นขึ้นด้วยงานของ Andrew Thomason Graham ได้ตีพิมพ์ผลลัพธ์ร่วมกับ Chung และRM Wilson ในปี 1989 ซึ่งได้รับการขนานนามว่าเป็น "ทฤษฎีบทพื้นฐานของกราฟกึ่งสุ่ม" โดยระบุว่าคำจำกัดความที่แตกต่างกันมากมายของกราฟเหล่านี้มีความเทียบเท่ากัน^{[A89a] [ 26 ]}

ข้อสันนิษฐานเรื่องก้อนกรวดของเกรแฮมซึ่งปรากฏในบทความปี 1989 โดยชุง^{[ 27 ]}เป็นปัญหาที่ยังเปิดอยู่เกี่ยวกับจำนวนก้อนกรวดของผลคูณคาร์ทีเซียนของกราฟ^{[ 28 ]}

งานในช่วงแรกของ Graham เกี่ยวกับการจัดตารางงานในโรงงาน^{[A66] [A69]}ได้นำอัตราส่วนการประมาณค่ากรณี เลวร้ายที่สุดมา ใช้ในการศึกษาอัลกอริทึมการประมาณค่าและวางรากฐานสำหรับการพัฒนาการวิเคราะห์เชิงแข่งขันของอัลกอริทึมออนไลน์ใน ภายหลัง ^{[ 29 ]}งานนี้ได้รับการยอมรับในภายหลังว่ามีความสำคัญต่อทฤษฎีการบรรจุกล่องด้วย [ ^{30 ] ซึ่ง}เป็นสาขาที่ Graham ทำงานอย่างชัดเจนมากขึ้นในภายหลัง^[A74]

อัลกอริทึม Coffman–Grahamซึ่ง Graham ได้ตีพิมพ์ร่วมกับEdward G. Coffman Jr.ในปี 1972 ^[A72b]ให้อัลกอริทึมที่เหมาะสมที่สุดสำหรับการจัดตารางเวลาเครื่องจักรสองเครื่อง และอัลกอริทึมการประมาณค่า ที่รับประกัน สำหรับเครื่องจักรจำนวนมากขึ้น นอกจากนี้ยังถูกนำไปใช้ในการวาดกราฟแบบเลเยอร์ด้วย^{[ 31 ]}

ในบทความสำรวจเกี่ยวกับอัลกอริทึมการจัดตารางเวลาที่ตีพิมพ์ในปี 1979 เกรแฮมและผู้เขียนร่วมของเขาได้นำเสนอสัญกรณ์สามสัญลักษณ์สำหรับการจำแนกปัญหาการจัดตารางเวลาเชิงทฤษฎีตามระบบของเครื่องจักรที่จะใช้งาน คุณลักษณะของงานและทรัพยากร เช่น ข้อกำหนดสำหรับการซิงโครไนซ์หรือการไม่ขัดจังหวะ และมาตรวัดประสิทธิภาพที่จะต้องปรับให้เหมาะสม^[A79]การจำแนกประเภทนี้บางครั้งเรียกว่า "สัญกรณ์ของเกรแฮม" หรือ "สัญกรณ์ของเกรแฮม" ^{[ 32 ]}

การสแกนของ Grahamเป็นอัลกอริทึมที่ใช้กันอย่างแพร่หลายและใช้งานได้จริงสำหรับการสร้างขอบนูนของชุดจุดสองมิติ โดยอาศัยการเรียงลำดับจุดแล้วแทรกเข้าไปในขอบนูนตามลำดับที่เรียง^{[ 33 ]} Graham ได้เผยแพร่อัลกอริทึมนี้ในปี 1972 ^[A72c]

ปัญหา รูปหลายเหลี่ยมเล็กที่ใหญ่ที่สุดถามถึงรูปหลายเหลี่ยมที่มีพื้นที่มากที่สุดสำหรับเส้นผ่านศูนย์กลางที่กำหนด ที่น่าประหลาดใจคือ ตามที่เกรแฮมสังเกต คำตอบไม่ได้เป็นรูปหลายเหลี่ยมปกติ เสมอ ไป^[A75a]ข้อสันนิษฐานของเกรแฮมในปี 1975 เกี่ยวกับรูปร่างของรูปหลายเหลี่ยมเหล่านี้ได้รับการพิสูจน์ในที่สุดในปี 2007 ^{[ 34 ]}

ในเอกสารตีพิมพ์อีกฉบับในปี 1975 Graham และ Erdős สังเกตว่าสำหรับการจัดเรียงสี่เหลี่ยมจัตุรัสหน่วยลงในสี่เหลี่ยมจัตุรัสขนาดใหญ่ที่มีความยาวด้านไม่เป็นจำนวนเต็ม สามารถใช้สี่เหลี่ยมจัตุรัสเอียงเพื่อเว้นพื้นที่ว่างไว้ซึ่งมีค่าต่ำกว่าเชิงเส้นตามความยาวด้านของสี่เหลี่ยมจัตุรัสขนาดใหญ่ ซึ่งแตกต่างจากการจัดเรียงสี่เหลี่ยมจัตุรัสที่วางตัวตามแนวแกนอย่างชัดเจน^[A75b] Klaus RothและBob Vaughanพิสูจน์ว่าบางครั้งอาจจำเป็นต้องมีพื้นที่ว่างอย่างน้อยที่สุดที่เป็นสัดส่วนกับรากที่สองของความยาวด้าน การพิสูจน์ขอบเขตที่แน่นหนาของพื้นที่ว่างยังคงเป็นปัญหาที่ยังไม่ได้รับการแก้ไข^{[ 35 ]}

ในสถิติแบบไม่ใช้พารามิเตอร์บทความปี 1977 โดยPersi Diaconisและ Graham ได้ศึกษาคุณสมบัติทางสถิติของกฎฟุตรูลของสเปียร์แมน ซึ่ง เป็นการวัดความสัมพันธ์เชิงลำดับที่เปรียบเทียบการเรียงสับเปลี่ยน สองแบบ โดยการรวมระยะห่างระหว่างตำแหน่งของรายการในสองการเรียงสับเปลี่ยนเข้าด้วยกัน^[A77] พวกเขาเปรียบเทียบการวัดนี้กับวิธีการหาความสัมพันธ์เชิงลำดับอื่นๆ ส่งผลให้เกิด "อสมการ Diaconis–Graham"

${\displaystyle I+E\leq D\leq 2I}$

โดยที่คือกฎของ Spearman คือจำนวนการผกผันระหว่างการเรียงสับเปลี่ยนสองแบบ (เวอร์ชันที่ไม่เป็นมาตรฐานของสัมประสิทธิ์สหสัมพันธ์ลำดับ Kendall ) และคือจำนวนขั้นต่ำของการสลับสององค์ประกอบที่จำเป็นเพื่อให้ได้การเรียงสับเปลี่ยนหนึ่งจากอีกแบบหนึ่ง^{[ 36 ]}${\displaystyle D}$${\displaystyle I}$${\displaystyle E}$

กระบวนการสุ่ม Chung –Diaconis–Grahamเป็นการเดินสุ่มบนจำนวนเต็มมอดูลจำนวนคี่ซึ่งในแต่ละขั้นตอนจะเพิ่มจำนวนก่อนหน้าเป็นสองเท่า แล้วสุ่มเพิ่มศูนย์หรือ(มอดูล) ในบทความปี 1987 Chung, Diaconis และ Graham ได้ศึกษาเวลาการผสมของกระบวนการนี้ โดยได้รับแรงบันดาลใจจากการศึกษาตัวสร้างเลขสุ่มเทียม [ ^{A87] [ 37 ]}${\displaystyle p}$${\displaystyle 1}$${\displaystyle -1}$${\displaystyle p}$

เกรแฮมเริ่มเป็นนักเล่นกลที่เก่งกาจตั้งแต่อายุ 15 ปี และฝึกฝนการเล่นกลลูกบอลได้ถึงหกลูก^{[ 4 ]} (แม้ว่าภาพถ่ายที่ตีพิมพ์จะแสดงให้เห็นว่าเขาเล่นกลลูกบอลสิบสองลูก^{[ 5 ]}แต่มันเป็นภาพที่ถูกดัดแปลง^{[ 3 ]} ) เขาได้สอนสตีฟ มิลส์ผู้ชนะเลิศการแข่งขันของสมาคมนักเล่นกลนานาชาติหลายสมัย ให้เล่นกล และงานของเขากับมิลส์ช่วยเป็นแรงบันดาลใจให้มิลส์พัฒนา รูปแบบการเล่นกล Mills' Messนอกจากนี้ เกรแฮมยังได้มีส่วนสำคัญต่อทฤษฎีการเล่นกล รวมถึงการตีพิมพ์ผลงานหลายชิ้นในsiteswapsในปี 1972 เขาได้รับเลือกเป็นประธานของ สมาคมนัก เล่นกลนานาชาติ^{[ 4 ]}

ในปี 2003 เกรแฮมได้รับรางวัล Leroy P. Steele Prize for Lifetime Achievement ประจำปีของAmerican Mathematical Societyรางวัลนี้ยกย่องผลงานของเขาในด้านคณิตศาสตร์เชิงดิสครีตการเผยแพร่คณิตศาสตร์ผ่านการบรรยายและการเขียน การเป็นผู้นำที่Bell Labsและการดำรงตำแหน่งประธานของสมาคม^{[ 2 ]}เขาเป็นหนึ่งในห้าผู้ได้รับรางวัล George Pólya Prize ครั้งแรก ของSociety for Industrial and Applied Mathematicsโดยได้รับรางวัลร่วมกับนักทฤษฎี Ramsey คนอื่นๆ ได้แก่ Klaus Leeb, Bruce Rothschild , Alfred Halesและ Robert I. Jewett ^{[ 38 ]}เขายังเป็นหนึ่งในสองผู้ได้รับรางวัลEuler Medal ครั้งแรก ของInstitute of Combinatorics and its Applicationsโดยอีกคนหนึ่งคือClaude Berge ^{[ 39 ]}

เกรแฮมได้รับเลือกเป็นสมาชิกสถาบันวิทยาศาสตร์แห่งชาติในปี 1985 ^{[ 40 ]}ในปี 1999 เขาได้รับการแต่งตั้งเป็นสมาชิก ACM "เนื่องจากมีส่วนสำคัญในการวิเคราะห์อัลกอริทึม โดยเฉพาะอย่างยิ่งการวิเคราะห์กรณีที่เลวร้ายที่สุดของฮิวริสติก ทฤษฎีการจัดตารางเวลา และเรขาคณิตเชิงคำนวณ" ^{[ 41 ]}เขากลายเป็นสมาชิกของสมาคมคณิตศาสตร์อุตสาหกรรมและประยุกต์ในปี 2009 รางวัลสมาชิกยกย่อง "การมีส่วนร่วมของเขาในคณิตศาสตร์เชิงดิสครีตและการประยุกต์ใช้" ^{[ 42 ]}ในปี 2012 เขากลายเป็นสมาชิกของสมาคมคณิตศาสตร์อเมริกัน^{[ 43 ]}

เกรแฮมได้รับเชิญให้เป็นวิทยากรในการประชุมนานาชาติของนักคณิตศาสตร์ ในปี 1982 (จัดขึ้นในปี 1983 ที่วอร์ซอ) ^{[ 13 ]}โดยบรรยายในหัวข้อ "การพัฒนาล่าสุดในทฤษฎีแรมซีย์" ^[A84]เขาได้รับ รางวัล Josiah Willard Gibbs Lecturer สองครั้ง ในปี 2001 และ 2015 ^{[ 13 ]} สมาคมคณิตศาสตร์แห่งอเมริกาได้มอบรางวัล Carl Allendoerfer Prize ให้แก่เขา สำหรับบทความเรื่อง "Steiner Trees on a Checkerboard" ร่วมกับ Chung และMartin GardnerในMathematics Magazine (1989) ^{[A89b] [ 44 ]}และรางวัล Lester R. Ford Awardสำหรับบทความเรื่อง "A whirlwind tour of computational geometry" ร่วมกับFrances YaoในAmerican Mathematical Monthly (1990) ^{[A90] [ 45 ]}หนังสือของเขาเรื่อง Magical Mathematicsร่วมกับPersi Diaconis ^[B6]ได้รับ รางวัล Euler Book Prize ^{[ 46 ]}

เอกสารประกอบการ ประชุม Integers 2005ได้รับการตีพิมพ์เป็นหนังสือที่ระลึก เนื่อง ในโอกาสวันเกิดครบรอบ 70 ปีของ Ron Graham [ ^{47 ] หนังสือ}ที่ระลึกอีกเล่มหนึ่งซึ่งจัดทำขึ้นจากการประชุมที่จัดขึ้นในปี 2015 เพื่อเป็นเกียรติแก่วันเกิดครบรอบ 80 ปีของ Graham ได้รับการตีพิมพ์ในปี 2018 ในชื่อหนังสือConnections in discrete mathematics: a celebration of the work of Ron Graham ^{[ 48 ]}

• ประวัติงานวิจัยของ Graham จากคณะ UCSD
• เอกสารของรอน เกรแฮม  – คลังเอกสารที่ครอบคลุมทุกด้านของงานเขียนของรอน เกรแฮม
• เกี่ยวกับรอน เกรแฮม  – หน้าเว็บที่สรุปแง่มุมบางประการของชีวิตและคณิตศาสตร์ของเกรแฮม – ส่วนหนึ่งของเว็บไซต์ของฟาน ชุง
• "มูลนิธิไซมอนส์: โรนัลด์ เกรแฮม (1935–2020)"มูลนิธิไซมอนส์ 11 มกราคม 2016- บทสัมภาษณ์ทางวิดีโอฉบับเต็ม
• "นักคณิตศาสตร์สามท่านที่เราสูญเสียไปในปี 2020: จอห์น คอนเวย์, โรนัลด์ เกรแฮม และฟรีแมน ไดสัน ต่างสำรวจโลกด้วยความคิดของพวกเขา"ร็อคมอร์, แดน. (31 ธันวาคม 2020) เดอะนิวยอร์กเกอร์
• Buhler, Joe; Butler, Steve; Spencer, Joel (ธันวาคม 2021). "Ronald Lewis Graham (1935–2020)" (PDF) . Notices of the American Mathematical Society . 68 (11): 1931– 1950. doi : 10.1090/noti2382 .
• ผลงานตีพิมพ์ของ Ronald Grahamที่ได้รับการจัดทำดัชนีโดยGoogle Scholar