Greedy maximal independent sets via local limits

Seminar
Speaker
Peleg Michaeli (Tel-Aviv University)
Date
01/12/2019 - 15:30 - 14:00Add to Calendar 2019-12-01 14:00:00 2019-12-01 15:30:00 Greedy maximal independent sets via local limits The random greedy algorithm for finding a maximal independent set in a graph has been studied extensively in various settings in combinatorics, probability, computer science — and even in chemistry.  The algorithm builds a maximal independent set by inspecting the vertices of the graph one at a time according to a random order, adding the current vertex to the independent set if it is not connected to any previously added vertex by an edge. In this talk I will present a natural and general framework for calculating the asymptotics of the proportion of the yielded independent set for sequences of (possibly random) graphs, involving a useful notion of local convergence.  We use this framework both to give short and simple proofs for results on previously studied families of graphs, such as paths and binomial random graphs, and to give new results for other models such as random trees. If time allows, I will discuss a more delicate result, according to which in expectation, the cardinality of a random greedy independent set in the path is no larger than that in any other tree of the same order. The talk is based on joint work with Michael Krivelevich, Tamás Mészáros and Clara Shikhelman. Room 201, Math and CS Building (Bldg. 216) אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Room 201, Math and CS Building (Bldg. 216)
Abstract

The random greedy algorithm for finding a maximal independent set in a graph
has been studied extensively in various settings in combinatorics, probability,
computer science — and even in chemistry.  The algorithm builds a maximal
independent set by inspecting the vertices of the graph one at a time according
to a random order, adding the current vertex to the independent set if it is
not connected to any previously added vertex by an edge.

In this talk I will present a natural and general framework for calculating the
asymptotics of the proportion of the yielded independent set for sequences of
(possibly random) graphs, involving a useful notion of local convergence.  We
use this framework both to give short and simple proofs for results on
previously studied families of graphs, such as paths and binomial random
graphs, and to give new results for other models such as random trees.

If time allows, I will discuss a more delicate result, according to which in
expectation, the cardinality of a random greedy independent set in the path is
no larger than that in any other tree of the same order.

The talk is based on joint work with Michael Krivelevich, Tamás Mészáros and
Clara Shikhelman.

Last Updated Date : 25/11/2019