Improved mixing condition on the grid for counting and sampling independent sets
ABSTRACT: The hard-core model has received much attention in the past couple of decades as a lattice gas model with hard constraints in statistical physics, a multicast model of calls in communication networks, and as a weighted independent set problem in combinatorics, probability and theoretical c...
- Autores:
-
Restrepo López, Ricardo
Shin, Jinwoo
Tetali, Prasad
Vigoda, Eric
Yang, Linji
- Tipo de recurso:
- Article of investigation
- Fecha de publicación:
- 2013
- Institución:
- Universidad de Antioquia
- Repositorio:
- Repositorio UdeA
- Idioma:
- eng
- OAI Identifier:
- oai:bibliotecadigital.udea.edu.co:10495/35215
- Acceso en línea:
- https://hdl.handle.net/10495/35215
- Palabra clave:
- Física estadística
Statistical physics
- Rights
- openAccess
- License
- http://creativecommons.org/licenses/by/2.5/co/
| id |
UDEA2_b2af8a704b9f174ccf21279b87e8bc9b |
|---|---|
| oai_identifier_str |
oai:bibliotecadigital.udea.edu.co:10495/35215 |
| network_acronym_str |
UDEA2 |
| network_name_str |
Repositorio UdeA |
| repository_id_str |
|
| dc.title.spa.fl_str_mv |
Improved mixing condition on the grid for counting and sampling independent sets |
| title |
Improved mixing condition on the grid for counting and sampling independent sets |
| spellingShingle |
Improved mixing condition on the grid for counting and sampling independent sets Física estadística Statistical physics |
| title_short |
Improved mixing condition on the grid for counting and sampling independent sets |
| title_full |
Improved mixing condition on the grid for counting and sampling independent sets |
| title_fullStr |
Improved mixing condition on the grid for counting and sampling independent sets |
| title_full_unstemmed |
Improved mixing condition on the grid for counting and sampling independent sets |
| title_sort |
Improved mixing condition on the grid for counting and sampling independent sets |
| dc.creator.fl_str_mv |
Restrepo López, Ricardo Shin, Jinwoo Tetali, Prasad Vigoda, Eric Yang, Linji |
| dc.contributor.author.none.fl_str_mv |
Restrepo López, Ricardo Shin, Jinwoo Tetali, Prasad Vigoda, Eric Yang, Linji |
| dc.contributor.researchgroup.spa.fl_str_mv |
Análisis Numérico y Financiero: Matemáticas aplicadas para la industria |
| dc.subject.lemb.none.fl_str_mv |
Física estadística Statistical physics |
| topic |
Física estadística Statistical physics |
| description |
ABSTRACT: The hard-core model has received much attention in the past couple of decades as a lattice gas model with hard constraints in statistical physics, a multicast model of calls in communication networks, and as a weighted independent set problem in combinatorics, probability and theoretical computer science. In this model, each independent set I in a graph G is weighted proportionally to λ|I|, for a positive real parameter λ. For large λ, computing the partition function (namely, the normalizing constant which makes the weighting a probability distribution on a finite graph) on graphs of maximum degree ≥ 3, is a well known computationally challenging problem. More concretely, let λc(T) denote the critical value for the so-called uniqueness |
| publishDate |
2013 |
| dc.date.issued.none.fl_str_mv |
2013 |
| dc.date.accessioned.none.fl_str_mv |
2023-06-01T12:53:27Z |
| dc.date.available.none.fl_str_mv |
2023-06-01T12:53:27Z |
| dc.type.spa.fl_str_mv |
Artículo de investigación |
| dc.type.coar.spa.fl_str_mv |
http://purl.org/coar/resource_type/c_2df8fbb1 |
| dc.type.redcol.spa.fl_str_mv |
https://purl.org/redcol/resource_type/ART |
| dc.type.coarversion.spa.fl_str_mv |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |
| dc.type.driver.spa.fl_str_mv |
info:eu-repo/semantics/article |
| dc.type.version.spa.fl_str_mv |
info:eu-repo/semantics/publishedVersion |
| format |
http://purl.org/coar/resource_type/c_2df8fbb1 |
| status_str |
publishedVersion |
| dc.identifier.citation.spa.fl_str_mv |
Restrepo, R., Shin, J., Tetali, P. et al. Improved mixing condition on the grid for counting and sampling independent sets. Probab. Theory Relat. Fields 156, 75–99 (2013). https://doi.org/10.1007/s00440-012-0421-8 |
| dc.identifier.issn.none.fl_str_mv |
0178-8051 |
| dc.identifier.uri.none.fl_str_mv |
https://hdl.handle.net/10495/35215 |
| dc.identifier.doi.none.fl_str_mv |
10.1007/s00440-012-0421-8 |
| dc.identifier.eissn.none.fl_str_mv |
1432-2064 |
| identifier_str_mv |
Restrepo, R., Shin, J., Tetali, P. et al. Improved mixing condition on the grid for counting and sampling independent sets. Probab. Theory Relat. Fields 156, 75–99 (2013). https://doi.org/10.1007/s00440-012-0421-8 0178-8051 10.1007/s00440-012-0421-8 1432-2064 |
| url |
https://hdl.handle.net/10495/35215 |
| dc.language.iso.spa.fl_str_mv |
eng |
| language |
eng |
| dc.relation.ispartofjournalabbrev.spa.fl_str_mv |
Probab. Theory. Relat. Fields. |
| dc.relation.citationendpage.spa.fl_str_mv |
99 |
| dc.relation.citationissue.spa.fl_str_mv |
1-2 |
| dc.relation.citationstartpage.spa.fl_str_mv |
75 |
| dc.relation.citationvolume.spa.fl_str_mv |
156 |
| dc.relation.ispartofjournal.spa.fl_str_mv |
Probability Theory and Related Fields |
| dc.rights.uri.*.fl_str_mv |
http://creativecommons.org/licenses/by/2.5/co/ |
| dc.rights.uri.spa.fl_str_mv |
https://creativecommons.org/licenses/by/4.0/ |
| dc.rights.accessrights.spa.fl_str_mv |
info:eu-repo/semantics/openAccess |
| dc.rights.coar.spa.fl_str_mv |
http://purl.org/coar/access_right/c_abf2 |
| rights_invalid_str_mv |
http://creativecommons.org/licenses/by/2.5/co/ https://creativecommons.org/licenses/by/4.0/ http://purl.org/coar/access_right/c_abf2 |
| eu_rights_str_mv |
openAccess |
| dc.format.extent.spa.fl_str_mv |
25 |
| dc.format.mimetype.spa.fl_str_mv |
application/pdf |
| dc.publisher.spa.fl_str_mv |
Springer Institute of Mathematical Statistics |
| dc.publisher.place.spa.fl_str_mv |
Berlín, Alemania |
| institution |
Universidad de Antioquia |
| bitstream.url.fl_str_mv |
https://bibliotecadigital.udea.edu.co/bitstreams/7e6acae9-325b-4b3c-8321-ce3652c803c5/download https://bibliotecadigital.udea.edu.co/bitstreams/6703a73b-388d-4875-af37-74115618efc9/download https://bibliotecadigital.udea.edu.co/bitstreams/543cf4e4-944c-4855-9873-7ceef082badd/download https://bibliotecadigital.udea.edu.co/bitstreams/7b2390ec-a67d-42fb-9660-7bf34b2be5e0/download https://bibliotecadigital.udea.edu.co/bitstreams/a6a45526-36e1-477c-aebb-789586d266d6/download |
| bitstream.checksum.fl_str_mv |
1646d1f6b96dbbbc38035efc9239ac9c 8a4605be74aa9ea9d79846c1fba20a33 307d741714db5218ccfa3323917967d1 419d4ee328171405b670eb06a104ce9b 13b9b8171472c204752f40bc812635cb |
| bitstream.checksumAlgorithm.fl_str_mv |
MD5 MD5 MD5 MD5 MD5 |
| repository.name.fl_str_mv |
Repositorio Institucional de la Universidad de Antioquia |
| repository.mail.fl_str_mv |
aplicacionbibliotecadigitalbiblioteca@udea.edu.co |
| _version_ |
1851052442775453696 |
| spelling |
Restrepo López, RicardoShin, JinwooTetali, PrasadVigoda, EricYang, LinjiAnálisis Numérico y Financiero: Matemáticas aplicadas para la industria2023-06-01T12:53:27Z2023-06-01T12:53:27Z2013Restrepo, R., Shin, J., Tetali, P. et al. Improved mixing condition on the grid for counting and sampling independent sets. Probab. Theory Relat. Fields 156, 75–99 (2013). https://doi.org/10.1007/s00440-012-0421-80178-8051https://hdl.handle.net/10495/3521510.1007/s00440-012-0421-81432-2064ABSTRACT: The hard-core model has received much attention in the past couple of decades as a lattice gas model with hard constraints in statistical physics, a multicast model of calls in communication networks, and as a weighted independent set problem in combinatorics, probability and theoretical computer science. In this model, each independent set I in a graph G is weighted proportionally to λ|I|, for a positive real parameter λ. For large λ, computing the partition function (namely, the normalizing constant which makes the weighting a probability distribution on a finite graph) on graphs of maximum degree ≥ 3, is a well known computationally challenging problem. More concretely, let λc(T) denote the critical value for the so-called uniquenessCOL010637125application/pdfengSpringerInstitute of Mathematical StatisticsBerlín, Alemaniahttp://creativecommons.org/licenses/by/2.5/co/https://creativecommons.org/licenses/by/4.0/info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2Improved mixing condition on the grid for counting and sampling independent setsArtículo de investigaciónhttp://purl.org/coar/resource_type/c_2df8fbb1https://purl.org/redcol/resource_type/ARThttp://purl.org/coar/version/c_970fb48d4fbd8a85info:eu-repo/semantics/articleinfo:eu-repo/semantics/publishedVersionFísica estadísticaStatistical physicsProbab. Theory. Relat. Fields.991-275156Probability Theory and Related FieldsPublicationCC-LICENSElicense_rdflicense_rdfapplication/rdf+xml; charset=utf-8927https://bibliotecadigital.udea.edu.co/bitstreams/7e6acae9-325b-4b3c-8321-ce3652c803c5/download1646d1f6b96dbbbc38035efc9239ac9cMD52falseAnonymousREADLICENSElicense.txtlicense.txttext/plain; charset=utf-81748https://bibliotecadigital.udea.edu.co/bitstreams/6703a73b-388d-4875-af37-74115618efc9/download8a4605be74aa9ea9d79846c1fba20a33MD53falseAnonymousREADORIGINALRestrepoRicardo_2013_IndependentSets.pdfRestrepoRicardo_2013_IndependentSets.pdfArtículo de investigaciónapplication/pdf528884https://bibliotecadigital.udea.edu.co/bitstreams/543cf4e4-944c-4855-9873-7ceef082badd/download307d741714db5218ccfa3323917967d1MD54trueAnonymousREADTEXTRestrepoRicardo_2013_IndependentSets.pdf.txtRestrepoRicardo_2013_IndependentSets.pdf.txtExtracted texttext/plain61393https://bibliotecadigital.udea.edu.co/bitstreams/7b2390ec-a67d-42fb-9660-7bf34b2be5e0/download419d4ee328171405b670eb06a104ce9bMD55falseAnonymousREADTHUMBNAILRestrepoRicardo_2013_IndependentSets.pdf.jpgRestrepoRicardo_2013_IndependentSets.pdf.jpgGenerated Thumbnailimage/jpeg10806https://bibliotecadigital.udea.edu.co/bitstreams/a6a45526-36e1-477c-aebb-789586d266d6/download13b9b8171472c204752f40bc812635cbMD56falseAnonymousREAD10495/35215oai:bibliotecadigital.udea.edu.co:10495/352152025-03-26 22:26:05.248http://creativecommons.org/licenses/by/2.5/co/open.accesshttps://bibliotecadigital.udea.edu.coRepositorio Institucional de la Universidad de Antioquiaaplicacionbibliotecadigitalbiblioteca@udea.edu.coTk9URTogUExBQ0UgWU9VUiBPV04gTElDRU5TRSBIRVJFClRoaXMgc2FtcGxlIGxpY2Vuc2UgaXMgcHJvdmlkZWQgZm9yIGluZm9ybWF0aW9uYWwgcHVycG9zZXMgb25seS4KCk5PTi1FWENMVVNJVkUgRElTVFJJQlVUSU9OIExJQ0VOU0UKCkJ5IHNpZ25pbmcgYW5kIHN1Ym1pdHRpbmcgdGhpcyBsaWNlbnNlLCB5b3UgKHRoZSBhdXRob3Iocykgb3IgY29weXJpZ2h0Cm93bmVyKSBncmFudHMgdG8gRFNwYWNlIFVuaXZlcnNpdHkgKERTVSkgdGhlIG5vbi1leGNsdXNpdmUgcmlnaHQgdG8gcmVwcm9kdWNlLAp0cmFuc2xhdGUgKGFzIGRlZmluZWQgYmVsb3cpLCBhbmQvb3IgZGlzdHJpYnV0ZSB5b3VyIHN1Ym1pc3Npb24gKGluY2x1ZGluZwp0aGUgYWJzdHJhY3QpIHdvcmxkd2lkZSBpbiBwcmludCBhbmQgZWxlY3Ryb25pYyBmb3JtYXQgYW5kIGluIGFueSBtZWRpdW0sCmluY2x1ZGluZyBidXQgbm90IGxpbWl0ZWQgdG8gYXVkaW8gb3IgdmlkZW8uCgpZb3UgYWdyZWUgdGhhdCBEU1UgbWF5LCB3aXRob3V0IGNoYW5naW5nIHRoZSBjb250ZW50LCB0cmFuc2xhdGUgdGhlCnN1Ym1pc3Npb24gdG8gYW55IG1lZGl1bSBvciBmb3JtYXQgZm9yIHRoZSBwdXJwb3NlIG9mIHByZXNlcnZhdGlvbi4KCllvdSBhbHNvIGFncmVlIHRoYXQgRFNVIG1heSBrZWVwIG1vcmUgdGhhbiBvbmUgY29weSBvZiB0aGlzIHN1Ym1pc3Npb24gZm9yCnB1cnBvc2VzIG9mIHNlY3VyaXR5LCBiYWNrLXVwIGFuZCBwcmVzZXJ2YXRpb24uCgpZb3UgcmVwcmVzZW50IHRoYXQgdGhlIHN1Ym1pc3Npb24gaXMgeW91ciBvcmlnaW5hbCB3b3JrLCBhbmQgdGhhdCB5b3UgaGF2ZQp0aGUgcmlnaHQgdG8gZ3JhbnQgdGhlIHJpZ2h0cyBjb250YWluZWQgaW4gdGhpcyBsaWNlbnNlLiBZb3UgYWxzbyByZXByZXNlbnQKdGhhdCB5b3VyIHN1Ym1pc3Npb24gZG9lcyBub3QsIHRvIHRoZSBiZXN0IG9mIHlvdXIga25vd2xlZGdlLCBpbmZyaW5nZSB1cG9uCmFueW9uZSdzIGNvcHlyaWdodC4KCklmIHRoZSBzdWJtaXNzaW9uIGNvbnRhaW5zIG1hdGVyaWFsIGZvciB3aGljaCB5b3UgZG8gbm90IGhvbGQgY29weXJpZ2h0LAp5b3UgcmVwcmVzZW50IHRoYXQgeW91IGhhdmUgb2J0YWluZWQgdGhlIHVucmVzdHJpY3RlZCBwZXJtaXNzaW9uIG9mIHRoZQpjb3B5cmlnaHQgb3duZXIgdG8gZ3JhbnQgRFNVIHRoZSByaWdodHMgcmVxdWlyZWQgYnkgdGhpcyBsaWNlbnNlLCBhbmQgdGhhdApzdWNoIHRoaXJkLXBhcnR5IG93bmVkIG1hdGVyaWFsIGlzIGNsZWFybHkgaWRlbnRpZmllZCBhbmQgYWNrbm93bGVkZ2VkCndpdGhpbiB0aGUgdGV4dCBvciBjb250ZW50IG9mIHRoZSBzdWJtaXNzaW9uLgoKSUYgVEhFIFNVQk1JU1NJT04gSVMgQkFTRUQgVVBPTiBXT1JLIFRIQVQgSEFTIEJFRU4gU1BPTlNPUkVEIE9SIFNVUFBPUlRFRApCWSBBTiBBR0VOQ1kgT1IgT1JHQU5JWkFUSU9OIE9USEVSIFRIQU4gRFNVLCBZT1UgUkVQUkVTRU5UIFRIQVQgWU9VIEhBVkUKRlVMRklMTEVEIEFOWSBSSUdIVCBPRiBSRVZJRVcgT1IgT1RIRVIgT0JMSUdBVElPTlMgUkVRVUlSRUQgQlkgU1VDSApDT05UUkFDVCBPUiBBR1JFRU1FTlQuCgpEU1Ugd2lsbCBjbGVhcmx5IGlkZW50aWZ5IHlvdXIgbmFtZShzKSBhcyB0aGUgYXV0aG9yKHMpIG9yIG93bmVyKHMpIG9mIHRoZQpzdWJtaXNzaW9uLCBhbmQgd2lsbCBub3QgbWFrZSBhbnkgYWx0ZXJhdGlvbiwgb3RoZXIgdGhhbiBhcyBhbGxvd2VkIGJ5IHRoaXMKbGljZW5zZSwgdG8geW91ciBzdWJtaXNzaW9uLgo= |