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.
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).
