Mathew Penrose
- Published in print:
- 2003
- Published Online:
- September 2007
- ISBN:
- 9780198506263
- eISBN:
- 9780191707858
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198506263.001.0001
- Subject:
- Mathematics, Probability / Statistics
This book sets out a body of rigorous mathematical theory for finite graphs with nodes placed randomly in Euclidean d-space according to a common probability density, and edges added to connect ...
More
This book sets out a body of rigorous mathematical theory for finite graphs with nodes placed randomly in Euclidean d-space according to a common probability density, and edges added to connect points that are close to each other. As an alternative to classical random graph models, these geometric graphs are relevant to the modelling of real networks having spatial content, arising for example in wireless communications, parallel processing, classification, epidemiology, astronomy, and the internet. Their study illustrates numerous techniques of modern stochastic geometry, including Stein's method, martingale methods, and continuum percolation. Typical results in the book concern properties of a graph G on n random points with edges included for interpoint distances up to r, with the parameter r dependent on n and typically small for large n. Asymptotic distributional properties are derived for numerous graph quantities. These include the number of copies of a given finite graph embedded in G, the number of isolated components isomorphic to a given graph, the empirical distributions of vertex degrees, the clique number, the chromatic number, the maximum and minimum degree, the size of the largest component, the total number of components, and the connectivity of the graph.Less
This book sets out a body of rigorous mathematical theory for finite graphs with nodes placed randomly in Euclidean d-space according to a common probability density, and edges added to connect points that are close to each other. As an alternative to classical random graph models, these geometric graphs are relevant to the modelling of real networks having spatial content, arising for example in wireless communications, parallel processing, classification, epidemiology, astronomy, and the internet. Their study illustrates numerous techniques of modern stochastic geometry, including Stein's method, martingale methods, and continuum percolation. Typical results in the book concern properties of a graph G on n random points with edges included for interpoint distances up to r, with the parameter r dependent on n and typically small for large n. Asymptotic distributional properties are derived for numerous graph quantities. These include the number of copies of a given finite graph embedded in G, the number of isolated components isomorphic to a given graph, the empirical distributions of vertex degrees, the clique number, the chromatic number, the maximum and minimum degree, the size of the largest component, the total number of components, and the connectivity of the graph.
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.0002
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
This chapter focuses on certain basic constructions that occur frequently in the rest of the book, emphasizing the product and the retract, but also considering other constructs. These include the ...
More
This chapter focuses on certain basic constructions that occur frequently in the rest of the book, emphasizing the product and the retract, but also considering other constructs. These include the shift graph, the exponential graph, and the Lovász vector. Taken together, such constructions are the common thread and the leitmotiv of this book. The highlights of the sections on products include a linear algebra-based lower bound on the dimension of a graph; a stronger version of the edge reconstruction result from this chapter; a discussion of cancellation and unique factorization properties; a construction of graphs with arbitrarily high odd girth and chromatic number; an exploration of the Product Conjecture; and an elementary proof of the multiplicativity of oriented cycles of prime power length. The sections on retracts contain the proof that an isometric tree and a shortest cycle is always a retract of a reflexive graph; a similar result holds for shortest odd cycles in irreflexive nearly bipartite graphs. Absolute reflexive retracts are characterized in several different ways, including characterizations in terms of majority functions, the variety of paths, and the Helly property (or the absence of holes). A reflexive graph is shown to admit a winning strategy for the cop in the game of cops and robbers, if and only if it is dismantlable, and dismantlable graphs are related to absolute reflexive retracts. Finally, median graphs are introduced and related to retracts of hypercubes. An application of median graphs and retractions is given in a resource location problem.Less
This chapter focuses on certain basic constructions that occur frequently in the rest of the book, emphasizing the product and the retract, but also considering other constructs. These include the shift graph, the exponential graph, and the Lovász vector. Taken together, such constructions are the common thread and the leitmotiv of this book. The highlights of the sections on products include a linear algebra-based lower bound on the dimension of a graph; a stronger version of the edge reconstruction result from this chapter; a discussion of cancellation and unique factorization properties; a construction of graphs with arbitrarily high odd girth and chromatic number; an exploration of the Product Conjecture; and an elementary proof of the multiplicativity of oriented cycles of prime power length. The sections on retracts contain the proof that an isometric tree and a shortest cycle is always a retract of a reflexive graph; a similar result holds for shortest odd cycles in irreflexive nearly bipartite graphs. Absolute reflexive retracts are characterized in several different ways, including characterizations in terms of majority functions, the variety of paths, and the Helly property (or the absence of holes). A reflexive graph is shown to admit a winning strategy for the cop in the game of cops and robbers, if and only if it is dismantlable, and dismantlable graphs are related to absolute reflexive retracts. Finally, median graphs are introduced and related to retracts of hypercubes. An application of median graphs and retractions is given in a resource location problem.
Mathew Penrose
- Published in print:
- 2003
- Published Online:
- September 2007
- ISBN:
- 9780198506263
- eISBN:
- 9780191707858
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198506263.003.0006
- Subject:
- Mathematics, Probability / Statistics
This chapter is concerned with maximum degree, clique number, and chromatic number. A focusing (i.e., two-point concentration) phenomenon is demonstrated for the distribution of the maximum degree in ...
More
This chapter is concerned with maximum degree, clique number, and chromatic number. A focusing (i.e., two-point concentration) phenomenon is demonstrated for the distribution of the maximum degree in the subconnective regime, and likewise for clique number. Laws of large numbers are presented for maximum degree and clique number in the subconnective and connectivity regimes. For the chromatic number, a law of large numbers is presented in the subconnectivity regime, and bounds on its ratio to the clique number are given for the superconnective regime. These bounds are given in terms of packings of the unit ball.Less
This chapter is concerned with maximum degree, clique number, and chromatic number. A focusing (i.e., two-point concentration) phenomenon is demonstrated for the distribution of the maximum degree in the subconnective regime, and likewise for clique number. Laws of large numbers are presented for maximum degree and clique number in the subconnective and connectivity regimes. For the chromatic number, a law of large numbers is presented in the subconnectivity regime, and bounds on its ratio to the clique number are given for the superconnective regime. These bounds are given in terms of packings of the unit ball.
