| EPSRC Reference: |
EP/K033379/1 |
| Title: |
Robustness of properties of random and pseudo-random graphs |
| Principal Investigator: |
Hefetz, Dr D |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
School of Mathematics |
| Organisation: |
University of Birmingham |
| Scheme: |
First Grant - Revised 2009 |
| Starts: |
01 October 2013 |
Ends: |
30 September 2015 |
Value (£): |
96,865
|
| EPSRC Research Topic Classifications: |
|
| EPSRC Industrial Sector Classifications: |
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
Combinatorics is a fundamental area of Mathematics which has found important applications in many of its branches, such as Algebra, Ergodic Theory, Geometry, Number Theory, Probability Theory, Topology and others. It is also highly influential in many other scientific disciplines as well as in the solution of real life problems. The field has experienced explosive growth in recent decades, mainly due to the development of computers and the central role of Combinatorics in Theoretical Computer Science.
The theory of random graphs is an important area of Combinatorics which lies at its interface with Probability Theory. It has numerous applications in Theoretical Computer Science and in the physical, biological and social sciences and its study is key to the development of all of these areas. For example, random graphs are used to model massive real life networks (such as the Internet) and phenomena (such as the spread of an epidemic).
The proposed project explores properties which are satisfied by sparse random graphs in some robust fashion. For example, instead of just requiring a network of computers (modelled by an appropriate graph) to be connected (so that each computer will be able to communicate with all others) we will require that the network remains connected even if some connections become faulty due to malicious attack. In addition to the direct contribution to the development of the theory of random graphs, this line of research continues an exciting new trend in Extremal Combinatorics of transferring fundamental results from the setting of dense graphs to the setting of sparse graphs. It can also potentially lead to general embedding results for sparse pseudo-random graphs. The dense case is well understood via the celebrated Regularity and Blow-up Lemmas, but relatively little is known for the sparse case. Finally, the project also involves the theory of Positional Games and aims to prove game-theoretic analogues of classical results of Extremal Combinatorics.
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
|
| Further Information: |
|
| Organisation Website: |
http://www.bham.ac.uk |