| NSF Org: |
DMS Division Of Mathematical Sciences |
| Recipient: |
|
| Initial Amendment Date: | July 3, 2016 |
| Latest Amendment Date: | July 3, 2016 |
| Award Number: | 1600811 |
| Award Instrument: | Standard 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, 2016 |
| End Date: | June 30, 2020 (Estimated) |
| Total Intended Award Amount: | $180,000.00 |
| Total Awarded Amount to Date: | $180,000.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
1600 HAMPTON ST COLUMBIA SC US 29208-3403 (803)777-7093 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
1523 Greene Street Columbia SC US 29208-0001 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Combinatorics |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.049 |
ABSTRACT
This research project investigates basic combinatorial questions about discrete structures and explores applications of discrete mathematics in computer science, biology, and engineering. The investigators continue their work on extremal graph, set, and hypergraph theory and forbidden configurations. They investigate connections between graph theory and geometry, on the one hand studying Ricci curvature on graphs, on the other hand studying crossing numbers of graphs and related incidence problems. The project will study graph and tree indices originating in chemical graph theory and will apply combinatorial and probabilistic techniques to phylogenetics and to the theory of complex networks. Results of the project will contribute to the better understanding of key phenomena in network science, of discretization of geometric space, of phylogenetics, and of other fields. The investigators will continue the training of Ph.D. students through involvement in the research, introducing them to interdisciplinary and international research collaboration.
The project will contribute to the understanding of "optimal" extreme structures and "typical" random structures in discrete mathematics. This area is referred to broadly as extremal combinatorics, and some of the main open questions in the area will be studied, including various instances of the Turan problem for graphs, hypergraphs and posets, problems in combinatorial geometry, in the vein of the Erdos unit distance problem and crossing and incidence problems, and combinatorial questions on trees such as the Maximum Agreement Subtree problem as well as topics related to chemistry. This project will build upon sophisticated methods that have been developed to attack these problems, such as the approach via crossing numbers and incidences, the Guth-Katz low degree polynomial method, and the generalization of the notion of Ricci Curvature from differential geometry to graphs, which allows, to some extent, functional analytic tools to be brought to bear.
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.
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.
The project focused on properties of extremal structures and random structures in combinatorics. In particular, the work focused on Turan numbers of graphs and hypergraphs, Ricci curvature of graphs, crossing number of graphs and tanglegrams, and basic problems of network science. Several of the results are relevant not just for mathematics, but also for the sciences.
Tanglegrams are used to describe the co-evolution of hosts and parasites, and tanglegram crossing numbers are relevant for the number of jumps of parasites from one host to another. We gave a characterization of planarity of tanglegrams, determined the magnitude of the crossing number of a random tanglegram, and determined asymptotically the maximum possible crossing number of a tanglegram of given size.
In network science, when trying to make sense statistically from observed networks, the number of zeros in the joint degree vector are relevant as they correspond to quantities not estimable by maximum likelihood estimation in the exponential random graph model. We made partial results on the maximum possible number of nonzero entries in a joint degree vector. The following problem has a similar motivation from network statistics: given a graph, whose vertex set is partitioned into constant number of classes, is there a subgraph, which exhibits prescribed degrees at the vertices, and prescribed number of edges between the vertex classes? We solved this problem with a randomized algorithm.
In Ramsey theory, we improved the upper bound on size-Ramsey number of tigh hypergraph paths. We settled Jahanbekam and West's conjecture on the anti-Ramsey number of edge-disjoint rainbow spanning trees. In spectral hypergraph theory, we settled Nikiforov's conjecture and proved the principal case of Frankl and Furedi's conjecture on Lagrangian.
In the grant period the PIs graduated 6 Ph.D. sudents, ran research seminars at their departments for graduate students, and mentored and collaborated with a number of Ph.D. students and junior researchers from other institutions.
Last Modified: 01/01/2021
Modified by: Laszlo Szekely
Please report errors in award information by writing to: awardsearch@nsf.gov.
