Search Results

Pascal' Triangle and Catalan Numbers

Thomas Koshy

in Catalan Numbers with Applications

This chapter shows the various ways Catalan numbers can be extracted from Pascal's triangle. It includes discussion of nonisomorphic groups, Catalan polynomials, Touchard's recursive formula, and ... More

This chapter shows the various ways Catalan numbers can be extracted from Pascal's triangle. It includes discussion of nonisomorphic groups, Catalan polynomials, Touchard's recursive formula, and Jonah's theorem.Less

EXPANDING THE TUTTE POLYNOMIAL OF A MATROID OVER THE INDEPENDENT SETS

Koko Kalambay Kayibi

in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

This chapter provides direct combinatorial proof of an expansion of the Tutte polynomial by independent sets of the matroid. Another expansion of the Tutte polynomial is presented in terms of ... More

This chapter provides direct combinatorial proof of an expansion of the Tutte polynomial by independent sets of the matroid. Another expansion of the Tutte polynomial is presented in terms of spanning sets. In the process, it is shown that there is a partition of the set of independent sets of a matroid, such that if the independent set I and the basis B are contained in the same part of the partition, the external activity of I is equal to the external activity of B.Less

ORBIT COUNTING AND THE TUTTE POLYNOMIAL

Peter J. Cameron

in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

This chapter summarizes the various attempts to extend the Tutte polynomial of a matroid to a polynomial which counts orbits of a group on various sets of objects that the usual Tutte polynomial ... More

This chapter summarizes the various attempts to extend the Tutte polynomial of a matroid to a polynomial which counts orbits of a group on various sets of objects that the usual Tutte polynomial counts. In other words, the aim is to produce a hybrid of the Tutte polynomial and the cycle index polynomial. There have been various attempts at this, some of which are good for some aims but not for others.Less

COMPLEXITY OF GRAPH POLYNOMIALS

Steven D. Noble

in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

This chapter examines the complexity of evaluating graph polynomials, related to the Tutte polynomial, for various classes of matroids. It begins with a short introduction to matroids, complexity, ... More

This chapter examines the complexity of evaluating graph polynomials, related to the Tutte polynomial, for various classes of matroids. It begins with a short introduction to matroids, complexity, and the Tutte polynomial. The intractability results for the Tutte polynomial are then discussed, including proof of the most often quoted result of classifying the hard points for evaluation of the Tutte polynomial in the graphic case. Contrasting results are presented, giving polynomial time algorithms for restricted classes of input, particularly graphs with bounded tree-width. Finally, the complexity results for various classes of matroids are presented.Less

TUTTE-WHITNEY POLYNOMIALS: SOME HISTORY AND GENERALIZATIONS

Graham E. Farr

in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

The Tutte-Whitney polynomials play a key role in the study of counting problems on graphs, and have close connections with statistical mechanics and knot theory. This chapter briefly reviews their ... More

The Tutte-Whitney polynomials play a key role in the study of counting problems on graphs, and have close connections with statistical mechanics and knot theory. This chapter briefly reviews their history and outlines a number of generalizations. It then describes some generalized Tutte-Whitney functions and extends some of these further. These functions are defined for arbitrary collections of sets and for arbitrary binary functions, and have some of the characteristic elements of Tutte-Whitney theory, including interesting partial evaluations and deletion-contraction relations.Less

APPROXIMATING THE TUTTE POLYNOMIAL

Mark Jerrum

in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

This chapter examines some algorithmic problems associated with matroids. It focuses on determining a ‘fully polynomial randomized approximation scheme’ or ‘FPRAS’. First, the problem of counting ... More

