Note on forcing pairs

Link:
Autor/in:
Erscheinungsjahr:
2011
Medientyp:
Text
Schlagworte:
  • Chung-Graham-Wilson theorem
  • Forcing pairs
  • Quasi-random graphs
Beschreibung:
  • The notion of forcing pairs is located in the study of quasi-random graphs. Roughly speaking, a pair of graphs (F, F') is called forcing if the following holds: suppose for a sequence of graphs (Gn) there is a p>0 such that the number of copies of F and the number of copies of F' in every graph Gn of the sequence (Gn) is approximately the same as the expected value in the random graph G(n, p), then the sequence of graphs (Gn) is quasi-random in the sense of Chung, Graham and Wilson. We describe a construction which, given any graph F with at least one edge, yields a graph F' such that (F, F') forms a forcing pair. © 2011 Elsevier B.V.
Lizenz:
  • info:eu-repo/semantics/restrictedAccess
Quellsystem:
Forschungsinformationssystem der UHH
Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/124a7aba-d932-47b0-a592-355302be78d1