{"id":3979,"date":"2026-01-29T14:19:50","date_gmt":"2026-01-29T22:19:50","guid":{"rendered":"https:\/\/colleges.claremont.edu\/ccms\/?post_type=tribe_events&p=3979"},"modified":"2026-01-29T14:25:43","modified_gmt":"2026-01-29T22:25:43","slug":"sampling-from-the-proper-colorings-of-a-graph-using-a-number-of-colors-linear-in-the-maximum-degree-in-expected-linear-time-mark-huber-cmc","status":"publish","type":"tribe_events","link":"https:\/\/colleges.claremont.edu\/ccms\/event\/sampling-from-the-proper-colorings-of-a-graph-using-a-number-of-colors-linear-in-the-maximum-degree-in-expected-linear-time-mark-huber-cmc\/","title":{"rendered":"Sampling from the proper colorings of a graph using a number of colors linear in the maximum degree in expected linear time (Mark Huber, CMC)"},"content":{"rendered":"

Abstract:<\/strong> A proper coloring of a graph is an assignment of colors from \\( \\{1, 2, \\ldots, k\\} \\) to each node of a graph such that no two nodes connected by an edge receive the same color. Let \\( \\Delta \\) denote the maximum degree of the graph. If \\( k \\geq \\Delta + 1 \\) then at least one proper coloring always exists. However, counting the number of proper colorings of an arbitrary graph is a #P-complete problem, even when \\( \\Delta = 3 \\). This means finding a polynomial time exact algorithm is unlikely to be found. On the other hand, if a user can sample uniformly at random from the proper colorings of a graph, then it becomes possible to approximately count the number of proper colorings to arbitrary precision in polynomial time. This work presents the first algorithm that has an expected running time that is linear in the size of the graph under the condition that \\( k > 3.637 \\Delta \\). Joint work with Kritika Bhandari.<\/p>\n","protected":false},"excerpt":{"rendered":"

Abstract: A proper coloring of a graph is an assignment of colors from \\( \\{1, 2, \\ldots, k\\} \\) to each node of a graph such that no two nodes […]<\/p>\n","protected":false},"author":262,"featured_media":0,"template":"","meta":{"_acf_changed":false,"_price":"","_stock":"","_tribe_ticket_header":"","_tribe_default_ticket_provider":"","_tribe_ticket_capacity":"0","_ticket_start_date":"","_ticket_end_date":"","_tribe_ticket_show_description":"","_tribe_ticket_show_not_going":false,"_tribe_ticket_use_global_stock":"","_tribe_ticket_global_stock_level":"","_global_stock_mode":"","_global_stock_cap":"","_tribe_rsvp_for_event":"","_tribe_ticket_going_count":"","_tribe_ticket_not_going_count":"","_tribe_tickets_list":"[]","_tribe_ticket_has_attendee_info_fields":false,"_tribe_events_status":"","_tribe_events_status_reason":"","_tribe_events_is_hybrid":"","_tribe_events_is_virtual":"","_tribe_events_virtual_video_source":"","_tribe_events_virtual_embed_video":"","_tribe_events_virtual_linked_button_text":"","_tribe_events_virtual_linked_button":"","_tribe_events_virtual_show_embed_at":"","_tribe_events_virtual_show_embed_to":[],"_tribe_events_virtual_show_on_event":"","_tribe_events_virtual_show_on_views":"","_tribe_events_virtual_url":"","footnotes":"","_tec_slr_enabled":"","_tec_slr_layout":""},"tags":[],"tribe_events_cat":[15],"class_list":["post-3979","tribe_events","type-tribe_events","status-publish","hentry","tribe_events_cat-applied-math-seminar","cat_applied-math-seminar"],"acf":[],"yoast_head":"\nSampling from the proper colorings of a graph using a number of colors linear in the maximum degree in expected linear time (Mark Huber, CMC) - Claremont Center for the Mathematical Sciences<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/colleges.claremont.edu\/ccms\/event\/sampling-from-the-proper-colorings-of-a-graph-using-a-number-of-colors-linear-in-the-maximum-degree-in-expected-linear-time-mark-huber-cmc\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Sampling from the proper colorings of a graph using a number of colors linear in the maximum degree in expected linear time (Mark Huber, CMC) - Claremont Center for the Mathematical Sciences\" \/>\n<meta property=\"og:description\" content=\"Abstract: A proper coloring of a graph is an assignment of colors from ( {1, 2, ldots, k} ) to each node of a graph such that no two nodes […]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/colleges.claremont.edu\/ccms\/event\/sampling-from-the-proper-colorings-of-a-graph-using-a-number-of-colors-linear-in-the-maximum-degree-in-expected-linear-time-mark-huber-cmc\/\" \/>\n<meta property=\"og:site_name\" content=\"Claremont Center for the Mathematical Sciences\" \/>\n<meta property=\"article:modified_time\" content=\"2026-01-29T22:25:43+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/colleges.claremont.edu\\\/ccms\\\/event\\\/sampling-from-the-proper-colorings-of-a-graph-using-a-number-of-colors-linear-in-the-maximum-degree-in-expected-linear-time-mark-huber-cmc\\\/\",\"url\":\"https:\\\/\\\/colleges.claremont.edu\\\/ccms\\\/event\\\/sampling-from-the-proper-colorings-of-a-graph-using-a-number-of-colors-linear-in-the-maximum-degree-in-expected-linear-time-mark-huber-cmc\\\/\",\"name\":\"Sampling from the proper colorings of a graph using a number of colors linear in the maximum degree in expected linear time (Mark Huber, CMC) - Claremont Center for the Mathematical Sciences\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/colleges.claremont.edu\\\/ccms\\\/#website\"},\"datePublished\":\"2026-01-29T22:19:50+00:00\",\"dateModified\":\"2026-01-29T22:25:43+00:00\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/colleges.claremont.edu\\\/ccms\\\/event\\\/sampling-from-the-proper-colorings-of-a-graph-using-a-number-of-colors-linear-in-the-maximum-degree-in-expected-linear-time-mark-huber-cmc\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/colleges.claremont.edu\\\/ccms\\\/event\\\/sampling-from-the-proper-colorings-of-a-graph-using-a-number-of-colors-linear-in-the-maximum-degree-in-expected-linear-time-mark-huber-cmc\\\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/colleges.claremont.edu\\\/ccms\\\/event\\\/sampling-from-the-proper-colorings-of-a-graph-using-a-number-of-colors-linear-in-the-maximum-degree-in-expected-linear-time-mark-huber-cmc\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/colleges.claremont.edu\\\/ccms\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Events\",\"item\":\"https:\\\/\\\/colleges.claremont.edu\\\/ccms\\\/events\\\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Sampling from the proper colorings of a graph using a number of colors linear in the maximum degree in expected linear time (Mark Huber, CMC)\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/colleges.claremont.edu\\\/ccms\\\/#website\",\"url\":\"https:\\\/\\\/colleges.claremont.edu\\\/ccms\\\/\",\"name\":\"Claremont Center for the Mathematical Sciences\",\"description\":\"Proudly Serving the Math Community at the Claremont Colleges Since 2007\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/colleges.claremont.edu\\\/ccms\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Sampling from the proper colorings of a graph using a number of colors linear in the maximum degree in expected linear time (Mark Huber, CMC) - Claremont Center for the Mathematical Sciences","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/colleges.claremont.edu\/ccms\/event\/sampling-from-the-proper-colorings-of-a-graph-using-a-number-of-colors-linear-in-the-maximum-degree-in-expected-linear-time-mark-huber-cmc\/","og_locale":"en_US","og_type":"article","og_title":"Sampling from the proper colorings of a graph using a number of colors linear in the maximum degree in expected linear time (Mark Huber, CMC) - Claremont Center for the Mathematical Sciences","og_description":"Abstract: A proper coloring of a graph is an assignment of colors from ( {1, 2, ldots, k} ) to each node of a graph such that no two nodes […]","og_url":"https:\/\/colleges.claremont.edu\/ccms\/event\/sampling-from-the-proper-colorings-of-a-graph-using-a-number-of-colors-linear-in-the-maximum-degree-in-expected-linear-time-mark-huber-cmc\/","og_site_name":"Claremont Center for the Mathematical Sciences","article_modified_time":"2026-01-29T22:25:43+00:00","twitter_card":"summary_large_image","twitter_misc":{"Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/colleges.claremont.edu\/ccms\/event\/sampling-from-the-proper-colorings-of-a-graph-using-a-number-of-colors-linear-in-the-maximum-degree-in-expected-linear-time-mark-huber-cmc\/","url":"https:\/\/colleges.claremont.edu\/ccms\/event\/sampling-from-the-proper-colorings-of-a-graph-using-a-number-of-colors-linear-in-the-maximum-degree-in-expected-linear-time-mark-huber-cmc\/","name":"Sampling from the proper colorings of a graph using a number of colors linear in the maximum degree in expected linear time (Mark Huber, CMC) - Claremont Center for the Mathematical Sciences","isPartOf":{"@id":"https:\/\/colleges.claremont.edu\/ccms\/#website"},"datePublished":"2026-01-29T22:19:50+00:00","dateModified":"2026-01-29T22:25:43+00:00","breadcrumb":{"@id":"https:\/\/colleges.claremont.edu\/ccms\/event\/sampling-from-the-proper-colorings-of-a-graph-using-a-number-of-colors-linear-in-the-maximum-degree-in-expected-linear-time-mark-huber-cmc\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/colleges.claremont.edu\/ccms\/event\/sampling-from-the-proper-colorings-of-a-graph-using-a-number-of-colors-linear-in-the-maximum-degree-in-expected-linear-time-mark-huber-cmc\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/colleges.claremont.edu\/ccms\/event\/sampling-from-the-proper-colorings-of-a-graph-using-a-number-of-colors-linear-in-the-maximum-degree-in-expected-linear-time-mark-huber-cmc\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/colleges.claremont.edu\/ccms\/"},{"@type":"ListItem","position":2,"name":"Events","item":"https:\/\/colleges.claremont.edu\/ccms\/events\/"},{"@type":"ListItem","position":3,"name":"Sampling from the proper colorings of a graph using a number of colors linear in the maximum degree in expected linear time (Mark Huber, CMC)"}]},{"@type":"WebSite","@id":"https:\/\/colleges.claremont.edu\/ccms\/#website","url":"https:\/\/colleges.claremont.edu\/ccms\/","name":"Claremont Center for the Mathematical Sciences","description":"Proudly Serving the Math Community at the Claremont Colleges Since 2007","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/colleges.claremont.edu\/ccms\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"}]}},"ticketed":false,"_links":{"self":[{"href":"https:\/\/colleges.claremont.edu\/ccms\/wp-json\/wp\/v2\/tribe_events\/3979","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/colleges.claremont.edu\/ccms\/wp-json\/wp\/v2\/tribe_events"}],"about":[{"href":"https:\/\/colleges.claremont.edu\/ccms\/wp-json\/wp\/v2\/types\/tribe_events"}],"author":[{"embeddable":true,"href":"https:\/\/colleges.claremont.edu\/ccms\/wp-json\/wp\/v2\/users\/262"}],"version-history":[{"count":0,"href":"https:\/\/colleges.claremont.edu\/ccms\/wp-json\/wp\/v2\/tribe_events\/3979\/revisions"}],"wp:attachment":[{"href":"https:\/\/colleges.claremont.edu\/ccms\/wp-json\/wp\/v2\/media?parent=3979"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/colleges.claremont.edu\/ccms\/wp-json\/wp\/v2\/tags?post=3979"},{"taxonomy":"tribe_events_cat","embeddable":true,"href":"https:\/\/colleges.claremont.edu\/ccms\/wp-json\/wp\/v2\/tribe_events_cat?post=3979"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}