Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn improved linear bound on the number of perfect matchings in cubic graphs
139
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We show that every cubic bridgeless graph with n vertices has at least 3n/4-10 perfect matchings. This is the first bound that differs by more than a constant from the maximal dimension of the perfect matching polytope.
rate research
Read More
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.
Let $G$ be a simple graph with $2n$ vertices and a perfect matching. The forcing number $f(G,M)$ of a perfect matching $M$ of $G$ is the smallest cardinality of a subset of $M$ that is contained in no other perfect matching of $G$. Among all perfect matchings $M$ of $G$, the minimum and maximum values of $f(G,M)$ are called the minimum and maximum forcing numbers of $G$, denoted by $f(G)$ and $F(G)$, respectively. Then $f(G)leq F(G)leq n-1$. Che and Chen (2011) proposed an open problem: how to characterize the graphs $G$ with $f(G)=n-1$. Later they showed that for bipartite graphs $G$, $f(G)=n-1$ if and only if $G$ is complete bipartite graph $K_{n,n}$. In this paper, we solve the problem for general graphs and obtain that $f(G)=n-1$ if and only if $G$ is a complete multipartite graph or $K^+_{n,n}$ ($K_{n,n}$ with arbitrary additional edges in the same partite set). For a larger class of graphs $G$ with $F(G)=n-1$ we show that $G$ is $n$-connected and a brick (3-connected and bicritical graph) except for $K^+_{n,n}$. In particular, we prove that the forcing spectrum of each such graph $G$ is continued by matching 2-switches and the minimum forcing numbers of all such graphs $G$ form an integer interval from $lfloorfrac{n}{2}rfloor$ to $n-1$.
Ahlswede and Katona (1977) posed the following isodiametric problem in Hamming spaces: For every $n$ and $1le Mle2^{n}$, determine the minimum average Hamming distance of binary codes with length $n$ and size $M$. Fu, Wei, and Yeung (2001) used linear programming duality to derive a lower bound on the minimum average distance. However, their linear programming approach was not completely exploited. In this paper, we improve Fu-Wei-Yeungs bound by finding a better feasible solution to their dual program. For fixed $0<ale1/2$ and for $M=leftlceil a2^{n}rightrceil $, our feasible solution attains the asymptotically optimal value of Fu-Wei-Yeungs dual program as $ntoinfty$. Hence for $0<ale1/2$, all possible asymptotic bounds that can be derived by Fu-Wei-Yeungs linear program have been characterized. Furthermore, noting that the average distance of a code is closely related to weights of Fourier coefficients of a Boolean function, we also apply the linear programming technique to prove bounds on Fourier weights of a Boolean function of various degrees.
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.
A family of perfect matchings of $K_{2n}$ is $t$-$intersecting$ if any two members share $t$ or more edges. We prove for any $t in mathbb{N}$ that every $t$-intersecting family of perfect matchings has size no greater than $(2(n-t) - 1)!!$ for sufficiently large $n$, and that equality holds if and only if the family is composed of all perfect matchings that contain a fixed set of $t$ disjoint edges. This is an asymptotic version of a conjecture of Godsil and Meagher that can be seen as the non-bipartite analogue of the Deza-Frankl conjecture proven by Ellis, Friedgut, and Pilpel.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
