University of Waterloo

researchers with a paper here

Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.

collaborating institutions

Showing math.COShow all

326 papers · 1 filter

math.CO2025

North-East Lattice Paths Avoiding $k$ Collinear Points via Satisfiability

Aaron Barnoff, Curtis Bright

We investigate the Gerver-Ramsey collinearity problem of determining the maximum number of points in a north-east lattice path without $k$ collinear points. Using a satisfiability…

math.CO2025

Orthogonal Latin Squares of Order Ten with Two Relations: A SAT Investigation

Curtis Bright, Amadou Keita, Brett Stevens

A $k$ -net( $n$ ) is a combinatorial design equivalent to $k - 2$ mutually orthogonal Latin squares of order $n$ . A relation in a net is a linear dependency over $F_{2}$ in the i…

math.CO2025

Suns in triangle-free graphs of large chromatic number

Sepehr Hajebi, Sophie Spirkl

For an integer $t \geq 4$ , a $t$ -sun is a graph obtained from a $t$ -vertex cycle $C$ by adding a degree-one neighbor for each vertex of $C$ . Trotignon asked whether every triangle-f…

math.CO2025

Myrvold's Results on Orthogonal Triples of $10 \times 10$ Latin Squares: A SAT Investigation

Curtis Bright, Amadou Keita, Brett Stevens

Ever since E. T. Parker constructed an orthogonal pair of $10 \times 10$ Latin squares in 1959, an orthogonal triple of $10 \times 10$ Latin squares has been one of the most sought-aft…

math.CO2025★ 1 cited

Runs in Paperfolding Sequences

Jeffrey Shallit

The paperfolding sequences form an uncountable class of infinite sequences over the alphabet ${- 1, 1}$ that describe the sequence of folds arising from iterated folding of a pi…

math.CO2024★ 1 cited

Induced subgraphs and tree decompositions XVI. Complete bipartite induced minors

Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl

We prove that for every graph $G$ with a sufficiently large complete bipartite induced minor, either $G$ has an induced minor isomorphic to a large wall, or $G$ contains a large co…

math.CO2024

A power sum expansion for the Kromatic symmetric function

Laura Pierson

The chromatic symmetric $X_{G}$ function is a symmetric function generalization of the chromatic polynomial of a graph, introduced by Stanley (1995). Stanley gave an expansion formul…

math.CO2024★ 1 cited

Improving the Caro-Wei bound and applications to Turán stability

Tom Kelly, Luke Postle

We prove that if $G$ is a graph and $f (v) \leq 1/ (d (v) + 1/2)$ for each $v \in V (G)$ , then either $G$ has an independent set of size at least $\sum_{v \in V (G)} f (v)$ or $G$ contains…

math.CO2024★ 3 cited

Tree independence number II. Three-path-configurations

Maria Chudnovsky, Sepehr Hajebi, Daniel Lokshtanov +1

A three-path-configuration is a graph consisting of three pairwise internally-disjoint paths the union of every two of which is an induced cycle of length at least four. A graph is…

math.CO2024★ 3 cited

Web bases in degree two from hourglass plabic graphs

Christian Gaetz, Oliver Pechenik, Stephan Pfannerer +2

Webs give a diagrammatic calculus for spaces of $U_{q} (sl_{r})$ -tensor invariants, but intrinsic characterizations of web bases are only known in certain cases. Recently, we…

math.CO2024

On prime Cayley graphs

Maria Chudnovsky, Michal Cizek, Logan Crew +4

The decomposition of complex networks into smaller, interconnected components is a central challenge in network theory with a wide range of potential applications. In this paper, w…

math.CO2024★ 2 cited

Probabilistic operators for non-attacking tableaux and a compact formula for the symmetric Macdonald polynomials

Olya Mandelshtam

We prove a new tableaux formula for the symmetric Macdonald polynomials $P_{λ} (X; q, t)$ that has considerably fewer terms and simpler weights than previously existing formulas. Our fo…

math.CO2024

Bounded degree graphs and hypergraphs with no full rainbow matchings

Ronen Wdowinski

Given a multi-hypergraph $G$ that is edge-colored into color classes $E_{1}, \dots, E_{n}$ , a full rainbow matching is a matching of $G$ that contains exactly one edge from each color…

math.CO2024★ 1 cited

Chordal graphs, even-hole-free graphs and sparse obstructions to bounded treewidth

Sepehr Hajebi

We present and study the following conjecture: for an integer $t \geq 4$ and a graph $H$ , every even-hole-free graph of large enough treewidth has an induced subgraph isomorphic to…

math.CO2023★ 4 cited

