This dissertation consists of several combinatorial problems on the integers. These problems fit inside the areas of extremal combinatorics and enumerative combinatorics.
We first study monochromatic solutions to equations when integers are colored with finitely many colors in Chapter 2. By looking at subsets of {1, 2, . . . , n} whose least common multiple is small, we improved a result of Brown and Rödl on the smallest integer n such that every 2-coloring of {1, 2, . . . , n} has a monochromatic solution to equations with unit fractions. Using a recent result of Boza, Marín, Revuelta, and Sanz, this technique also allows us to show a polynomial upper bound for the same problem, but with three colors.
We then study Maker-Breaker positional games for equations with fractional powers in Chapter 3. In these games, Maker and Breaker take turns to select a previously unclaimed number in {1, 2, . . . , n}, Maker wins if they can form a solution to a given equation, and Breaker wins if they can stop Maker. Using combinatorial arguments and results from number theory and arithmetic Ramsey theory, we found exact expressions or strong bounds for the smallest n such that Maker has a winning strategy.
Finally, we study permutations of integers in Chapters 4 to 6. In Chapter 4, we provide an alternative proof of a result by Miner and Pak which says that 123- and 132-avoiding permutations with a fixed leading term are enumerated by the ballot numbers. We then study the number of pattern-avoiding permutations with a fixed prefix of length t ≥ 1, generalizing the t = 1 case. We find exact expressions for single and pairs of patterns of length three as well as the pair 3412 and 3421. These expressions depend on t, the extrema, and the order statistics. In Chapter 5, we define rotations of permutations and study permutations such that they and their rotations avoid certain patterns. We obtain many enumerative results for patterns of length three and several of them are related to existing results on permutations avoiding other patterns. In Chapter 6, we look at subsequences with certain arithemtic properties that exist in all permutations of a given length. For example, we prove that for all positive integers k ≥ 3 and sufficiently large n, every permutation of {1, 2, . . . , n} has a subsequence (a1, a2, . . . , ak) such that either ∑ki=1 ai = 2a1 or ∑ki=1 ai = 2ak.
","abstract_html":"<p>This dissertation consists of several combinatorial problems on the integers. These problems fit inside the areas of extremal combinatorics and enumerative combinatorics.</p> <p>We first study monochromatic solutions to equations when integers are colored with finitely many colors in Chapter 2. By looking at subsets of {1, 2, . . . , <em>n</em>} whose least common multiple is small, we improved a result of Brown and Rödl on the smallest integer <em>n</em> such that every 2-coloring of {1, 2, . . . , <em>n</em>} has a monochromatic solution to equations with unit fractions. Using a recent result of Boza, Marín, Revuelta, and Sanz, this technique also allows us to show a polynomial upper bound for the same problem, but with three colors.</p> <p>We then study Maker-Breaker positional games for equations with fractional powers in Chapter 3. In these games, Maker and Breaker take turns to select a previously unclaimed number in {1, 2, . . . , <em>n</em>}, Maker wins if they can form a solution to a given equation, and Breaker wins if they can stop Maker. Using combinatorial arguments and results from number theory and arithmetic Ramsey theory, we found exact expressions or strong bounds for the smallest n such that Maker has a winning strategy.</p> <p>Finally, we study permutations of integers in Chapters 4 to 6. In Chapter 4, we provide an alternative proof of a result by Miner and Pak which says that 123- and 132-avoiding permutations with a fixed leading term are enumerated by the ballot numbers. We then study the number of pattern-avoiding permutations with a fixed prefix of length <em>t</em> ≥ 1, generalizing the <em>t</em> = 1 case. We find exact expressions for single and pairs of patterns of length three as well as the pair 3412 and 3421. These expressions depend on <em>t</em>, the extrema, and the order statistics. In Chapter 5, we define rotations of permutations and study permutations such that they and their rotations avoid certain patterns. We obtain many enumerative results for patterns of length three and several of them are related to existing results on permutations avoiding other patterns. In Chapter 6, we look at subsequences with certain arithemtic properties that exist in all permutations of a given length. For example, we prove that for all positive integers <em>k</em> ≥ 3 and sufficiently large <em>n</em>, every permutation of {1, 2, . . . , <em>n</em>} has a subsequence (<em>a</em><sub>1</sub>, <em>a</em><sub>2</sub>, . . . , <em>a<sub>k</sub></em>) such that either ∑<sup><em>k</em></sup><sub><em>i</em>=1</sub> <em>a<sub>i</sub></em> = 2<em>a</em><sub>1</sub> or ∑<sup><em>k</em></sup><sub><em>i</em>=1</sub> <em>a<sub>i</sub></em> = 2<em>a<sub>k</sub></em>.</p>","abstract_has_math":false,"creators":["Gaiser, Collier"],"institution":null,"degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":null,"degree_department":null,"school":null,"contributors":["Paul Horn","Mei Yin","Chris GauthierDickey","Shashank Kanade","Petr Vojtechovsky"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024-06-15T07:00:00Z","date_published":"2024-06-15T07:00:00Z","updated_at":"2026-07-24T02:01:48Z","subjects":["Colorings","Enumeration","Extremal problems","Games","Integers","Permutations","Number Theory","Other Mathematics","Physical Sciences and Mathematics"],"languages":["English (eng)"],"rights":["Copyright is held by the author. User is responsible for all copyright compliance.
"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.du.edu/etd/2397","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Paul Horn","Mei Yin","Chris GauthierDickey","Shashank Kanade","Petr Vojtechovsky"]},{"key":"dc:creator","label":"Author","values":["Gaiser, Collier"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Colorings","Enumeration","Extremal problems","Games","Integers","Permutations","Number Theory","Other Mathematics","Physical Sciences and Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English (eng)"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright is held by the author. User is responsible for all copyright compliance.
"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.du.edu/etd/2397"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["This dissertation consists of several combinatorial problems on the integers. These problems fit inside the areas of extremal combinatorics and enumerative combinatorics.
We first study monochromatic solutions to equations when integers are colored with finitely many colors in Chapter 2. By looking at subsets of {1, 2, . . . , n} whose least common multiple is small, we improved a result of Brown and Rödl on the smallest integer n such that every 2-coloring of {1, 2, . . . , n} has a monochromatic solution to equations with unit fractions. Using a recent result of Boza, Marín, Revuelta, and Sanz, this technique also allows us to show a polynomial upper bound for the same problem, but with three colors.
We then study Maker-Breaker positional games for equations with fractional powers in Chapter 3. In these games, Maker and Breaker take turns to select a previously unclaimed number in {1, 2, . . . , n}, Maker wins if they can form a solution to a given equation, and Breaker wins if they can stop Maker. Using combinatorial arguments and results from number theory and arithmetic Ramsey theory, we found exact expressions or strong bounds for the smallest n such that Maker has a winning strategy.
Finally, we study permutations of integers in Chapters 4 to 6. In Chapter 4, we provide an alternative proof of a result by Miner and Pak which says that 123- and 132-avoiding permutations with a fixed leading term are enumerated by the ballot numbers. We then study the number of pattern-avoiding permutations with a fixed prefix of length t ≥ 1, generalizing the t = 1 case. We find exact expressions for single and pairs of patterns of length three as well as the pair 3412 and 3421. These expressions depend on t, the extrema, and the order statistics. In Chapter 5, we define rotations of permutations and study permutations such that they and their rotations avoid certain patterns. We obtain many enumerative results for patterns of length three and several of them are related to existing results on permutations avoiding other patterns. In Chapter 6, we look at subsequences with certain arithemtic properties that exist in all permutations of a given length. For example, we prove that for all positive integers k ≥ 3 and sufficiently large n, every permutation of {1, 2, . . . , n} has a subsequence (a1, a2, . . . , ak) such that either ∑ki=1 ai = 2a1 or ∑ki=1 ai = 2ak.
"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Combinatorial Problems on the Integers: Colorings, Games, and Permutations"]}]}],"canonical_facts":{"dc:contributor":["Paul Horn","Mei Yin","Chris GauthierDickey","Shashank Kanade","Petr Vojtechovsky"],"dc:creator":["Gaiser, Collier"],"dc:description.abstract":["This dissertation consists of several combinatorial problems on the integers. These problems fit inside the areas of extremal combinatorics and enumerative combinatorics.
We first study monochromatic solutions to equations when integers are colored with finitely many colors in Chapter 2. By looking at subsets of {1, 2, . . . , n} whose least common multiple is small, we improved a result of Brown and Rödl on the smallest integer n such that every 2-coloring of {1, 2, . . . , n} has a monochromatic solution to equations with unit fractions. Using a recent result of Boza, Marín, Revuelta, and Sanz, this technique also allows us to show a polynomial upper bound for the same problem, but with three colors.
We then study Maker-Breaker positional games for equations with fractional powers in Chapter 3. In these games, Maker and Breaker take turns to select a previously unclaimed number in {1, 2, . . . , n}, Maker wins if they can form a solution to a given equation, and Breaker wins if they can stop Maker. Using combinatorial arguments and results from number theory and arithmetic Ramsey theory, we found exact expressions or strong bounds for the smallest n such that Maker has a winning strategy.
Finally, we study permutations of integers in Chapters 4 to 6. In Chapter 4, we provide an alternative proof of a result by Miner and Pak which says that 123- and 132-avoiding permutations with a fixed leading term are enumerated by the ballot numbers. We then study the number of pattern-avoiding permutations with a fixed prefix of length t ≥ 1, generalizing the t = 1 case. We find exact expressions for single and pairs of patterns of length three as well as the pair 3412 and 3421. These expressions depend on t, the extrema, and the order statistics. In Chapter 5, we define rotations of permutations and study permutations such that they and their rotations avoid certain patterns. We obtain many enumerative results for patterns of length three and several of them are related to existing results on permutations avoiding other patterns. In Chapter 6, we look at subsequences with certain arithemtic properties that exist in all permutations of a given length. For example, we prove that for all positive integers k ≥ 3 and sufficiently large n, every permutation of {1, 2, . . . , n} has a subsequence (a1, a2, . . . , ak) such that either ∑ki=1 ai = 2a1 or ∑ki=1 ai = 2ak.
"],"dc:format":["application/pdf"],"dc:identifier":["https://digitalcommons.du.edu/etd/2397"],"dc:language":["English (eng)"],"dc:rights":["Copyright is held by the author. User is responsible for all copyright compliance.
"],"dc:subject":["Colorings","Enumeration","Extremal problems","Games","Integers","Permutations","Number Theory","Other Mathematics","Physical Sciences and Mathematics"],"dc:title":["Combinatorial Problems on the Integers: Colorings, Games, and Permutations"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."]},"updated_at":"2026-07-24T02:01:48Z"}