Award Abstract # 1352121
CAREER: Extremal Combinatorics: Methods, Problems, and Challenges

NSF Org: DMS
Division Of Mathematical Sciences
Recipient: MASSACHUSETTS INSTITUTE OF TECHNOLOGY
Initial Amendment Date: March 11, 2014
Latest Amendment Date: May 6, 2015
Award Number: 1352121
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: April 1, 2014
End Date: October 31, 2015 (Estimated)
Total Intended Award Amount: $400,000.00
Total Awarded Amount to Date: $160,000.00
Funds Obligated to Date: FY 2014 = $50,610.00
FY 2015 = $0.00
History of Investigator:
  • Jacob Fox (Principal Investigator)
    jacobfox@stanford.edu
Recipient Sponsored Research Office: Massachusetts Institute of Technology
77 MASSACHUSETTS AVE
CAMBRIDGE
MA  US  02139-4301
(617)253-1000
Sponsor Congressional District: 07
Primary Place of Performance: Massachusetts Institute of Technology
77 Massachusetts Avenue
Cambridge
MA  US  02139-4307
Primary Place of Performance
Congressional District:
07
Unique Entity Identifier (UEI): E2NYLCDML6V1
Parent UEI: E2NYLCDML6V1
NSF Program(s): Combinatorics,
Division Co-Funding: CAREER
Primary Program Source: 01001415DB NSF RESEARCH & RELATED ACTIVIT
01001516DB NSF RESEARCH & RELATED ACTIVIT

01001617DB NSF RESEARCH & RELATED ACTIVIT

01001718DB NSF RESEARCH & RELATED ACTIVIT

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

ABSTRACT

This research project considers a variety of problems related to Szemerédi's regularity method and Ramsey theory. In tackling these problems, the PI will use a range of combinatorial methods that have recently led to substantial progress on related problems. Examples include probabilistic methods, density increment arguments, transference arguments, analytic tools, and embedding techniques. The first area in this project concerns Szemerédi's regularity method. Within this area, one of the main goals of the project is to obtain new bounds on the triangle removal lemma and its various extensions and variants. The triangle removal lemma states that any graph with a subcubic number of triangles can be made triangle-free by removing a subquadratic number of edges. Another major goal of the project is to further push the regularity method to sparse graphs and other combinatorial structures, and to obtain new applications. Specific problems include optimizing the pseudorandomness conditions needed to obtain sparse counting lemmas, proving analogous sparse regularity results in other combinatorial structures such as cubes, and providing new applications in number theory and discrete geometry such as extensions of the Green-Tao theorem on long arithmetic progressions in the primes. The second area in this project is estimating Ramsey numbers. The PI will work on proving new bounds for classical (complete) graph and hypergraph Ramsey numbers, and to prove linear bounds for Ramsey numbers of sparse graphs.

This project studies fundamental problems in combinatorics related to the structure of large networks. Examples of large networks include the Internet, Facebook, the brain, imperfect crystals, and designed chips. The structure of these networks can be critical in understanding how the networks function. Previous work has shown that the subjects under study in this project have a wide range of applications. Furthermore, this work has led to the development of powerful methods that have been used in many branches of mathematics and computer science. For example, previous progress on estimating Ramsey numbers led to the development of probabilistic techniques that have had a tremendous influence on computer science, such as in the design of randomized algorithms. It is expected that further work on these problems will lead to new methods and applications.

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.

D. Conlon, J. Fox, and B. Sudakov "Cycle Packing" Random Structures and Algorithms , v.45 , 2014 , p.608
D. Conlon, J. Fox, and B. Sudakov "Short proofs of some extremal results" Combinatorics, Probability, and Computing , v.23 , 2014 , p.8
D. Conlon, J. Fox, and Y. Zhao "Extremal results in sparse pseudorandom graphs" Advances in Mathematics , 2014 , p.206
D. Conlon, J. Fox, and Y. Zhao "The Green-Tao theorem: an exposition" EMS Surveys in Mathematical Sciences , v.1 , 2014 , p.257
D. Conlon, J. Fox, C. Lee, and B. Sudakov "The Erd?s-Gyárfás problem on generalized Ramsey numbers" Proceedings of the London Mathematical Society , v.110 , 2015 , p.1
D. Conlon, J. Fox, J. Pach, B. Sudakov, and A. Suk "Ramsey-type results for semi-algebraic relations." Transactions of the American Mathematical Society , v.366 , 2014 , p.5043
E. Ackerman, J. Fox, J. Pach, and A. Suk "On grids in topological graphs" Computational Geometry , v.47 , 2014 , p.710
J. Fox, A. Grinshpun, A. Liebenau, Y. Person, and T. Szabo "What is Ramsey-equivalent to a clique?" Journal of Combinatorial Theory Series B , v.109 , 2014 , p.120
J. Fox and J. Pach "Applications of a new separator theorem for string graphs" Combinatorics, Probability, and Computing , v.23 , 2014 , p.66
M. DeVos, Z. Dvorak, J. Fox, J. McDonald, B. Mohar, and D. Scheide "Minimum degree condition forcing complete graph immersion" Combinatorica , v.34 , 2014 , p.279

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

Print this page

Back to Top of page