Award Abstract # 1201380
Extremal Combinatorics

NSF Org: DMS
Division Of Mathematical Sciences
Recipient: CARNEGIE MELLON UNIVERSITY
Initial Amendment Date: April 4, 2012
Latest Amendment Date: July 1, 2014
Award Number: 1201380
Award Instrument: Continuing Grant
Program Manager: Tomek Bartoszynski
tbartosz@nsf.gov
 (703)292-4885
DMS
 Division Of Mathematical Sciences
MPS
 Directorate for Mathematical and Physical Sciences
Start Date: July 1, 2012
End Date: December 31, 2015 (Estimated)
Total Intended Award Amount: $299,991.00
Total Awarded Amount to Date: $299,991.00
Funds Obligated to Date: FY 2012 = $97,619.00
FY 2013 = $100,267.00

FY 2014 = $102,105.00
History of Investigator:
  • Po-Shen Loh (Principal Investigator)
    ploh@cmu.edu
Recipient Sponsored Research Office: Carnegie-Mellon University
5000 FORBES AVE
PITTSBURGH
PA  US  15213-3815
(412)268-8746
Sponsor Congressional District: 12
Primary Place of Performance: Carnegie-Mellon University
5000 Forbes Ave
Pittsburgh
PA  US  15213-3815
Primary Place of Performance
Congressional District:
12
Unique Entity Identifier (UEI): U3NKNFLNQ613
Parent UEI: U3NKNFLNQ613
NSF Program(s): Combinatorics
Primary Program Source: 01001213DB NSF RESEARCH & RELATED ACTIVIT
01001314DB NSF RESEARCH & RELATED ACTIVIT

01001415DB NSF RESEARCH & RELATED ACTIVIT
Program Reference Code(s):
Program Element Code(s): 797000
Award Agency Code: 4900
Fund Agency Code: 4900
Assistance Listing Number(s): 47.049

ABSTRACT

This project focuses on topics in Extremal Combinatorics, which investigate the relationships between useful parameters of discrete systems, and characterizes their extreme values over various families of those systems. Such problems often have applications in Computer Science and other areas of Mathematics, but are also elegant and interesting in their own right. The goal of this project is to further develop the toolbox of available approaches for attacking Combinatorial problems. This goal will be achieved by studying certain families of problems which can be organized according to the methods used in their solutions. First, we examine applications of analytical (continuous) arguments to discrete problems. Second, we study extremal problems related to set systems. Finally, we explore the application of probabilistic methods to purely deterministic problems.

The field of combinatorics encompasses the rigorous mathematical study of discrete structures and processes, such as sets, networks, and even algorithms. In the past, combinatorial problems were often solved by pure ingenuity. Today, however, a variety of powerful methods have emerged, which draw elements from many other branches of the mathematical sciences. At the same time, the rapid development of Computer Science has substantially increased the demand for foundational results on discrete systems--these can provide the theoretical basis for future work. The overarching objective of this project is to use a problem-driven philosophy to inspire innovations in the development of new techniques in Combinatorics. Unifying the problems in this study is a theme of simple, elegant statements that inspire approaches which arise from across the mathematical spectrum. Consequently, these problems also serve well as a platform for bringing young people into research.

PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH

Note:  When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

A. Dudek, A. Frieze, P. Loh, and S. Speiss "Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs" The Electronic Journal of Combinatorics , v.19 , 2012 , p.P44
C. Lee, P. Loh, and B. Sudakov "Judicious partitions of directed graphs" Random Structures and Algorithms , 2016
D. Bal, A. Frieze, M. Krivelevich, and P. Loh "Packing tree factors in random and pseudo-random graphs" The Electronic Journal of Combinatorics , v.21 , 2014 , p.P2.8
J. Fox, P. Loh, and Y. Zhao "The critical window for the classical Ramsey-Turan problem" Combinatorica , 2015 , p.accepted
J. Iglesias, N. Ince, and P. Loh "Computing with voting trees" SIAM Journal on Discrete Mathematics , v.28 , 2014 , p.673
M. Lavrov and P. Loh "Hamiltonian increasing paths in random edge orderings" Random Structures and Algorithms , 2016
P. Loh and J. Ma "Diameter critical graphs" Journal of Combinatorial Theory Series B , 2016
R. Graham, L. Hamilton, A. Levavi, and P. Loh "Anarchy is free in network creation" Transactions on Algorithms , 2016
W. Gan, P. Loh, and B. Sudakov "Maximizing the number of independent sets of a fixed size" Combinatorics, Probability and Computing , 2015

PROJECT OUTCOMES REPORT

Disclaimer

This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.

Combinatorics, which concerns the study of discrete structures such as sets and networks, is as ancient as humanity's ability to count.  Yet although in the beginning, combinatorial problems were solved by pure ingenuity, today that alone is not enough.  A rich variety of powerful methods have been developed, often drawing inspiration from other fields such as probability, analysis, algorithms, and even algebra and topology.  This award further developed the toolbox of available approaches, through investigating central problems in extremal combinatorics.  Simultaneously, it integrated these research problems and themes into educational and outreach activities that extended from the graduate to the K-12 level, and from coast to coast.

The work produced a total of 9 published papers, one accepted paper, and one submitted paper, all to leading peer-reviewed mathematical journals.  Several answered decades-old conjectures in the field.  In addition to producing new research results, the PI mentored numerous students at both graduate and undergraduate levels, as well as two post-docs, assisting all at various stages of their professional development.  The PI widely disseminated the results by giving 36 research talks throughout the world, from major universities such as Stanford and MIT, to regional centers such as the University of Memphis, to far-reaching places such as international conferences in Beijing and the United Kingdom.

The PI was also heavily involved in outreach activities at the K-12 level, from coaching his local middle school's math team to serving as the national lead coach of the USA Math Olympiad team.  He makes it a point to combine his frequent research conference/collaboration travel with visits to local high schools, where he holds events to popularize mathematics.  All of these activities are helping to develop the future pipeline for STEM talent.

In addition, as the director of the national Math Olympiad Summer Program, the PI has transformed what was previously a pure high school math camp into a vertically integrated long-term enrichment program.  He managed its relocation to Carnegie Mellon University in 2015, where it plugged in to the full university's infrastructure, broadening the possibilities for enrichment.

The PI has worked to raise the level of analytical aptitude in the United States, through initiatives which often unite research and K-12 outreach, with the ultimate objective of leaving an impact on the general educational level in the country.

Last Modified: 05/30/2016
Modified by: Po-Shen Loh

Please report errors in award information by writing to: awardsearch@nsf.gov.

Print this page

Back to Top of page