This chapter examines some algorithmic problems associated with matroids. It focuses on determining a ‘fully polynomial randomized approximation scheme’ or ‘FPRAS’. First, the problem of counting matroid bases is considered. Feder and Mihail's polynomial time algorithm for approximating the number of bases in ‘balanced’ matroids is then described, and an improved analysis from Jerrum and Son is presented. The more general problem of evaluating the Tutte polynomial is discussed. This is a two-variable polynomial T(M; x, y) which is associated with a matroid M that encodes much information about M. What is known about the complexity of approximating the Tutte polynomial is reviewed, and the boundary is extended.Less

Finding the Roots of Algebraic Equations

Victor J. Katz and Karen Hunger Parshall

in Taming the Unknown: A History of Algebra from Antiquity to the Early Twentieth Century

This chapter highlights some of the struggles to solve fifth-degree polynomials as well as the development of the idea of a group and its application to answering the question of solvability of ... More

This chapter highlights some of the struggles to solve fifth-degree polynomials as well as the development of the idea of a group and its application to answering the question of solvability of polynomial equations. It begins by surveying some of the methods by which mathematicians attempted to solve—and sometimes did solve—various algebraic equations of degree higher than four. The chapter then turns to the theory of permutations as well as group theory. It turned out that the key to proving the impossibility of the fifth-degree polynomials and, more generally, the key to determining which polynomial equations were, in fact, solvable algebraically, was a totally new construct, the group.Less

Sonine Polynomials Expansion of The Velocity Distribution Function

Nikolai V. Brilliantov and Thorsten Pöschel

in Kinetic Theory of Granular Gases

The velocity distribution of function of a granular gas is different from the Maxwell distribution. It may be represented in the form of a Sonine polynomials expansion. This chapter shows that the ... More

The velocity distribution of function of a granular gas is different from the Maxwell distribution. It may be represented in the form of a Sonine polynomials expansion. This chapter shows that the coefficients of this expansion describe the moments of the velocity distribution function. The first non-trivial Sonine coefficient a2 is of particular interest for the gas kinetics.Less

Thermoelastic Polynomials

Józef Ignaczak and Martin Ostoja‐Starzewski

in Thermoelasticity with Finite Wave Speeds

This chapter begins from the observation that the fundamental solutions of the G‐L theory may be determined with the help of polynomial sequences on the time axis, the so‐called polynomials of ... More

This chapter begins from the observation that the fundamental solutions of the G‐L theory may be determined with the help of polynomial sequences on the time axis, the so‐called polynomials of thermoelasticity. A number of recurrence relations describing these polynomials is given, and then it is shown that a pair of thermoelastic polynomials can be identified with an element of the null space of a linear ordinary differential operator. On this basis, an integral relation and associated thermoelastic polynomials are developed.Less

Knowability

Ben Brubaker, Daniel Bump, and Solomon Friedberg

in Weyl Group Multiple Dirichlet Series: Type A Combinatorial Theory (AM-175)

This chapter introduces the Knowability Lemma, which explains when products of Gauss sums associated to elements of a preaccordion are explicitly evaluable as polynomials in q, the order of the ... More

This chapter introduces the Knowability Lemma, which explains when products of Gauss sums associated to elements of a preaccordion are explicitly evaluable as polynomials in q, the order of the residue class field. It considers an episode in the cartoon associated to the short Gelfand-Tsetlin pattern and the three cases that apply according to the Knowability Lemma, two of which are maximality and knowability. Knowability is not important for the proof that Statement C implies Statement B. The chapter discusses the cases where ε‎ is Class II or Class I, leaving the remaining two cases to the reader. It also describes the variant of the argument for the case that ε‎ is of Class I, again leaving the two other cases to the reader.Less

Sylvester denumerant

J. L. Ramírez Alfonsín

in The Diophantine Frobenius Problem

In 1857, while investigating the partition number function, J. J. Sylvester defined the function d(m; a1, . . . , an), called the denumerant, as the number of nonnegative integer representations of m ... More

