9 papers · 1 filter
The Lovász Local Lemma: Foundations and Applications
Igal Sason
The Lovász Local Lemma (LLL) is a central tool in probabilistic combinatorics, providing a sufficient condition under which a finite collection of undesirable events with limited…
On the transitivity of Gilbert graphs and their complements
Noam Krupnik, Igal Sason, Abraham Berman
The Gilbert graph , which arises naturally in graph theory and coding theory, is the regular graph on in which two vertices are adjacent if…
Advances in the Shannon Capacity of Graphs
Nitay Lavi, Igal Sason
We derive exact values and new bounds for the Shannon capacity of two families of graphs: the -Kneser graphs and the tadpole graphs. We also construct a countably infinite famil…
Counting Graph Homomorphisms in Bipartite Settings
Igal Sason
This paper studies the problem of counting homomorphisms from a bipartite source graph to a bipartite target graph. An exact formula is first derived for the number of homomorphism…
An example showing that Schrijver's -function need not upper bound the Shannon capacity of a graph
Igal Sason
This letter addresses an open question concerning a variant of the Lovász function, which was introduced by Schrijver and independently by McEliece et al. (1978). The…
On H-Intersecting Graph Families and Counting of Homomorphisms
Igal Sason
This work derives an upper bound on the maximum cardinality of a family of graphs on a fixed number of vertices, in which the intersection of every two graphs in that family contai…