9 papers
Shannon Capacity and Related Graph Invariants for Lexicographic Products
Igal Sason
This paper studies the Shannon capacity of lexicographic products of finite confusability graphs, together with the Lovász theta function and the fractional Haemers number. The lex…
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…