Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCoverings, Matchings and the number of maximal independent sets of graphs
133
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We determine the maximum number of maximal independent sets of arbitrary graphs in terms of their covering numbers and we completely characterize the extremal graphs. As an application, we give a similar result for Konig-Egervary graphs in terms of their matching numbers.
rate research
Read More
Nielsen proved that the maximum number of maximal independent sets (MISs) of size $k$ in an $n$-vertex graph is asymptotic to $(n/k)^k$, with the extremal construction a disjoint union of $k$ cliques with sizes as close to $n/k$ as possible. In this paper we study how many MISs of size $k$ an $n$-vertex graph $G$ can have if $G$ does not contain a clique $K_t$. We prove for all fixed $k$ and $t$ that there exist such graphs with $n^{lfloorfrac{(t-2)k}{t-1}rfloor-o(1)}$ MISs of size $k$ by utilizing recent work of Gowers and B. Janzer on a generalization of the Ruzsa-Szemeredi problem. We prove that this bound is essentially best possible for triangle-free graphs when $kle 4$.
There are distributed graph algorithms for finding maximal matchings and maximal independent sets in $O(Delta + log^* n)$ communication rounds; here $n$ is the number of nodes and $Delta$ is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on $n$ is optimal: these problems cannot be solved in $o(log^* n)$ rounds even if $Delta = 2$. However, the dependency on $Delta$ is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds. We prove that the upper bounds are tight. We show that maximal matchings and maximal independent sets cannot be found in $o(Delta + log log n / log log log n)$ rounds with any randomized algorithm in the LOCAL model of distributed computing. As a corollary, it follows that there is no deterministic algorithm for maximal matchings or maximal independent sets that runs in $o(Delta + log n / log log n)$ rounds; this is an improvement over prior lower bounds also as a function of $n$.
We prove tight upper bounds on the logarithmic derivative of the independence and matching polynomials of d-regular graphs. For independent sets, this theorem is a strengthening of the results of Kahn, Galvin and Tetali, and Zhao showing that a union of copies of $K_{d,d}$ maximizes the number of independent sets and the independence polynomial of a d-regular graph. For matchings, this shows that the matching polynomial and the total number of matchings of a d-regular graph are maximized by a union of copies of $K_{d,d}$. Using this we prove the asymptotic upper matching conjecture of Friedland, Krop, Lundow, and Markstrom. In probabilistic language, our main theorems state that for all d-regular graphs and all $lambda$, the occupancy fraction of the hard-core model and the edge occupancy fraction of the monomer-dimer model with fugacity $lambda$ are maximized by $K_{d,d}$. Our method involves constrained optimization problems over distributions of random variables and applies to all d-regular graphs directly, without a reduction to the bipartite case.
This paper studies the problem of upper bounding the number of independent sets in a graph, expressed in terms of its degree distribution. For bipartite regular graphs, Kahn (2001) established a tight upper bound using an information-theoretic approach, and he also conjectured an upper bound for general graphs. His conjectured bound was recently proved by Sah et al. (2019), using different techniques not involving information theory. The main contribution of this work is the extension of Kahns information-theoretic proof technique to handle irregular bipartite graphs. In particular, when the bipartite graph is regular on one side, but it may be irregular in the other, the extended entropy-based proof technique yields the same bound that was conjectured by Kahn (2001) and proved by Sah et al. (2019).
A well-known conjecture by Lovasz and Plummer from the 1970s asserted that a bridgeless cubic graph has exponentially many perfect matchings. It was solved in the affirmative by Esperet et al. (Adv. Math. 2011). On the other hand, Chudnovsky and Seymour (Combinatorica 2012) proved the conjecture in the special case of cubic planar graphs. In our work we consider random bridgeless cubic planar graphs with the uniform distribution on graphs with $n$ vertices. Under this model we show that the expected number of perfect matchings in labeled bridgeless cubic planar graphs is asymptotically $cgamma^n$, where $c>0$ and $gamma sim 1.14196$ is an explicit algebraic number. We also compute the expected number of perfect matchings in (non necessarily bridgeless) cubic planar graphs and provide lower bounds for unlabeled graphs. Our starting point is a correspondence between counting perfect matchings in rooted cubic planar maps and the partition function of the Ising model in rooted triangulations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
