Randomly Coloring Regular Bipartite Graphs and Graphs with Bounded Common Neighbors View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2012

AUTHORS

Ching-Chen Kuo , Hsueh-I Lu

ABSTRACT

Let G be an n-node graph with maximum degree Δ. The Glauber dynamics for G, defined by Jerrum, is a Markov chain over the k-colorings of G. Many classes of G on which the Glauber dynamics mixes rapidly have been identified. Recent research efforts focus on the important case that Δ ≥ dlog2n holds for some sufficiently large constant d. We add the following new results along this direction, where ε can be any constant with 0 < ε < 1. Let α ≈ 1.645 be the root of (1 − e− 1/x)2 + 2xe− 1/x = 2. If G is regular and bipartite and k ≥ (α + ε)Δ, then the mixing time of the Glauber dynamics for G is O(nlogn).Let β ≈ 1.763 be the root of x = e1/x. If the number of common neighbors for any two adjacent nodes of G is at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{\epsilon^{1.5}\Delta}{360e}$\end{document} and k ≥ (1 + ε)βΔ, then the mixing time of the Glauber dynamics is O(nlogn). More... »

PAGES

24-33

Book

TITLE

Algorithms and Computation

ISBN

978-3-642-35260-7
978-3-642-35261-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-35261-4_6

DOI

http://dx.doi.org/10.1007/978-3-642-35261-4_6

DIMENSIONS

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


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": "Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kuo", 
        "givenName": "Ching-Chen", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lu", 
        "givenName": "Hsueh-I", 
        "id": "sg:person.013345515575.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2012", 
    "datePublishedReg": "2012-01-01", 
    "description": "Let G be an n-node graph with maximum degree \u0394. The Glauber dynamics for G, defined by Jerrum, is a Markov chain over the k-colorings of G. Many classes of G on which the Glauber dynamics mixes rapidly have been identified. Recent research efforts focus on the important case that \u0394\u2009\u2265\u2009dlog2n holds for some sufficiently large constant d. We add the following new results along this direction, where \u03b5 can be any constant with 0\u2009<\u2009\u03b5\u2009<\u20091. \nLet \u03b1\u2009\u2248\u20091.645 be the root of (1\u2009\u2212\u2009e\u2212\u20091/x)2\u2009+\u20092xe\u2212\u20091/x\u2009=\u20092. If G is regular and bipartite and k\u2009\u2265\u2009(\u03b1\u2009+\u2009\u03b5)\u0394, then the mixing time of the Glauber dynamics for G is O(nlogn).Let \u03b2\u2009\u2248\u20091.763 be the root of x\u2009=\u2009e1/x. If the number of common neighbors for any two adjacent nodes of G is at most \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\frac{\\epsilon^{1.5}\\Delta}{360e}$\\end{document} and k\u2009\u2265\u2009(1\u2009+\u2009\u03b5)\u03b2\u0394, then the mixing time of the Glauber dynamics is O(nlogn).", 
    "editor": [
      {
        "familyName": "Chao", 
        "givenName": "Kun-Mao", 
        "type": "Person"
      }, 
      {
        "familyName": "Hsu", 
        "givenName": "Tsan-sheng", 
        "type": "Person"
      }, 
      {
        "familyName": "Lee", 
        "givenName": "Der-Tsai", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-35261-4_6", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-35260-7", 
        "978-3-642-35261-4"
      ], 
      "name": "Algorithms and Computation", 
      "type": "Book"
    }, 
    "keywords": [
      "Glauber dynamics", 
      "maximum degree \u0394.", 
      "degree \u0394.", 
      "Markov chain", 
      "important case", 
      "new results", 
      "common neighbors", 
      "regular bipartite graphs", 
      "bipartite graphs", 
      "node graph", 
      "graph", 
      "dynamics", 
      "Jerrum", 
      "coloring", 
      "adjacent nodes", 
      "class", 
      "dynamic mix", 
      "recent research efforts", 
      "research efforts", 
      "direction", 
      "time", 
      "number", 
      "neighbors", 
      "nodes", 
      "chain", 
      "mix", 
      "efforts", 
      "cases", 
      "results", 
      "roots"
    ], 
    "name": "Randomly Coloring Regular Bipartite Graphs and Graphs with Bounded Common Neighbors", 
    "pagination": "24-33", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1040969283"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-35261-4_6"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-35261-4_6", 
      "https://app.dimensions.ai/details/publication/pub.1040969283"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:47", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_336.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-35261-4_6"
  }
]
 

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/978-3-642-35261-4_6'

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/978-3-642-35261-4_6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-35261-4_6'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-35261-4_6'


 

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

