Combinatorics and Optimization

Permanent URI for this collectionhttps://uwspace.uwaterloo.ca/handle/10012/9928

This is the collection for the University of Waterloo's Department of Combinatorics and Optimization.

Research outputs are organized by type (eg. Master Thesis, Article, Conference Paper).

Waterloo faculty, students, and staff can contact us or visit the UWSpace guide to learn more about depositing their research.

Browse

Browsing Combinatorics and Optimization by Subject "algebraic combinatorics"

Filter results by typing the first few letters
Now showing 1 - 7 of 7
  • Thumbnail Image
    Item
    A Complete Multipartite Basis for the Chromatic Symmetric Function
    (Society for Industrial and Applied Mathematics, 2021-11-15) Crew, Logan; Spirkl, Sophie
    In the vector space of symmetric functions, the elements of the basis of elementary symmetric functions are (up to a factor) the chromatic symmetric functions of disjoint unions of cliques. We consider their graph complements, the functions {rλ:λ an integer partition} defined as chromatic symmetric functions of complete multipartite graphs. This basis was first introduced by Penaguiao [J. Combin. Theory Ser. A, 175 (2020), 105258]. We provide a combinatorial interpretation for the coefficients of the change-of-basis formula between the rλ and the monomial symmetric functions, and we show that the coefficients of the chromatic and Tutte symmetric functions of a graph G when expanded in the r-basis enumerate certain intersections of partitions of V(G).
  • Thumbnail Image
    Item
    Enumeration of Factorizations in the Symmetric Group: From Centrality to Non-centrality
    (University of Waterloo, 2011-04-25T18:39:44Z) Sloss, Craig
    The character theory of the symmetric group is a powerful method of studying enu- merative questions about factorizations of permutations, which arise in areas including topology, geometry, and mathematical physics. This method relies on having an encoding of the enumerative problem in the centre Z(n) of the algebra C[S_n] spanned by the symmetric group S_n. This thesis develops methods to deal with permutation factorization problems which cannot be encoded in Z(n). The (p,q,n)-dipole problem, which arises in the study of connections between string theory and Yang-Mills theory, is the chief problem motivating this research. This thesis introduces a refinement of the (p,q,n)-dipole problem, namely, the (a,b,c,d)- dipole problem. A Join-Cut analysis of the (a,b,c,d)-dipole problem leads to two partial differential equations which determine the generating series for the problem. The first equation determines the series for (a,b,0,0)-dipoles, which is the initial condition for the second equation, which gives the series for (a,b,c,d)-dipoles. An analysis of these equa- tions leads to a process, recursive in genus, for solving the (a,b,c,d)-dipole problem for a surface of genus g. These solutions are expressed in terms of a natural family of functions which are well-understood as sums indexed by compositions of a binary string. The combinatorial analysis of the (a,b,0,0)-dipole problem reveals an unexpected fact about a special case of the (p,q,n)-dipole problem. When q=n−1, the problem may be encoded in the centralizer Z_1(n) of C[S_n] with respect to the subgroup S_{n−1}. The algebra Z_1(n) has many combinatorially important similarities to Z(n) which may be used to find an explicit expression for the genus polynomials for the (p,n−1,n)-dipole problem for all values of p and n, giving a solution to this case for all orientable surfaces. Moreover, the algebraic techniques developed to solve this problem provide an alge- braic approach to solving a class of non-central problems which includes problems such as the non-transitive star factorization problem and the problem of enumerating Z_1- decompositions of a full cycle, and raise intriguing questions about the combinatorial significance of centralizers with respect to subgroups other than S_{n−1}.
  • Thumbnail Image
    Item
    Modular relations of the Tutte symmetric function
    (Elsevier, 2022-04) Crew, Logan; Spirkl, Sophie
    For a graph G, its Tutte symmetric function XBG generalizes both the Tutte polynomial TG and the chromatic symmetric function XG. We may also consider XB as a map from the t-extended Hopf algebra G[t] of labelled graphs to symmetric functions. We show that the kernel of XB is generated by vertex-relabellings and a finite set of modular relations, in the same style as a recent analogous result by Penaguiao on the chromatic symmetric function X. In particular, we find one such relation that generalizes the well-known triangular modular relation of Orellana and Scott, and build upon this to give a modular relation of the Tutte symmetric function for any two-edge-connected graph that generalizes the n-cycle relation of Dahlberg and vanWilligenburg. Additionally, we give a structural characterization of all local modular relations of the chromatic and Tutte symmetric functions, and prove that there is no single local modification that preserves either function on simple graphs.
  • Thumbnail Image
    Item
    On Enumerative Structures in Quantum Field Theory
    (University of Waterloo, 2020-07-13) Mahmoud, Ali
    This thesis addresses a number of enumerative problems that arise in the context of quantum field theory and in the process of renormalization. In particular, the enumeration of rooted connected chord diagrams is further studied and new applications in quenched QED and Yukawa theories are introduced. Chord diagrams appear in quantum field theory in the context of Dyson-Schwinger equations, where, according to recent results, they are used to express the solutions. In another direction, we study the action of point field diffeomorphisms on a free theory. We give a new proof of a vanishing phenomenon for tree-level amplitudes of the transformed theories. A functional equation for $2$-connected chord diagrams is discovered, then is used to calculate the full asymptotic expansion of the number of $2$-connected chord diagrams by means of alien derivatives applied to factorially divergent power series. The calculation extends the older result by D. J. Kleitman on counting irreducible diagrams. Namely, Kleitman's result calculates the first coefficient of the infinite asymptotic expansion derived here and is therefore an approximation of the result presented. In calculating the asymptotics this way we are following the approach M. Borinsky used for solving the asymptotic counting problem of general connected chord diagrams. The numbers of $2$-connected chord diagrams and the sequence of coefficients of their asymptotic expansion amazingly also appeared, without being recognized, in more physical situations in the work of Broadhurst on 4-loop Dyson-Schwinger-Johnson anatomy, and among the renormalized quantities of quenched QED calculated by M. Borinsky. The underlying chord-diagrammatic structure of quenched QED and Yukawa theory is unveiled here. Realizing this combinatorial structure makes the asymptotic analysis of the Green functions of these theories easier, and no longer requires singularity analysis. As a subsidiary outcome, a combinatorial interpretation of sequence \href{https://oeis.org/A088221}{A088221} in terms of chord diagrams is obtained from analysing some of the expressions in the asymptotic expansion of connected chord diagrams in the work of M. Borinsky. Lastly, a problem from another context is considered. The problem was to reprove the cancellation of interaction terms produced by applying a point field diffeomorphism to a free field theory. The original proof by D. Kreimer and K. Yeats was intricate in a way that did not provide much insight, and, therefore, a proof on the level of generating functions was desired. This is what we do here. We show that the series of the tree-level amplitudes is exactly the compositional inverse of the diffeomorphism applied to the free theory. The relation to the combinatorial Legendre transform defined by D. Jackson, A. Kempf and A. Morales is outlined although still not settled. Simple combinatorial proofs are also given for some Bell polynomial identities.
  • Thumbnail Image
    Item
    Partition Algebras and Kronecker Coefficients
    (University of Waterloo, 2015-08-28) Marcott, Cameron
    Classical Schur-Weyl duality relates the representation theory of the general linear group to the representation theory of the symmetric group via their commuting actions on tensor space. With the goal of studying Kronecker products of symmetric group representations, the partition algebra is introduced as the commutator algebra of the diagonal action of the symmetric group on tensor space. An analysis of the representation theory of the partition offers results relating reduced Kronecker coefficients to Kronecker coefficients.
  • Thumbnail Image
    Item
    Sequences of Trees and Higher-Order Renormalization Group Equations
    (University of Waterloo, 2019-08-27) Dugan, William
    In 1998, Connes and Kreimer introduced a combinatorial Hopf algebra HCK on the vector space of forests of rooted trees that precisely explains the phenomenon of renormalization in quantum field theory. This Hopf algebra has been of great interest since its inception, as it connects the disciplines of algebra, combinatorics, and physics, providing interesting questions in each. In this thesis we introduce the notion of higher-order renormalization group equations, which generalize the usual renormalization group equation of quantum field theory, and further define a corresponding notion of order on certain sequences of trees constituting elements of the completion of HCK. We also give an explication of a result, due to Foissy, that characterizes which sequences of linear combinations of trees with one generator in each degree generate Hopf subalgebras of HCK. We conclude with some results towards classifying these sequences by their order (when such an order is admitted), and discuss the place of the Connes-Moscovici Hopf subalgebra in the context of this new framework.
  • Thumbnail Image
    Item
    Some Applications of Combinatorial Hopf Algebras to Integro-Differential Equations and Symmetric Function Identities
    (University of Waterloo, 2024-07-09) Olson-Harris, Nicholas
    Hopf algebras built from combinatorial objects have found application both within combinatorics and, following the work of Connes and Kreimer, in quantum field theory. Despite the apparent gulf between these areas, the types of Hopf algebras that arise are very similar. We use Hopf algebra techniques to solve two problems, one coming from quantum field theory and one from algebraic combinatorics. (1) Dyson–Schwinger equations are a formulation of the equations of motion of quantum field theory. From a mathematical perspective they are integro-differential equations which have a recursive, tree-like structure. In some cases, these equations are known to have solutions which can be written as combinatorial expansions over connected chord diagrams. We give a new expansion in terms of rooted trees equipped with a kind of decomposition we call a binary tubing. This is similar to the chord diagram expansion, but holds in greater generality, including to systems of Dyson–Schwinger equations and to Dyson–Schwinger equations in which insertion places are distinguished by different variables in the Mellin transform. Moreover we prove these results as a direct application of a purely Hopf-algebraic theorem characterizing maps from the Connes–Kreimer Hopf algebra of rooted trees (and variants thereof) to the Hopf algebra of univariate polynomials which arise from the universal property of the former. (2) A pair of skew Ferrers shapes are said to be skew-equivalent if they admit the same number of semistandard Young tableaux of each weight, or in other words if the skew Schur functions they define are equal. McNamara and van Willigenburg conjectured necessary and sufficient combinatorial conditions for this to happen but were unable to prove either direction in complete generality. Using Hopf-algebraic techniques building on a partial result of Yeats, we prove sufficiency.