List- $k$ -Coloring $H$ -free graphs for all $k > 4$

Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl

Given an integer $k > 4$ and a graph $H$ , we prove that, assuming P $\neq =$ NP, the List- $k$ -Coloring Problem restricted to $H$ -free graphs can be solved in polynomial time if and only…

math.CO2023

A Note on Eigenvalues of Cayley Graphs

Arnbjörg Soffía Árnadóttir, Chris Godsil

A graph is called integral if all its eigenvalues are integers. A Cayley graph is called normal if its connection set is a union of conjugacy classes. We show that a non-empty inte…

math.CO2023

Hopf algebras from poset growth models

Karen Yeats, Stav Zalel

We give a framework for growth models on posets which simultaneously generalizes the Classical Sequential Growth models for posets from causal set theory and the tree growth models…

math.CO2023★ 1 cited

Induced subgraphs and tree decompositions XII. Grid theorem for pinched graphs

Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi +1

Given an integer $c \in N$ , we say a graph $G$ is $c$ -pinched if $G$ does not contain an induced subgraph consisting of $c$ cycles, all going through a single common vertex…

math.CO2023★ 2 cited

Induced subdivisions with pinned branch vertices

Sepehr Hajebi

We prove that for all $r \in N \cup {0}$ and $s, t \in N$ , there exists $Ω = Ω (r, s, t) \in N$ with the following property. Let $G$ be a graph and let $H$ be a…

math.CO2023★ 3 cited

Promotion permutations for tableaux

Christian Gaetz, Oliver Pechenik, Stephan Pfannerer +2

In our companion paper, we develop a new $S L_{4}$ -web basis. Basis elements are given by certain planar graphs and are constructed so that important algebraic operations can be perfo…

math.CO2023★ 2 cited

Rotation-invariant web bases from hourglass plabic graphs

Christian Gaetz, Oliver Pechenik, Stephan Pfannerer +2

Webs give a diagrammatic calculus for spaces of tensor invariants. We introduce hourglass plabic graphs as a new avatar of webs, and use these to give the first rotation-invariant…

math.CO2023★ 38 cited

A chiral aperiodic monotile

David Smith, Joseph Samuel Myers, Craig S. Kaplan +1

The recently discovered "hat" aperiodic monotile mixes unreflected and reflected tiles in every tiling it admits, leaving open the question of whether a single shape can tile aperi…

math.CO2023★ 6 cited

Tree independence number I. (Even hole, diamond, pyramid)-free graphs

Tara Abrishami, Bogdan Alecu, Maria Chudnovsky +3

The tree-independence number tree- $α$ , first defined and studied by Dallard, Milanič and Štorgel, is a variant of treewidth tailored to solving the maximum independent set problem.…

math.CO2023★ 37 cited

An aperiodic monotile

David Smith, Joseph Samuel Myers, Craig S. Kaplan +1

A longstanding open problem asks for an aperiodic monotile, also known as an "einstein": a shape that admits tilings of the plane, but never periodic tilings. We answer this proble…

North-East Lattice Paths Avoiding k Collinear Points via Satisfiability

Orthogonal Latin Squares of Order Ten with Two Relations: A SAT Investigation

Suns in triangle-free graphs of large chromatic number

Myrvold's Results on Orthogonal Triples of 10×10 Latin Squares: A SAT Investigation

Runs in Paperfolding Sequences

Induced subgraphs and tree decompositions XVI. Complete bipartite induced minors

A power sum expansion for the Kromatic symmetric function

Improving the Caro-Wei bound and applications to Turán stability

Tree independence number II. Three-path-configurations

Web bases in degree two from hourglass plabic graphs

On prime Cayley graphs

Probabilistic operators for non-attacking tableaux and a compact formula for the symmetric Macdonald polynomials

Bounded degree graphs and hypergraphs with no full rainbow matchings

Chordal graphs, even-hole-free graphs and sparse obstructions to bounded treewidth

List-k-Coloring H-free graphs for all k>4

A Note on Eigenvalues of Cayley Graphs

Hopf algebras from poset growth models

Induced subgraphs and tree decompositions XII. Grid theorem for pinched graphs

Induced subdivisions with pinned branch vertices

Promotion permutations for tableaux

Rotation-invariant web bases from hourglass plabic graphs

A chiral aperiodic monotile

Tree independence number I. (Even hole, diamond, pyramid)-free graphs

An aperiodic monotile

North-East Lattice Paths Avoiding $k$ Collinear Points via Satisfiability

Myrvold's Results on Orthogonal Triples of $10 \times 10$ Latin Squares: A SAT Investigation

List- $k$ -Coloring $H$ -free graphs for all $k > 4$