Thomas Koshy
- Published in print:
- 2008
- Published Online:
- January 2009
- ISBN:
- 9780195334548
- eISBN:
- 9780199868766
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780195334548.003.0012
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
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
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.
Koko Kalambay Kayibi
- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0011
- Subject:
- Mathematics, Probability / Statistics
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
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.
Peter J. Cameron
- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0001
- Subject:
- Mathematics, Probability / Statistics
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
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.
Steven D. Noble
- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0013
- Subject:
- Mathematics, Probability / Statistics
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
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.
Graham E. Farr
- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0003
- Subject:
- Mathematics, Probability / Statistics
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
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.
Mark Jerrum
- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0009
- Subject:
- Mathematics, Probability / Statistics
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
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.
Nikolai V. Brilliantov and Thorsten Pöschel
- Published in print:
- 2004
- Published Online:
- January 2010
- ISBN:
- 9780198530381
- eISBN:
- 9780191713057
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198530381.003.0007
- Subject:
- Physics, Condensed Matter Physics / Materials
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
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.
Józef Ignaczak and Martin Ostoja‐Starzewski
- Published in print:
- 2009
- Published Online:
- February 2010
- ISBN:
- 9780199541645
- eISBN:
- 9780191716164
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199541645.003.0009
- Subject:
- Mathematics, Applied Mathematics, Mathematical Physics
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
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.
Victor J. Katz and Karen Hunger Parshall
- Published in print:
- 2014
- Published Online:
- October 2017
- ISBN:
- 9780691149059
- eISBN:
- 9781400850525
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691149059.003.0011
- Subject:
- Mathematics, History of Mathematics
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
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.
Ben Brubaker, Daniel Bump, and Solomon Friedberg
- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691150659
- eISBN:
- 9781400838998
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691150659.003.0012
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
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
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.
J. L. Ramírez Alfonsín
- Published in print:
- 2005
- Published Online:
- September 2007
- ISBN:
- 9780198568209
- eISBN:
- 9780191718229
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198568209.003.0004
- Subject:
- Mathematics, Algebra, Combinatorics / Graph Theory / Discrete Mathematics
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
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.
Pavol Hell and Jaroslav Nešetřil
- Published in print:
- 2004
- Published Online:
- September 2007
- ISBN:
- 9780198528173
- eISBN:
- 9780191713644
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198528173.003.0005
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
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
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.
Paul Baird and John C. Wood
- Published in print:
- 2003
- Published Online:
- September 2007
- ISBN:
- 9780198503620
- eISBN:
- 9780191708435
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198503620.003.0005
- Subject:
- Mathematics, Pure Mathematics
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
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.
Nicholas M. Katz
- Published in print:
- 2012
- Published Online:
- October 2017
- ISBN:
- 9780691153308
- eISBN:
- 9781400842704
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691153308.003.0023
- Subject:
- Mathematics, Number Theory
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
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.
Nicholas M. Katz
- Published in print:
- 2012
- Published Online:
- October 2017
- ISBN:
- 9780691153308
- eISBN:
- 9781400842704
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691153308.003.0024
- Subject:
- Mathematics, Number Theory
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.
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.
Peter Hancock and Anton Setzer
- Published in print:
- 2005
- Published Online:
- September 2007
- ISBN:
- 9780198566519
- eISBN:
- 9780191713927
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198566519.003.0007
- Subject:
- Mathematics, Logic / Computer Science / Mathematical Philosophy
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
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.
Rolf Niedermeier
- Published in print:
- 2006
- Published Online:
- September 2007
- ISBN:
- 9780198566076
- eISBN:
- 9780191713910
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198566076.003.0014
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
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
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.
Andrew Goodall
- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0007
- Subject:
- Mathematics, Probability / Statistics
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
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.
Geoffrey Grimmett
- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0008
- Subject:
- Mathematics, Probability / Statistics
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
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.
Sylvie Benzoni-Gavage and Denis Serre
- Published in print:
- 2006
- Published Online:
- September 2007
- ISBN:
- 9780199211234
- eISBN:
- 9780191705700
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199211234.003.0001
- Subject:
- Mathematics, Applied Mathematics
For first-order systems, the well-posedness of the Cauchy problem is equivalent to an algebraic condition on the symbol of the operator: the hyperbolicity. The hyperbolic Cauchy problem has the ...
More
For first-order systems, the well-posedness of the Cauchy problem is equivalent to an algebraic condition on the symbol of the operator: the hyperbolicity. The hyperbolic Cauchy problem has the property of finite velocity of propagation (support, singularities). Important classes are those of symmetric (or symmetrizable) and constantly hyperbolic operators (i.e., with constant multiplicity eigenvalues). Hyperbolic polynomials are interesting on their own. Dispersion can be studied through Strichartz estimates. The adjoint of an hyperbolic operator is hyperbolic.Less
For first-order systems, the well-posedness of the Cauchy problem is equivalent to an algebraic condition on the symbol of the operator: the hyperbolicity. The hyperbolic Cauchy problem has the property of finite velocity of propagation (support, singularities). Important classes are those of symmetric (or symmetrizable) and constantly hyperbolic operators (i.e., with constant multiplicity eigenvalues). Hyperbolic polynomials are interesting on their own. Dispersion can be studied through Strichartz estimates. The adjoint of an hyperbolic operator is hyperbolic.