Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Victoria

$34,000.00

Fractional and Signed Relaxations of Balanced Combinatorial Structures

FY 2024-25

Summary
Combinatorics is a branch of mathematics concerned with (usually finite) discrete structures. An everyday example is a Sudoku puzzle. The central questions in combinatorics concern existence, counting, and symmetries present in the structure. This area has numerous applications, particularly to problems in information sciences such as communication, data management, and the design of experiments. Across the field of combinatorics, the notions of balance and symmetry are pervasive. Some standard examples exhibiting these features are graph factorizations, block designs, error-correcting codes, and Latin squares. Often, these structures are very rigid, and exist only in the presence of special conditions or additional properties. These can be inherently arithmetic or geometric in nature. As a very basic example of an arithmetic condition, partitioning a set of size n into blocks of size k requires that n be a multiple of k. This is because each element must get allocated to exactly one block. If instead you could cut up elements and allocate them fractionally, this divisibility constraint would disappear. On the other hand, some structural properties have a geometric or fractional character to them. For an example of this, a partition as above must have at least one of its blocks intersecting a prescribed m-subset in at least mk/n elements. This holds even in the fractional setting, since the key tool (that the maximum of some list of numbers is at least their average) holds for real numbers, not just for integers. Combinatorial problems which receive insight from relaxed settings are often very pleasing, because they are seen to connect with other areas of mathematics. These connections are often far deeper than our toy example with partitions. A unifying theme of this research proposal is the investigation of signed and fractional relaxations of combinatorial problems involving balance or symmetry. These correspond to arithmetic and geometric properties underlying the combinatorics, and are usually motivated by open problems or recent work on the topics in question. Some specific areas of focus will include permutation covers, density constraints in graph decompositions, and signed hypergraph designs. The proposed research on permutation covers is closely related to the question of deciding whether large permutations are random. The idea here is to count occurrences of various small patterns and use these values as a statistic to test for randomness.  The research on graph decompositions aims to push frontiers on some long-standing conjectures, and at the same time enjoys applications related to network efficiency, experimental design, and coding theory.  Signed designs have interesting algebraic and number-theoretic features. Importantly, these topics are highly concrete and amenable to experimentation.  They provide excellent opportunities for a diverse and inclusive group of students interested in STEM at various levels.
Program
Discovery Grants Program - Individual
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2024-03966
Name nom
Dukes, Peter
Department département
Mathematics and Statistics
Organization id
7
Institution établissement
University of Victoria
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2024
Award amount
34000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2900
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Pure mathematics
Research subject fr
Mathématiques pures
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Fractional and Signed Relaxations of Balanced Combinatorial Structures
Keywords
combinatorics; block designs; latin squares; error-correcting codes; quasirandomness; graph decompositions; hypergraphs; permutations; symmetric functions; matrix analysis
Application summary
Combinatorics is a branch of mathematics concerned with (usually finite) discrete structures. An everyday example is a Sudoku puzzle. The central questions in combinatorics concern existence, counting, and symmetries present in the structure. This area has numerous applications, particularly to problems in information sciences such as communication, data management, and the design of experiments. Across the field of combinatorics, the notions of balance and symmetry are pervasive. Some standard examples exhibiting these features are graph factorizations, block designs, error-correcting codes, and Latin squares. Often, these structures are very rigid, and exist only in the presence of special conditions or additional properties. These can be inherently arithmetic or geometric in nature. As a very basic example of an arithmetic condition, partitioning a set of size n into blocks of size k requires that n be a multiple of k. This is because each element must get allocated to exactly one block. If instead you could cut up elements and allocate them fractionally, this divisibility constraint would disappear. On the other hand, some structural properties have a geometric or fractional character to them. For an example of this, a partition as above must have at least one of its blocks intersecting a prescribed m-subset in at least mk/n elements. This holds even in the fractional setting, since the key tool (that the maximum of some list of numbers is at least their average) holds for real numbers, not just for integers. Combinatorial problems which receive insight from relaxed settings are often very pleasing, because they are seen to connect with other areas of mathematics. These connections are often far deeper than our toy example with partitions. A unifying theme of this research proposal is the investigation of signed and fractional relaxations of combinatorial problems involving balance or symmetry. These correspond to arithmetic and geometric properties underlying the combinatorics, and are usually motivated by open problems or recent work on the topics in question. Some specific areas of focus will include permutation covers, density constraints in graph decompositions, and signed hypergraph designs. The proposed research on permutation covers is closely related to the question of deciding whether large permutations are random. The idea here is to count occurrences of various small patterns and use these values as a statistic to test for randomness.  The research on graph decompositions aims to push frontiers on some long-standing conjectures, and at the same time enjoys applications related to network efficiency, experimental design, and coding theory.  Signed designs have interesting algebraic and number-theoretic features. Importantly, these topics are highly concrete and amenable to experimentation.  They provide excellent opportunities for a diverse and inclusive group of students interested in STEM at various levels.