Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuestions on the Structure of Perfect Matchings inspired by Quantum Physics
158
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We state a number of related questions on the structure of perfect matchings. Those questions are inspired by and directly connected to Quantum Physics. In particular, they concern the constructability of general quantum states using modern photonic technology. For that we introduce a new concept, denoted as inherited vertex coloring. It is a vertex coloring for every perfect matching. The colors are inherited from the color of the incident edge for each perfect matching. First, we formulate the concepts and questions in pure graph-theoretical language, and finally we explain the physical context of every mathematical object that we use. Importantly, every progress towards answering these questions can directly be translated into new understanding in quantum physics.
rate research
Read More
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.
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.
A family of perfect matchings of $K_{2n}$ is $intersecting$ if any two of its members have an edge in common. It is known that if $mathcal{F}$ is family of intersecting perfect matchings of $K_{2n}$, then $|mathcal{F}| leq (2n-3)!!$ and if equality holds, then $mathcal{F} = mathcal{F}_{ij}$ where $ mathcal{F}_{ij}$ is the family of all perfect matchings of $K_{2n}$ that contain some fixed edge $ij$. In this note, we show that the extremal families are stable, namely, that for any $epsilon in (0,1/sqrt{e})$ and $n > n(epsilon)$, any intersecting family of perfect matchings of size greater than $(1 - 1/sqrt{e} + epsilon)(2n-3)!!$ is contained in $mathcal{F}_{ij}$ for some edge $ij$. The proof uses the Gelfand pair $(S_{2n},S_2 wr S_n)$ along with an isoperimetric method of Ellis.
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.
Let $H$ be a $k$-uniform $D$-regular simple hypergraph on $N$ vertices. Based on an analysis of the Rodl nibble, Alon, Kim and Spencer (1997) proved that if $k ge 3$, then $H$ contains a matching covering all but at most $ND^{-1/(k-1)+o(1)}$ vertices, and asked whether this bound is tight. In this paper we improve their bound by showing that for all $k > 3$, $H$ contains a matching covering all but at most $ND^{-1/(k-1)-eta}$ vertices for some $eta = Theta(k^{-3}) > 0$, when $N$ and $D$ are sufficiently large. Our approach consists of showing that the Rodl nibble process not only constructs a large matching but it also produces many well-distributed `augmenting stars which can then be used to significantly improve the matching constructed by the Rodl nibble process. Based on this, we also improve the results of Kostochka and Rodl (1998) and Vu (2000) on the size of matchings in almost regular hypergraphs with small codegree. As a consequence, we improve the best known bounds on the size of large matchings in combinatorial designs with general parameters. Finally, we improve the bounds of Molloy and Reed (2000) on the chromatic index of hypergraphs with small codegree (which can be applied to improve the best known bounds on the chromatic index of Steiner triple systems and more general designs).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
