Path Coupling Using Stopping Times View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2005

AUTHORS

Magnus Bordewich , Martin Dyer , Marek Karpinski

ABSTRACT

We analyse the mixing time of Markov chains using path coupling with stopping times. We apply this approach to two hypergraph problems. We show that the Glauber dynamics for independent sets in a hypergraph mixes rapidly as long as the maximum degree Δ of a vertex and the minimum size m of an edge satisfy m ≥ 2Δ +1. We also state results that the Glauber dynamics for proper q-colourings of a hypergraph mixes rapidly if m ≥ 4 and q > Δ, and if m = 3 and q ≥1.65Δ. We give related results on the hardness of exact and approximate counting for both problems. More... »

PAGES

19-31

Book

TITLE

Fundamentals of Computation Theory

ISBN

978-3-540-28193-1
978-3-540-31873-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11537311_3

DOI

http://dx.doi.org/10.1007/11537311_3

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1044558525


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "School of Computing, University of Leeds, LS2 9JT, Leeds, UK", 
          "id": "http://www.grid.ac/institutes/grid.9909.9", 
          "name": [
            "School of Computing, University of Leeds, LS2 9JT, Leeds, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bordewich", 
        "givenName": "Magnus", 
        "id": "sg:person.07664237516.14", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07664237516.14"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "School of Computing, University of Leeds, LS2 9JT, Leeds, UK", 
          "id": "http://www.grid.ac/institutes/grid.9909.9", 
          "name": [
            "School of Computing, University of Leeds, LS2 9JT, Leeds, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dyer", 
        "givenName": "Martin", 
        "id": "sg:person.010610754257.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010610754257.21"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science, University of Bonn, 53117, Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Dept. of Computer Science, University of Bonn, 53117, Bonn, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karpinski", 
        "givenName": "Marek", 
        "id": "sg:person.011636042271.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "We analyse the mixing time of Markov chains using path coupling with stopping times. We apply this approach to two hypergraph problems. We show that the Glauber dynamics for independent sets in a hypergraph mixes rapidly as long as the maximum degree \u0394 of a vertex and the minimum size m of an edge satisfy m \u2265 2\u0394 +1. We also state results that the Glauber dynamics for proper q-colourings of a hypergraph mixes rapidly if m \u2265 4 and q > \u0394, and if m = 3 and q \u22651.65\u0394. We give related results on the hardness of exact and approximate counting for both problems.", 
    "editor": [
      {
        "familyName": "Li\u015bkiewicz", 
        "givenName": "Maciej", 
        "type": "Person"
      }, 
      {
        "familyName": "Reischuk", 
        "givenName": "R\u00fcdiger", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11537311_3", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-28193-1", 
        "978-3-540-31873-6"
      ], 
      "name": "Fundamentals of Computation Theory", 
      "type": "Book"
    }, 
    "keywords": [
      "Glauber dynamics", 
      "proper q-colorings", 
      "path coupling", 
      "maximum degree \u0394", 
      "q-colorings", 
      "stopping time", 
      "Markov chain", 
      "approximate counting", 
      "hypergraph problems", 
      "related results", 
      "degree \u0394", 
      "independent set", 
      "edges satisfies", 
      "minimum size", 
      "dynamics", 
      "problem", 
      "coupling", 
      "vertices", 
      "satisfies", 
      "hypergraphs", 
      "set", 
      "results", 
      "approach", 
      "time", 
      "chain", 
      "size", 
      "counting", 
      "mix", 
      "hardness"
    ], 
    "name": "Path Coupling Using Stopping Times", 
    "pagination": "19-31", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1044558525"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11537311_3"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11537311_3", 
      "https://app.dimensions.ai/details/publication/pub.1044558525"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:46", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_123.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11537311_3"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/11537311_3'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/11537311_3'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11537311_3'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11537311_3'


 

This table displays all metadata directly associated to this object as RDF triples.

110 TRIPLES      22 PREDICATES      54 URIs      47 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11537311_3 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N710d8737a03e487a857ea7bc11902fb5
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 schema:description We analyse the mixing time of Markov chains using path coupling with stopping times. We apply this approach to two hypergraph problems. We show that the Glauber dynamics for independent sets in a hypergraph mixes rapidly as long as the maximum degree Δ of a vertex and the minimum size m of an edge satisfy m ≥ 2Δ +1. We also state results that the Glauber dynamics for proper q-colourings of a hypergraph mixes rapidly if m ≥ 4 and q > Δ, and if m = 3 and q ≥1.65Δ. We give related results on the hardness of exact and approximate counting for both problems.
7 schema:editor N5e8c76c7755644afb3fcd59fcf84caeb
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nb827e158e2104b89abf3bb943448a32f
11 schema:keywords Glauber dynamics
12 Markov chain
13 approach
14 approximate counting
15 chain
16 counting
17 coupling
18 degree Δ
19 dynamics
20 edges satisfies
21 hardness
22 hypergraph problems
23 hypergraphs
24 independent set
25 maximum degree Δ
26 minimum size
27 mix
28 path coupling
29 problem
30 proper q-colorings
31 q-colorings
32 related results
33 results
34 satisfies
35 set
36 size
37 stopping time
38 time
39 vertices
40 schema:name Path Coupling Using Stopping Times
41 schema:pagination 19-31
42 schema:productId N185cde0fb2cf4d478aa1c344d42348ab
43 Ne0c59e3d7e9a4752918d8a0fab8f1f91
44 schema:publisher Nd1f54dfce578411a8f17b009f02de72a
45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044558525
46 https://doi.org/10.1007/11537311_3
47 schema:sdDatePublished 2022-12-01T06:46
48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
49 schema:sdPublisher Nb0ca8d1dca7d4bc8bd2ad230ca3c5a81
50 schema:url https://doi.org/10.1007/11537311_3
51 sgo:license sg:explorer/license/
52 sgo:sdDataset chapters
53 rdf:type schema:Chapter
54 N185cde0fb2cf4d478aa1c344d42348ab schema:name doi
55 schema:value 10.1007/11537311_3
56 rdf:type schema:PropertyValue
57 N3cd1d625d86941f3b21144b5415dc890 rdf:first sg:person.011636042271.02
58 rdf:rest rdf:nil
59 N48eba935c59e4f1c846b86aeb1d366f2 rdf:first sg:person.010610754257.21
60 rdf:rest N3cd1d625d86941f3b21144b5415dc890
61 N5a042e8d1bb042deb4942d716b7db52a schema:familyName Reischuk
62 schema:givenName Rüdiger
63 rdf:type schema:Person
64 N5e8c76c7755644afb3fcd59fcf84caeb rdf:first Ne8c63de8915949c7bd12ef1bdde66ccc
65 rdf:rest Nfa12cf08a33f49dc8eedcb03b2ce3e4b
66 N710d8737a03e487a857ea7bc11902fb5 rdf:first sg:person.07664237516.14
67 rdf:rest N48eba935c59e4f1c846b86aeb1d366f2
68 Nb0ca8d1dca7d4bc8bd2ad230ca3c5a81 schema:name Springer Nature - SN SciGraph project
69 rdf:type schema:Organization
70 Nb827e158e2104b89abf3bb943448a32f schema:isbn 978-3-540-28193-1
71 978-3-540-31873-6
72 schema:name Fundamentals of Computation Theory
73 rdf:type schema:Book
74 Nd1f54dfce578411a8f17b009f02de72a schema:name Springer Nature
75 rdf:type schema:Organisation
76 Ne0c59e3d7e9a4752918d8a0fab8f1f91 schema:name dimensions_id
77 schema:value pub.1044558525
78 rdf:type schema:PropertyValue
79 Ne8c63de8915949c7bd12ef1bdde66ccc schema:familyName Liśkiewicz
80 schema:givenName Maciej
81 rdf:type schema:Person
82 Nfa12cf08a33f49dc8eedcb03b2ce3e4b rdf:first N5a042e8d1bb042deb4942d716b7db52a
83 rdf:rest rdf:nil
84 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
85 schema:name Mathematical Sciences
86 rdf:type schema:DefinedTerm
87 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
88 schema:name Pure Mathematics
89 rdf:type schema:DefinedTerm
90 sg:person.010610754257.21 schema:affiliation grid-institutes:grid.9909.9
91 schema:familyName Dyer
92 schema:givenName Martin
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010610754257.21
94 rdf:type schema:Person
95 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
96 schema:familyName Karpinski
97 schema:givenName Marek
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
99 rdf:type schema:Person
100 sg:person.07664237516.14 schema:affiliation grid-institutes:grid.9909.9
101 schema:familyName Bordewich
102 schema:givenName Magnus
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07664237516.14
104 rdf:type schema:Person
105 grid-institutes:grid.10388.32 schema:alternateName Dept. of Computer Science, University of Bonn, 53117, Bonn, Germany
106 schema:name Dept. of Computer Science, University of Bonn, 53117, Bonn, Germany
107 rdf:type schema:Organization
108 grid-institutes:grid.9909.9 schema:alternateName School of Computing, University of Leeds, LS2 9JT, Leeds, UK
109 schema:name School of Computing, University of Leeds, LS2 9JT, Leeds, UK
110 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...