Pavol Hell and Jaroslav Nesetril
- Published in print:
- 2004
- Published Online:
- September 2007
- ISBN:
- 9780198528173
- eISBN:
- 9780191713644
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198528173.001.0001
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
Graph theory is now an established discipline but the study of graph homomorphisms has only recently begun to gain wide acceptance and interest. This text is devoted entirely to the subject, bringing ...
More
Graph theory is now an established discipline but the study of graph homomorphisms has only recently begun to gain wide acceptance and interest. This text is devoted entirely to the subject, bringing together the highlights of the theory and its many applications. It looks at areas such as graph reconstruction, products, fractional and circular colourings, and constraint satisfaction problems, and has applications in complexity theory, artificial intelligence, telecommunications, and statistical physics. It has a wide focus on algebraic, combinatorial, and algorithmic aspects of graph homomorphisms. A reference list and historical summaries extend the material explicitly discussed. The book contains exercises of varying difficulty. Hints or references are provided for the more difficult exercises.Less
Graph theory is now an established discipline but the study of graph homomorphisms has only recently begun to gain wide acceptance and interest. This text is devoted entirely to the subject, bringing together the highlights of the theory and its many applications. It looks at areas such as graph reconstruction, products, fractional and circular colourings, and constraint satisfaction problems, and has applications in complexity theory, artificial intelligence, telecommunications, and statistical physics. It has a wide focus on algebraic, combinatorial, and algorithmic aspects of graph homomorphisms. A reference list and historical summaries extend the material explicitly discussed. The book contains exercises of varying difficulty. Hints or references are provided for the more difficult exercises.
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.0009
- Subject:
- Mathematics, Logic / Computer Science / Mathematical Philosophy
This chapter shows two major results. One, due to Lascar, says that countable arithmetically saturated models of PA have sequences of generic automorphisms, and consequently have a small index ...
More
This chapter shows two major results. One, due to Lascar, says that countable arithmetically saturated models of PA have sequences of generic automorphisms, and consequently have a small index property. The other, from the authors of the book, states that the standard systems of countable arithmetically saturated models of PA are coded in their automorphism groups. Other results shown include proving a connection between the existence of automorphims with dense conjugacy classes and providing answers to some combinatorial questions concerning coloring of Cartesian products of digraphs; and a theorem saying that the cofinality of the automorphism group of a countable recursively saturated model of PA is uncountable if and only if the model is arithmetically saturated.Less
This chapter shows two major results. One, due to Lascar, says that countable arithmetically saturated models of PA have sequences of generic automorphisms, and consequently have a small index property. The other, from the authors of the book, states that the standard systems of countable arithmetically saturated models of PA are coded in their automorphism groups. Other results shown include proving a connection between the existence of automorphims with dense conjugacy classes and providing answers to some combinatorial questions concerning coloring of Cartesian products of digraphs; and a theorem saying that the cofinality of the automorphism group of a countable recursively saturated model of PA is uncountable if and only if the model is arithmetically saturated.
Demetrios D. Demopoulos and Moshe Y. Vardi
- Published in print:
- 2005
- Published Online:
- November 2020
- ISBN:
- 9780195177374
- eISBN:
- 9780197562260
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780195177374.003.0017
- Subject:
- Computer Science, Mathematical Theory of Computation
This chapter presents a study of the satisfiability of random Horn formulas and a search for a phase transition. In the past decade, phase transitions or ...
More
This chapter presents a study of the satisfiability of random Horn formulas and a search for a phase transition. In the past decade, phase transitions or sharp thresholds, have been studied intensively in combinatorial problems. Although the idea of thresholds in a combinatorial context was introduced as early as 1960 [147], in recent years it has been a major subject of research in the communities of theoretical computer science, artificial intelligence, and statistical physics. As is apparent throughout this volume, phase transitions have been observed in numerous combinatorial problems, both for the probability that an instance of a problem has a solution and for the computational cost of solving an instance. In a few cases (2-SAT, 3-XORSAT, 1-in-k SAT) the existence and location of these phase transitions have also been formally proven [7, 94, 101, 131, 156, 202]. The problem at the center of this research is that of 3-satisfiability (3-SAT). An instance of 3-SAT consists of a conjunction of clauses, where each clause is a disjunction of three literals. The goal is to find a truth assignment that satisfies all clauses. The density of a 3-S AT instance is the ratio of the number of clauses to the number of Boolean variables. We call the number of variables the size of the instance. Experimental studies [110, 395, 397, 466, 469] have shown that there is a shift in the probability of satisfiability of random 3-S AT instances, from 1 to 0, located at around density 4.27 (this is also called the crossover point}. So far, in spite of much progress in obtaining rigorous bounds on the threshold location, highlighted in the previous chapters, there is no mathematical proof of a phase transition taking place at that density [1, 132, 177]. Experimental studies also show a peak of the computational complexity around the crossover point. In Kirkpatrick and Selman [319], finite-size scaling techniques were used to suggest a phase transition at the crossover point. Later, in Coafra et al. [96], experiments showed that a phase transition of the running time from polynomial in the instance size to exponential is solver-dependent, and for several different solvers this transition occurs at a density lower than the crossover point.
Less
This chapter presents a study of the satisfiability of random Horn formulas and a search for a phase transition. In the past decade, phase transitions or sharp thresholds, have been studied intensively in combinatorial problems. Although the idea of thresholds in a combinatorial context was introduced as early as 1960 [147], in recent years it has been a major subject of research in the communities of theoretical computer science, artificial intelligence, and statistical physics. As is apparent throughout this volume, phase transitions have been observed in numerous combinatorial problems, both for the probability that an instance of a problem has a solution and for the computational cost of solving an instance. In a few cases (2-SAT, 3-XORSAT, 1-in-k SAT) the existence and location of these phase transitions have also been formally proven [7, 94, 101, 131, 156, 202]. The problem at the center of this research is that of 3-satisfiability (3-SAT). An instance of 3-SAT consists of a conjunction of clauses, where each clause is a disjunction of three literals. The goal is to find a truth assignment that satisfies all clauses. The density of a 3-S AT instance is the ratio of the number of clauses to the number of Boolean variables. We call the number of variables the size of the instance. Experimental studies [110, 395, 397, 466, 469] have shown that there is a shift in the probability of satisfiability of random 3-S AT instances, from 1 to 0, located at around density 4.27 (this is also called the crossover point}. So far, in spite of much progress in obtaining rigorous bounds on the threshold location, highlighted in the previous chapters, there is no mathematical proof of a phase transition taking place at that density [1, 132, 177]. Experimental studies also show a peak of the computational complexity around the crossover point. In Kirkpatrick and Selman [319], finite-size scaling techniques were used to suggest a phase transition at the crossover point. Later, in Coafra et al. [96], experiments showed that a phase transition of the running time from polynomial in the instance size to exponential is solver-dependent, and for several different solvers this transition occurs at a density lower than the crossover point.
Rebecca Treiman and Brett Kessler
- Published in print:
- 2014
- Published Online:
- December 2014
- ISBN:
- 9780199907977
- eISBN:
- 9780190228422
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199907977.003.0011
- Subject:
- Psychology, Developmental Psychology, Cognitive Psychology
This chapter discusses how children deal with the complexities in alphabetic writing systems. Many such systems include conditioned rules: One spelling of a phoneme is likely to occur in certain ...
More
This chapter discusses how children deal with the complexities in alphabetic writing systems. Many such systems include conditioned rules: One spelling of a phoneme is likely to occur in certain contexts and another spelling is more likely in other contexts. The chapter reviews research on how children learn about different types of conditioning. For example, it examines how the choice among potential spellings for a vowel is affected by the consonants in the syllable’s onset or coda or by the stress of the syllable and whether rhymes have a special status. Research shows that spellers have more difficulty in cases in which appeals to context don’t help—unconditioned inconsistencies—than with conditioned spellings. The chapter also considers how children consider morphology in deciding among possible spellings and how they deal with digraphs (two-letter spellings) and homography (cases in which a spelling represents more than one phoneme).Less
This chapter discusses how children deal with the complexities in alphabetic writing systems. Many such systems include conditioned rules: One spelling of a phoneme is likely to occur in certain contexts and another spelling is more likely in other contexts. The chapter reviews research on how children learn about different types of conditioning. For example, it examines how the choice among potential spellings for a vowel is affected by the consonants in the syllable’s onset or coda or by the stress of the syllable and whether rhymes have a special status. Research shows that spellers have more difficulty in cases in which appeals to context don’t help—unconditioned inconsistencies—than with conditioned spellings. The chapter also considers how children consider morphology in deciding among possible spellings and how they deal with digraphs (two-letter spellings) and homography (cases in which a spelling represents more than one phoneme).