106 TRIPLES      23 PREDICATES      56 URIs      49 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-35261-4_6 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N31d9d61a7a9648a5bd3c2950279475e7
4 schema:datePublished 2012
5 schema:datePublishedReg 2012-01-01
6 schema:description Let G be an n-node graph with maximum degree Δ. The Glauber dynamics for G, defined by Jerrum, is a Markov chain over the k-colorings of G. Many classes of G on which the Glauber dynamics mixes rapidly have been identified. Recent research efforts focus on the important case that Δ ≥ dlog2n holds for some sufficiently large constant d. We add the following new results along this direction, where ε can be any constant with 0 < ε < 1. Let α ≈ 1.645 be the root of (1 − e− 1/x)2 + 2xe− 1/x = 2. If G is regular and bipartite and k ≥ (α + ε)Δ, then the mixing time of the Glauber dynamics for G is O(nlogn).Let β ≈ 1.763 be the root of x = e1/x. If the number of common neighbors for any two adjacent nodes of G is at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{\epsilon^{1.5}\Delta}{360e}$\end{document} and k ≥ (1 + ε)βΔ, then the mixing time of the Glauber dynamics is O(nlogn).
7 schema:editor N68793c181b1143c0be2d99dbd62f8a15
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N0e75da5101a84470805837795c9dbf87
12 schema:keywords Glauber dynamics
13 Jerrum
14 Markov chain
15 adjacent nodes
16 bipartite graphs
17 cases
18 chain
19 class
20 coloring
21 common neighbors
22 degree Δ.
23 direction
24 dynamic mix
25 dynamics
26 efforts
27 graph
28 important case
29 maximum degree Δ.
30 mix
31 neighbors
32 new results
33 node graph
34 nodes
35 number
36 recent research efforts
37 regular bipartite graphs
38 research efforts
39 results
40 roots
41 time
42 schema:name Randomly Coloring Regular Bipartite Graphs and Graphs with Bounded Common Neighbors
43 schema:pagination 24-33
44 schema:productId N310fe3324ca446258379f8f56ff08ce3
45 Nb3f374e57d94479d9ad8c616c9e0e392
46 schema:publisher Ncc73f30a8d4b4186b73f32b05b4ced49
47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040969283
48 https://doi.org/10.1007/978-3-642-35261-4_6
49 schema:sdDatePublished 2022-05-10T10:47
50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
51 schema:sdPublisher Nf7bffa162937410e90ef0450dc6500ad
52 schema:url https://doi.org/10.1007/978-3-642-35261-4_6
53 sgo:license sg:explorer/license/
54 sgo:sdDataset chapters
55 rdf:type schema:Chapter
56 N0e75da5101a84470805837795c9dbf87 schema:isbn 978-3-642-35260-7
57 978-3-642-35261-4
58 schema:name Algorithms and Computation
59 rdf:type schema:Book
60 N27499ff98bd14e789f37753f2d1f7020 schema:familyName Lee
61 schema:givenName Der-Tsai
62 rdf:type schema:Person
63 N310fe3324ca446258379f8f56ff08ce3 schema:name doi
64 schema:value 10.1007/978-3-642-35261-4_6
65 rdf:type schema:PropertyValue
66 N31d9d61a7a9648a5bd3c2950279475e7 rdf:first Nd7f2632d17324bc082a1d0ad02d3fa8e
67 rdf:rest Ne1310592e95543b780d4ee90dc204dc4
68 N4142821df67740d2a9a01d0b9215894d rdf:first N27499ff98bd14e789f37753f2d1f7020
69 rdf:rest rdf:nil
70 N68793c181b1143c0be2d99dbd62f8a15 rdf:first Nd3434405bc644804a1f6948266007f6f
71 rdf:rest N6d45abd3fed1493bac04c4e7b5427f42
72 N6d45abd3fed1493bac04c4e7b5427f42 rdf:first N8e269d8d451644f8a8d8973aed94f094
73 rdf:rest N4142821df67740d2a9a01d0b9215894d
74 N8e269d8d451644f8a8d8973aed94f094 schema:familyName Hsu
75 schema:givenName Tsan-sheng
76 rdf:type schema:Person
77 Nb3f374e57d94479d9ad8c616c9e0e392 schema:name dimensions_id
78 schema:value pub.1040969283
79 rdf:type schema:PropertyValue
80 Ncc73f30a8d4b4186b73f32b05b4ced49 schema:name Springer Nature
81 rdf:type schema:Organisation
82 Nd3434405bc644804a1f6948266007f6f schema:familyName Chao
83 schema:givenName Kun-Mao
84 rdf:type schema:Person
85 Nd7f2632d17324bc082a1d0ad02d3fa8e schema:affiliation grid-institutes:grid.19188.39
86 schema:familyName Kuo
87 schema:givenName Ching-Chen
88 rdf:type schema:Person
89 Ne1310592e95543b780d4ee90dc204dc4 rdf:first sg:person.013345515575.46
90 rdf:rest rdf:nil
91 Nf7bffa162937410e90ef0450dc6500ad schema:name Springer Nature - SN SciGraph project
92 rdf:type schema:Organization
93 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
94 schema:name Mathematical Sciences
95 rdf:type schema:DefinedTerm
96 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
97 schema:name Pure Mathematics
98 rdf:type schema:DefinedTerm
99 sg:person.013345515575.46 schema:affiliation grid-institutes:grid.19188.39
100 schema:familyName Lu
101 schema:givenName Hsueh-I
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
103 rdf:type schema:Person
104 grid-institutes:grid.19188.39 schema:alternateName Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan
105 schema:name Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan
106 rdf:type schema:Organization
 




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


...