Substructures in a graph can imply global consequences. We prove sufficient conditions for the abelian group of integral flows of a graph to admit a basis consisting only of flows with support equal to a Hamilton-circuit. As another example, we prove limit-laws for logical statements about graphs embedded on a surface, and we define a new measure on sets of sign-matrices whose precision in approximating another, better-known measure is controlled by circuits within an auxiliary graph.
Translated abstract:
Unterstrukturen eines Graphen können globale Konsequenzen nach sich ziehen. Wir beweisen Bedingungen dafür, dass die abelsche Gruppe aller Rundflüsse eine Basis aus Flüssen mit Hamiltonkreisträger gestattet. Außerdem beweisen wir Grenzwertsätze für logische Aussagen über Graphen auf einer Fläche, und wir definieren ein neues Maß auf Mengen von Vorzeichenmatrizen, das ein anderes, bekannteres Maß mit einer Güte approximiert, die von Kreisen in einem Hilfsgraphen geregelt wird.
Login
BibTeX