Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

McGill University

$18,000.00

Graphs, games and quasirandomness

EF 2009-10

Résumé
My proposed research lies in the fields of combinatorics and combinatorial optimization. The problems I aim to study fall into four general categories; (1) positional games, (2) combinatorics of linear programming, especially the model of unique sink orientation of hypercubes, (3) theory of sparse quasirandom graphs, and (4) extremal combinatorial problems of various kinds. I study these questions from different points of view, considering both combinatorial and algorithmic aspects. Positional games are two player games of perfect information, that are strongly related to the concepts of randomization and derandomization in computer science. We aim to find and describe winning strategies for important classes of games. Our investigation is often guided by probabilistic intuition and particular strategies frequently provide algorithmization of related algorithms. Linear programming (LP) is probably the single most frequently solved computational task in computers today. It involves maximizing or minimizing a linear function, such that the solution satisfies a set of given linear constraints. There exists a variety of algorithms that solve LP very fast in practice. Despite their practical success there are interesting theoretical open questions mostly surrounding the geometry and combinatorics of linear programming. I plan to study some of these questions; an advance on them could have practical consequences down the road. A graph is called quasirandom if some of its properties resemble those of truly random graphs. I intend to construct new quasirandom graphs with useful properties. Explicit constructions of quasirandom graphs are potentially helpful in computer science where they can save (expensive) random bits, or in combinatorics where their imperfect randomness might be crucial in providing solutions to extremal problems, studied under category (4).
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
371890-2009
Name nom
Szabo, Tibor
Department département
Mathematics and Statistics
Organization id
61
Institution établissement
McGill University
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2009
Competition year année de concours
2009
Award amount
18000
Program id
RGPIN
Program nane en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
337
Committee name en
Pure & Applied Maths - B
Committee name fr
Maths pures et appliquées - B
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
1
Nb partie
5
Application title
Graphs, games and quasirandomness
Keyword
NA
Application summary
My proposed research lies in the fields of combinatorics and combinatorial optimization. The problems I aim to study fall into four general categories; (1) positional games, (2) combinatorics of linear programming, especially the model of unique sink orientation of hypercubes, (3) theory of sparse quasirandom graphs, and (4) extremal combinatorial problems of various kinds. I study these questions from different points of view, considering both combinatorial and algorithmic aspects. Positional games are two player games of perfect information, that are strongly related to the concepts of randomization and derandomization in computer science. We aim to find and describe winning strategies for important classes of games. Our investigation is often guided by probabilistic intuition and particular strategies frequently provide algorithmization of related algorithms. Linear programming (LP) is probably the single most frequently solved computational task in computers today. It involves maximizing or minimizing a linear function, such that the solution satisfies a set of given linear constraints. There exists a variety of algorithms that solve LP very fast in practice. Despite their practical success there are interesting theoretical open questions mostly surrounding the geometry and combinatorics of linear programming. I plan to study some of these questions; an advance on them could have practical consequences down the road. A graph is called quasirandom if some of its properties resemble those of truly random graphs. I intend to construct new quasirandom graphs with useful properties. Explicit constructions of quasirandom graphs are potentially helpful in computer science where they can save (expensive) random bits, or in combinatorics where their imperfect randomness might be crucial in providing solutions to extremal problems, studied under category (4).