In 1857, while investigating the partition number function, J. J. Sylvester defined the function d(m; a1, . . . , an), called the denumerant, as the number of nonnegative integer representations of m by a1, . . . , an. This chapter is devoted to the study of the denumerant and related functions. After discussing briefly some basic properties of the partition function and its relation with denumerants, the general behaviour of d(m; a1, . . . , an) and its connection to g(a1, . . . , an) are analyzed. Two interesting methods for computing denumerants — one based on a decomposition of the rational fraction into partial fractions and another due to E. T. Bell — are described. An exact value of d(m; p, q) — first found by T. Popoviciu in 1953 — is proved, and the known results when n = 2 and n = 3 are summarized. The calculation of g(a1, . . . , an) by using Hilbert series via free resolutions, and the use of this approach to show an explicit formula for g(a1, a2, a3), are shown. The connection among denumerants, FP, and Ehrhart polynomial as well as two variants of d(m; a1, . . . , an) are discussed.Less

TESTING FOR THE EXISTENCE OF HOMOMORPHISMS

Pavol Hell and Jaroslav Nešetřil

in Graphs and Homomorphisms

This chapter explores the algorithmic aspects of graph homomorphisms and of similar partition problems. The highlights include the dichotomy classification of graph homomorphisms to a fixed target ... More

This chapter explores the algorithmic aspects of graph homomorphisms and of similar partition problems. The highlights include the dichotomy classification of graph homomorphisms to a fixed target graph $H$; a proof of the fact that dichotomy for digraph homomorphisms would imply dichotomy for all constraint satisfaction problems; a presentation of consistency-based algorithms; and associated dualities that seem to be applicable to all known polynomial cases of the digraph homomorphism problem. The role of polymorphisms in the design of polynomial algorithms is highlighted, and it is shown that graphs with the same set of polymorphisms define polynomially equivalent problems. The polymorphism known as the majority function is shown to yield a polynomial time homomorphism testing algorithm. The dichotomy classification of list homomorphism problems for reflexive graphs is presented. List matrix partition problems are posed in the language of trigraph homomorphisms, and the richness of the associated algorithms is illustrated on the case of clique cutsets and generalized split graphs.Less

Harmonic morphisms defined by polynomials

Paul Baird and John C. Wood

in Harmonic Morphisms Between Riemannian Manifolds

This chapter establishes the Liouville-type theorem which asserts that any entire (i.e., globally defined) harmonic morphism from a Euclidean space of arbitrary dimension to a Euclidean space of ... More

This chapter establishes the Liouville-type theorem which asserts that any entire (i.e., globally defined) harmonic morphism from a Euclidean space of arbitrary dimension to a Euclidean space of dimension more than two is necessarily polynomial. In fact, the harmonic morphism need only be defined off a closed polar set. It is shown that any horizontally conformal polynomial mapping is necessarily harmonic and, hence, a harmonic morphism. At a critical point of finite order, a horizontally conformal mapping is approximated, at least at the level of the first non-constant term in its Taylor expansion, by a harmonic morphism. Important classes of polynomial harmonic morphisms are classified. This provides information on the local behaviour of a harmonic morphism near a critical point, and leads to global topological restrictions on its domain.Less

SL(n) Examples with Slightly Composite n

Nicholas M. Katz

in Convolution and Equidistribution: Sato-Tate Theorems for Finite-Field Mellin Transforms (AM-180)

This chapter continues to study the object N of Theorem 21.1. Thus, k is a finite field of characteristic p, ψ‎ a nontrivial additive character of k, f(x) = f(x)=∑i=−baAixi∈k[x,1/x]Aᵢxⁱ ɛ k[x, 1/x] ... More

This chapter continues to study the object N of Theorem 21.1. Thus, k is a finite field of characteristic p, ψ‎ a nontrivial additive character of k, f(x) = f(x)=∑i=−baAixi∈k[x,1/x]Aᵢxⁱ ɛ k[x, 1/x] is a Laurent polynomial of “bidegree” (a, b), with a; b both ≤ 1 and both prime to p. It is assumed that f(x) is Artin–Schreier reduced. It takes for N the object N:ℒψ(f(x))(1/2)[1]∈ρarith.Less

