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.0010
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
This chapter investigates several occurrences of Catalan numbers in the theory of partitioning. Noncrossing partition is explained in detail.
This chapter investigates several occurrences of Catalan numbers in the theory of partitioning. Noncrossing partition is explained in detail.
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.
Debraj Ray
- Published in print:
- 2007
- Published Online:
- January 2008
- ISBN:
- 9780199207954
- eISBN:
- 9780191709104
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199207954.001.0001
- Subject:
- Economics and Finance, Financial Economics
The formation of coalitions to achieve both collaborative and competitive goals is a phenomenon we see all around us. The list of examples of this phenomenon is long and varied: production cartels, ...
More
The formation of coalitions to achieve both collaborative and competitive goals is a phenomenon we see all around us. The list of examples of this phenomenon is long and varied: production cartels, political lobbies, customs unions, environmental coalitions, and ethnic alliances are just a few everyday instances. This book looks at coalition formation from the perspective of game theory. How are agreements determined? Which coalitions will form? And are such agreements invariably efficient from a social perspective? The book brings together developments in both cooperative and non-cooperative game theory to study the analytics of coalition formation and binding agreements. It concentrates on pure theory, but discusses several potential applications, such as oligopoly and the provision of public goods.Less
The formation of coalitions to achieve both collaborative and competitive goals is a phenomenon we see all around us. The list of examples of this phenomenon is long and varied: production cartels, political lobbies, customs unions, environmental coalitions, and ethnic alliances are just a few everyday instances. This book looks at coalition formation from the perspective of game theory. How are agreements determined? Which coalitions will form? And are such agreements invariably efficient from a social perspective? The book brings together developments in both cooperative and non-cooperative game theory to study the analytics of coalition formation and binding agreements. It concentrates on pure theory, but discusses several potential applications, such as oligopoly and the provision of public goods.
Iain Mclean and Alistair McMillan
- Published in print:
- 2005
- Published Online:
- February 2006
- ISBN:
- 9780199258208
- eISBN:
- 9780191603334
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/0199258201.003.0005
- Subject:
- Political Science, UK Politics
This chapter examines the unravelling of the Union between 1886 and 1921. It discusses the continuing link between Union and Empire, the incoherence of Diceyan Unionism, centre-periphery politics, ...
More
This chapter examines the unravelling of the Union between 1886 and 1921. It discusses the continuing link between Union and Empire, the incoherence of Diceyan Unionism, centre-periphery politics, the attempted Unionist coup-d’etat in 1910-14, Bonar Law and Ulster paramilitarism, George V’s threatened vetoes, and primoridal and instrumental Unionism. By 1921, the Union question had resolved into a Northern Ireland question and an imperial question. It left two ragged ends from the 1886 attempt to settle it, namely representation and finance in the outlying parts of the Union.Less
This chapter examines the unravelling of the Union between 1886 and 1921. It discusses the continuing link between Union and Empire, the incoherence of Diceyan Unionism, centre-periphery politics, the attempted Unionist coup-d’etat in 1910-14, Bonar Law and Ulster paramilitarism, George V’s threatened vetoes, and primoridal and instrumental Unionism. By 1921, the Union question had resolved into a Northern Ireland question and an imperial question. It left two ragged ends from the 1886 attempt to settle it, namely representation and finance in the outlying parts of the Union.
John McGarry and Brendan O'Leary
- Published in print:
- 2004
- Published Online:
- August 2004
- ISBN:
- 9780199266579
- eISBN:
- 9780191601446
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/0199266573.003.0003
- Subject:
- Political Science, UK Politics
The chapter, initially published in 1989, reviews efforts by the UK and Irish governments to achieve a settlement in Northern Ireland during the late 1980s. It bears the impress of its time; ...
More
The chapter, initially published in 1989, reviews efforts by the UK and Irish governments to achieve a settlement in Northern Ireland during the late 1980s. It bears the impress of its time; normatively consociational, but somewhat bleak in its assessments. It contains an appraisal of constitutional options facing policymakers.Less
The chapter, initially published in 1989, reviews efforts by the UK and Irish governments to achieve a settlement in Northern Ireland during the late 1980s. It bears the impress of its time; normatively consociational, but somewhat bleak in its assessments. It contains an appraisal of constitutional options facing policymakers.
Nikolaus Beck
- Published in print:
- 2008
- Published Online:
- September 2008
- ISBN:
- 9780199231423
- eISBN:
- 9780191710865
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199231423.003.0010
- Subject:
- Business and Management, Political Economy
This chapter shows that organizational ecology is much more sociological and less biological than many critics of organizational ecology think. It argues that organizational ecology and its theory of ...
More
This chapter shows that organizational ecology is much more sociological and less biological than many critics of organizational ecology think. It argues that organizational ecology and its theory of competition rests heavily on the seminal work of Emile Durkheim on the division of labour, and on the thoughts of Amos Hawley on human ecology. It suggests that the expressions used by the agents of organizational ecology are ‘Darwinian’ but that the theoretical argumentation is ‘Durkheimian’. The chapter highlights the theoretical foundations of organizational ecology and emphasizes that competition — and not the biological aspects of evolution — forms the core of the organizational ecology theory. The most the most important sub-concepts of organizational ecology that deal with competition and market formation are also discussed: density dependence and resource partitioning. The first concept deals with the impact of the number of competitors on the survival and founding chances of organizations. The latter is concerned with the influence of market concentration on the vital rates of specialist and generalist organizations.Less
This chapter shows that organizational ecology is much more sociological and less biological than many critics of organizational ecology think. It argues that organizational ecology and its theory of competition rests heavily on the seminal work of Emile Durkheim on the division of labour, and on the thoughts of Amos Hawley on human ecology. It suggests that the expressions used by the agents of organizational ecology are ‘Darwinian’ but that the theoretical argumentation is ‘Durkheimian’. The chapter highlights the theoretical foundations of organizational ecology and emphasizes that competition — and not the biological aspects of evolution — forms the core of the organizational ecology theory. The most the most important sub-concepts of organizational ecology that deal with competition and market formation are also discussed: density dependence and resource partitioning. The first concept deals with the impact of the number of competitors on the survival and founding chances of organizations. The latter is concerned with the influence of market concentration on the vital rates of specialist and generalist organizations.
Barry M McCoy
- Published in print:
- 2009
- Published Online:
- February 2010
- ISBN:
- 9780199556632
- eISBN:
- 9780191723278
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199556632.001.0001
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This book begins where elementary books and courses leave off and covers the advances made in statistical mechanics in the past fifty years. The book is divided into three parts. The first part is on ...
More
This book begins where elementary books and courses leave off and covers the advances made in statistical mechanics in the past fifty years. The book is divided into three parts. The first part is on general theory which includes a summary of the basic principles of statistical mechanics; a presentation of the physical phenomena covered and the models used to discuss them; theorems on the existence and uniqueness of partition functions; theorems on order; and critical phenomena and scaling theory. The second part is on series and numerical methods which includes derivations of the Mayer and Ree–Hoover expansions of the low density virial equation of state; Groeneveld's theorems; the application to hard spheres and discs; a summary of numerical studies of systems at high density; and the use of high temperature series expansions to estimate critical exponents for magnets. The third part covers exactly solvable models which includes a detailed presentation of the Pfaffian methods of computing the Ising partition function, magnetization, correlation functions, and susceptibility; the star-triangle (Yang–Baxter equation); functional equations and the free energy for the eight-vertex model; and the hard hexagon and chiral Potts models. All needed mathematics is developed in detail and many open questions are discussed. The goal is to guide the reader to the current forefront of research.Less
This book begins where elementary books and courses leave off and covers the advances made in statistical mechanics in the past fifty years. The book is divided into three parts. The first part is on general theory which includes a summary of the basic principles of statistical mechanics; a presentation of the physical phenomena covered and the models used to discuss them; theorems on the existence and uniqueness of partition functions; theorems on order; and critical phenomena and scaling theory. The second part is on series and numerical methods which includes derivations of the Mayer and Ree–Hoover expansions of the low density virial equation of state; Groeneveld's theorems; the application to hard spheres and discs; a summary of numerical studies of systems at high density; and the use of high temperature series expansions to estimate critical exponents for magnets. The third part covers exactly solvable models which includes a detailed presentation of the Pfaffian methods of computing the Ising partition function, magnetization, correlation functions, and susceptibility; the star-triangle (Yang–Baxter equation); functional equations and the free energy for the eight-vertex model; and the hard hexagon and chiral Potts models. All needed mathematics is developed in detail and many open questions are discussed. The goal is to guide the reader to the current forefront of research.
Hendrik Lorenz
- Published in print:
- 2006
- Published Online:
- September 2006
- ISBN:
- 9780199290635
- eISBN:
- 9780191604027
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/0199290636.003.0003
- Subject:
- Philosophy, Ancient Philosophy
This chapter raises and explains two central questions about Plato’s theory of the tripartite soul. First, what is involved in Plato’s claim that the embodied human soul is a thing of parts? ...
More
This chapter raises and explains two central questions about Plato’s theory of the tripartite soul. First, what is involved in Plato’s claim that the embodied human soul is a thing of parts? Secondly, does Plato have a reasonable basis for holding that the soul is composed of precisely three parts, reason, spirit, and appetite?Less
This chapter raises and explains two central questions about Plato’s theory of the tripartite soul. First, what is involved in Plato’s claim that the embodied human soul is a thing of parts? Secondly, does Plato have a reasonable basis for holding that the soul is composed of precisely three parts, reason, spirit, and appetite?
Hendrik Lorenz
- Published in print:
- 2006
- Published Online:
- September 2006
- ISBN:
- 9780199290635
- eISBN:
- 9780191604027
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/0199290636.003.0004
- Subject:
- Philosophy, Ancient Philosophy
This chapter argues that Republic-style partition of the soul amounts to a position that can fairly be characterized in terms of two main claims. First, the proper subjects of desires and aversions ...
More
This chapter argues that Republic-style partition of the soul amounts to a position that can fairly be characterized in terms of two main claims. First, the proper subjects of desires and aversions are not whole souls, but in each case some part or other of the soul in question. Secondly, the parts of the soul that are the proper subjects of desires and aversions are unified in the strong sense that it is impossible for a given soul-part to desire something and at the same time to be averse to it.Less
This chapter argues that Republic-style partition of the soul amounts to a position that can fairly be characterized in terms of two main claims. First, the proper subjects of desires and aversions are not whole souls, but in each case some part or other of the soul in question. Secondly, the parts of the soul that are the proper subjects of desires and aversions are unified in the strong sense that it is impossible for a given soul-part to desire something and at the same time to be averse to it.
Hendrik Lorenz
- Published in print:
- 2006
- Published Online:
- September 2006
- ISBN:
- 9780199290635
- eISBN:
- 9780191604027
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/0199290636.003.0005
- Subject:
- Philosophy, Ancient Philosophy
This chapter addresses the concern that for a Platonic soul to make sense, is not right to say that it has genuine parts. It also assesses the philosophical cost of soul-partition by considering its ...
More
This chapter addresses the concern that for a Platonic soul to make sense, is not right to say that it has genuine parts. It also assesses the philosophical cost of soul-partition by considering its impact on the question of the soul’s immortality and by worrying, with Aristotle, about the soul’s unity.Less
This chapter addresses the concern that for a Platonic soul to make sense, is not right to say that it has genuine parts. It also assesses the philosophical cost of soul-partition by considering its impact on the question of the soul’s immortality and by worrying, with Aristotle, about the soul’s unity.
Sammy Smooha
- Published in print:
- 2001
- Published Online:
- November 2003
- ISBN:
- 9780199244348
- eISBN:
- 9780191599866
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/0199244340.003.0013
- Subject:
- Political Science, UK Politics
Smooha argues that Jews have settled in Palestine – Land of Israel in sufficient strength to establish a strong independent state in part of the area (pre‐1967 Israel), although their attempt to ...
More
Smooha argues that Jews have settled in Palestine – Land of Israel in sufficient strength to establish a strong independent state in part of the area (pre‐1967 Israel), although their attempt to incorporate the rest (the West Bank and Gaza) by settlement has failed. As a result, partition has become the most feasible way to resolve the Jewish–Palestinian conflict. In Ireland, by contrast, the position of British settlers (Protestants) is said to be much weaker than their Jewish counterparts. The Protestants are weak demographically, lack international legitimacy, are not supported by Britain, and are faced with a confident Irish nationalism. As a consequence, the historical trend points to Britain's withdrawal and an end to the partition of Ireland as the most likely form of conflict resolution.Less
Smooha argues that Jews have settled in Palestine – Land of Israel in sufficient strength to establish a strong independent state in part of the area (pre‐1967 Israel), although their attempt to incorporate the rest (the West Bank and Gaza) by settlement has failed. As a result, partition has become the most feasible way to resolve the Jewish–Palestinian conflict. In Ireland, by contrast, the position of British settlers (Protestants) is said to be much weaker than their Jewish counterparts. The Protestants are weak demographically, lack international legitimacy, are not supported by Britain, and are faced with a confident Irish nationalism. As a consequence, the historical trend points to Britain's withdrawal and an end to the partition of Ireland as the most likely form of conflict resolution.
Stephen J. Blundell and Katherine M. Blundell
- Published in print:
- 2009
- Published Online:
- February 2010
- ISBN:
- 9780199562091
- eISBN:
- 9780191718236
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199562091.003.0025
- Subject:
- Physics, Particle Physics / Astrophysics / Cosmology
This chapter repeats the derivation of the partition function for a gas, and hence of the other thermodynamic properties that can be obtained from it, but this time includes relativistic effects. It ...
More
This chapter repeats the derivation of the partition function for a gas, and hence of the other thermodynamic properties that can be obtained from it, but this time includes relativistic effects. It shows that this leads to some subtle changes in these properties which have profound consequences. It first reviews the full relativistic dispersion relation for particles with non-zero mass and then derives the partition function for ultrarelativistic particles.Less
This chapter repeats the derivation of the partition function for a gas, and hence of the other thermodynamic properties that can be obtained from it, but this time includes relativistic effects. It shows that this leads to some subtle changes in these properties which have profound consequences. It first reviews the full relativistic dispersion relation for particles with non-zero mass and then derives the partition function for ultrarelativistic particles.
Klaus H. Goetz
- Published in print:
- 1999
- Published Online:
- November 2003
- ISBN:
- 9780198294467
- eISBN:
- 9780191600067
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/0198294468.003.0008
- Subject:
- Political Science, Comparative Politics
This account of institutional change and positional differentiation of senior officials in Germany's Federal administration is presented in five sections. Section I, ‘Senior Officials and the ...
More
This account of institutional change and positional differentiation of senior officials in Germany's Federal administration is presented in five sections. Section I, ‘Senior Officials and the Reassertion of Political Authority’, is introductory and discusses the causes and implications of change in the organization and in the political and administrative roles of the senior civil service; changes identified include party politicization, parliamentarization and federalization of the national policy process, modernization initiatives, European integration, and unification. Section II gives a brief survey of the Federal senior ministerial personnel (looking at pay grade and rank, and centrality), and section III considers paths to the top, paying particular attention to the procedures for recruitment and promotion and the consequences of weak formal structures for personnel planning and development. Following on from the definition of political craft as a defining attribute of effective top officials, section IV highlights the central position of political coordination units as training grounds in the Federal administration and comments on the informal positional differentiation that they encourage. The discussion concludes in section V with an assessment of the implications of the partition of the ministerial bureaucracy between Bonn and Berlin.Less
This account of institutional change and positional differentiation of senior officials in Germany's Federal administration is presented in five sections. Section I, ‘Senior Officials and the Reassertion of Political Authority’, is introductory and discusses the causes and implications of change in the organization and in the political and administrative roles of the senior civil service; changes identified include party politicization, parliamentarization and federalization of the national policy process, modernization initiatives, European integration, and unification. Section II gives a brief survey of the Federal senior ministerial personnel (looking at pay grade and rank, and centrality), and section III considers paths to the top, paying particular attention to the procedures for recruitment and promotion and the consequences of weak formal structures for personnel planning and development. Following on from the definition of political craft as a defining attribute of effective top officials, section IV highlights the central position of political coordination units as training grounds in the Federal administration and comments on the informal positional differentiation that they encourage. The discussion concludes in section V with an assessment of the implications of the partition of the ministerial bureaucracy between Bonn and Berlin.
Gurharpal Singh
- Published in print:
- 2001
- Published Online:
- November 2003
- ISBN:
- 9780199244904
- eISBN:
- 9780191600050
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/0199244901.003.0005
- Subject:
- Political Science, Comparative Politics
Gurharpal Singh traces the institutional dependence of the Indian state on conceptions of itself and its original borders as sacrosanct. But, the author argues that the state is, in reality, reshaped ...
More
Gurharpal Singh traces the institutional dependence of the Indian state on conceptions of itself and its original borders as sacrosanct. But, the author argues that the state is, in reality, reshaped as a result of demands from linguistic and other groups of the dominant North Central Hindu/Indian populations, while demands from the periphery are ignored. The chapter examines how political elites deliberately entrenched the hegemonic beliefs about the state size after the partition, the centre's response to the challenges faced by Kashmir and Punjab to these beliefs, and various coalitions in favour and against reshaping of the Indian state.Less
Gurharpal Singh traces the institutional dependence of the Indian state on conceptions of itself and its original borders as sacrosanct. But, the author argues that the state is, in reality, reshaped as a result of demands from linguistic and other groups of the dominant North Central Hindu/Indian populations, while demands from the periphery are ignored. The chapter examines how political elites deliberately entrenched the hegemonic beliefs about the state size after the partition, the centre's response to the challenges faced by Kashmir and Punjab to these beliefs, and various coalitions in favour and against reshaping of the Indian state.
Andy Hector, Thomas Bell, John Connolly, John Finn, Jeremy Fox, Laura Kirwan, Michel Loreau, Jennie McLaren, Bernhard Schmid, and Alexandra Weigelt
- Published in print:
- 2009
- Published Online:
- September 2009
- ISBN:
- 9780199547951
- eISBN:
- 9780191720345
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199547951.003.0007
- Subject:
- Biology, Ecology, Biodiversity / Conservation Biology
Meta-analysis of the first generation of biodiversity experiments has revealed that there is a general positive relationship between diversity and ecosystem processes that is consistent across ...
More
Meta-analysis of the first generation of biodiversity experiments has revealed that there is a general positive relationship between diversity and ecosystem processes that is consistent across trophic groups and ecosystem types. However, the mechanisms generating these general patterns are still under debate. While there are unresolved conceptual issues about the nature of diversity and complementarity, the debate is partly due to the difficulty of performing a full-factorial analysis of the functional effects of all species in a diverse community. However, there are now several different analytical approaches that can address mechanisms even when full factorial analysis is not possible. This chapter presents an overview and users' guide to these methods. This chapter concludes that the current toolbox of methods allows investigation of the mechanisms for most, if not all, biodiversity and ecosystem functioning experiments conducted to date that manipulate species within a single trophic level (e.g. plant biodiversity experiments). Methods that can address mechanisms in multitrophic studies are a key need for future research.Less
Meta-analysis of the first generation of biodiversity experiments has revealed that there is a general positive relationship between diversity and ecosystem processes that is consistent across trophic groups and ecosystem types. However, the mechanisms generating these general patterns are still under debate. While there are unresolved conceptual issues about the nature of diversity and complementarity, the debate is partly due to the difficulty of performing a full-factorial analysis of the functional effects of all species in a diverse community. However, there are now several different analytical approaches that can address mechanisms even when full factorial analysis is not possible. This chapter presents an overview and users' guide to these methods. This chapter concludes that the current toolbox of methods allows investigation of the mechanisms for most, if not all, biodiversity and ecosystem functioning experiments conducted to date that manipulate species within a single trophic level (e.g. plant biodiversity experiments). Methods that can address mechanisms in multitrophic studies are a key need for future research.
Barbara Tversky, Jeffrey M. Zacks, and Bridgette Martin Hard
- Published in print:
- 2008
- Published Online:
- May 2008
- ISBN:
- 9780195188370
- eISBN:
- 9780199870462
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780195188370.003.0019
- Subject:
- Psychology, Cognitive Neuroscience
This chapter focuses on the structure of experience, covering language, objects, scenes, and events. It is argued that partitioning the world is the first step to comprehending it. Some partitioning ...
More
This chapter focuses on the structure of experience, covering language, objects, scenes, and events. It is argued that partitioning the world is the first step to comprehending it. Some partitioning is so instantaneous and automatic that perception of the world is not of multimedia mixtures of continuously changing sensations but rather of coherent objects, events, and scenes. The mind goes on to parse those elements and to look for structure among the parts. Typically there is a perceptual basis for part structure. Truly understanding each of these elements of our lives requires assigning meaning to their parts.Less
This chapter focuses on the structure of experience, covering language, objects, scenes, and events. It is argued that partitioning the world is the first step to comprehending it. Some partitioning is so instantaneous and automatic that perception of the world is not of multimedia mixtures of continuously changing sensations but rather of coherent objects, events, and scenes. The mind goes on to parse those elements and to look for structure among the parts. Typically there is a perceptual basis for part structure. Truly understanding each of these elements of our lives requires assigning meaning to their parts.
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.
Andrea Braides
- Published in print:
- 2002
- Published Online:
- September 2007
- ISBN:
- 9780198507840
- eISBN:
- 9780191709890
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198507840.003.0006
- Subject:
- Mathematics, Applied Mathematics
The study of segmentation problems, i.e., variational problems where the unknown is a piecewise-constant function, allows the introduction of a new type of weak convergence, related to the weak* ...
More
The study of segmentation problems, i.e., variational problems where the unknown is a piecewise-constant function, allows the introduction of a new type of weak convergence, related to the weak* convergence of measures, and the corresponding variational concepts. In particular, lower semicontinuity of segmentation functionals is proved to be equivalent to sub-additivity of integrands. Correspondingly, the notions of relaxation and Gamma-convergence can be expressed through suitable sub-additive envelopes. The theory of Caccioppoli partitions in higher dimension is outlined.Less
The study of segmentation problems, i.e., variational problems where the unknown is a piecewise-constant function, allows the introduction of a new type of weak convergence, related to the weak* convergence of measures, and the corresponding variational concepts. In particular, lower semicontinuity of segmentation functionals is proved to be equivalent to sub-additivity of integrands. Correspondingly, the notions of relaxation and Gamma-convergence can be expressed through suitable sub-additive envelopes. The theory of Caccioppoli partitions in higher dimension is outlined.
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.
Roman Kossak and James H. Schmerl
- Published in print:
- 2006
- Published Online:
- September 2007
- ISBN:
- 9780198568278
- eISBN:
- 9780191718199
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198568278.003.0004
- Subject:
- Mathematics, Logic / Computer Science / Mathematical Philosophy
This chapter examines substructure lattices, with emphasis on how to obtain models with specific finite lattices as substructure lattices. The finite distributive lattice case is presented in full. ...
More
This chapter examines substructure lattices, with emphasis on how to obtain models with specific finite lattices as substructure lattices. The finite distributive lattice case is presented in full. The general technique involving canonical partition properties using congruence lattices and theorems such as the Hales-Jewett theorem is described and applied. Wilkie's theorem for the pentagon lattice and Paris' theorem for all countable distributive lattices are also presented.Less
This chapter examines substructure lattices, with emphasis on how to obtain models with specific finite lattices as substructure lattices. The finite distributive lattice case is presented in full. The general technique involving canonical partition properties using congruence lattices and theorems such as the Hales-Jewett theorem is described and applied. Wilkie's theorem for the pentagon lattice and Paris' theorem for all countable distributive lattices are also presented.
