QRGRAPH
Quasirandomness in Graphs and Hypergraphs
| Coordinatore | THE UNIVERSITY OF BIRMINGHAM
Spiacenti, non ci sono informazioni su questo coordinatore. Contattare Fabio per maggiori infomrazioni, grazie. |
| Nazionalità Coordinatore | United Kingdom [UK] |
| Totale costo | 742˙749 € |
| EC contributo | 742˙749 € |
| Programma | FP7-IDEAS-ERC
Specific programme: "Ideas" implementing the Seventh Framework Programme of the European Community for research, technological development and demonstration activities (2007 to 2013) |
| Code Call | ERC-2010-StG_20091028 |
| Funding Scheme | ERC-SG |
| Anno di inizio | 2010 |
| Periodo (anno-mese-giorno) | 2010-12-01 - 2015-11-30 |
Partecipanti
| # | ||||
|---|---|---|---|---|
| 1 |
THE UNIVERSITY OF BIRMINGHAM
Organization address
address: Edgbaston contact info |
UK (BIRMINGHAM) | hostInstitution | 742˙749.06 |
| 2 |
THE UNIVERSITY OF BIRMINGHAM
Organization address
address: Edgbaston contact info |
UK (BIRMINGHAM) | hostInstitution | 742˙749.06 |
Mappa
Word cloud
Esplora la "nuvola delle parole (Word Cloud) per avere un'idea di massima del progetto.
Obiettivo del progetto (Objective)
'A structure is called quasirandom if it has a number of properties that one would expect from a random structure with similar parameters. For instance, a graph is quasirandom if its edges are spread evenly over the vertices. This concept has been remarkably useful in many areas, including Number theory, Graph theory and the design of algorithms.
Quasirandomness is a field that is developing very rapidly, but there are many connections and properties that are still unexplored. In my proposal, I will concentrate on 4 important topics where I believe that quasirandomness is crucial to further progress: hypergraph matchings, decompositions of graphs, topological subgraphs as well as sparse graphs and hypergraphs.
As an illustration of a matching problem, consider a group of people and construct a graph by drawing an edge if they like each other - a perfect matching splits the people into teams of 2 which can work together. How and when this can be achieved for teams of 2 is well understood, but not for teams of 3 or more people. This can be formulated as a hypergraph matching problem. I believe that quasirandom decompositions can be used to give quite general sufficient conditions which guarantee a perfect hypergraph matching.
A better understanding of quasirandomness of sparse hypergraphs would have applications e.g. to checking whether a Boolean formula is satisfiable. This is one of the fundamental problems in Theoretical Computer Science.'