Other SL(n) Examples

Nicholas M. Katz

in Convolution and Equidistribution: Sato-Tate Theorems for Finite-Field Mellin Transforms (AM-180)

This chapter fixes an integer n ≤ 3 which is not a power of the characteristic p, and a monic polynomial f(x) ɛ k[x] of degree n, f(x)=∑i=0nAixi, An=1.

FOURIER ANALYSIS ON FINITE ABELIAN GROUPS: SOME GRAPHICAL APPLICATIONS

Andrew Goodall

in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

This article reviews basic techniques of Fourier analysis on a finite abelian group Q, with subsequent applications in graph theory. These include evaluations of the Tutte polynomial of a graph G in ... More

This article reviews basic techniques of Fourier analysis on a finite abelian group Q, with subsequent applications in graph theory. These include evaluations of the Tutte polynomial of a graph G in terms of cosets of the Q-flows of G. Other applications to spanning trees of Cayley graphs and to group-valued models on phylogenetic trees are also presented to illustrate methods.Less

FLOWS AND FERROMAGNETS

Geoffrey Grimmett

in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

The Tutte polynomial and its relatives play important roles in matroid theory, computational complexity, and models of statistical physics. They provide the natural way to count and relate a variety ... More

The Tutte polynomial and its relatives play important roles in matroid theory, computational complexity, and models of statistical physics. They provide the natural way to count and relate a variety of objects defined on graphs. This chapter shows that they permit a representation of the two-point correlation function of a ferromagnetic Potts model on a graph G in terms of the flow polynomials of certain related random graphs. This representation extends to general Potts models the so-called random-current expansion for Ising models, and it amplifies the links between the Potts partition function and the Tutte polynomial.Less

INTERACTIVE PROGRAMS AND WEAKLY FINAL COALGEBRAS IN DEPENDENT TYPE THEORY

Peter Hancock and Anton Setzer

in From Sets and Types to Topology and Analysis: Towards practicable foundations for constructive mathematics

This chapter considers the representation of interactive programs in dependent type theory and bases it on the monadic I/O used in Haskell. Two versions are described: in the first the interface with ... More

This chapter considers the representation of interactive programs in dependent type theory and bases it on the monadic I/O used in Haskell. Two versions are described: in the first the interface with the real world is fixed, while in the second the potential interactions may depend on the history of previous interactions. It also looks at client and server programs, which run on opposite sides of an interface. The type of interactive program is defined as a weakly final coalgebra for a general form of polynomial functor. The chapter gives formation/introduction/elimination/equality rules for these coalgebras. The relationship of the corresponding rules with guarded induction is studied by showing that the introduction rules are a slightly restricted form of guarded induction. However, the form in which they represent guarded induction is not by means of recursive equations but by using an elimination operator in a crucial way.Less

CONNECTIONS TO APPROXIMATION ALGORITHMS

Rolf Niedermeier

in Invitation to Fixed-Parameter Algorithms

This chapter summarizes the currently known connections between fixed-parameter and polynomial-time approximation algorithmics. Important topics in this context are lower bound and impossibility ... More

This chapter summarizes the currently known connections between fixed-parameter and polynomial-time approximation algorithmics. Important topics in this context are lower bound and impossibility results. In particular, polynomial-time approximation schemes are discussed in some detail, providing a link with parameterized complexity theory.Less

THE CONTRIBUTIONS OF DOMINIC WELSH TO MATROID THEORY

James Oxley

in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

Dominic Welsh began writing papers in matroid theory nearly forty years ago. Since then, he has made numerous important contributions to the subject. This chapter reviews Dominic Welsh's work in and ... More

Dominic Welsh began writing papers in matroid theory nearly forty years ago. Since then, he has made numerous important contributions to the subject. This chapter reviews Dominic Welsh's work in and influence on the development of matroid theory.Less