اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAn Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs
81
0
0.0
(
0
)
تأليف
Vijay V. Vazirani
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We prove that a fractional perfect matching in a non-bipartite graph can be written, in polynomial time, as a convex combination of perfect matchings. This extends the Birkhoff-von Neumann Theorem from bipartite to non-bipartite graphs. The algorithm of Birkhoff and von Neumann is greedy; it starts with the given fractional perfect matching and successively removes from it perfect matchings, with appropriate coefficients. This fails in non-bipartite graphs -- removing perfect matchings arbitrarily can lead to a graph that is non-empty but has no perfect matchings. Using odd cuts appropriately saves the day.
قيم البحث
اقرأ أيضاً
We revisit the Krein-von Neumann extension in the case where the underlying symmetric operator is strictly positive and apply this to derive the explicit form of the Krein-von Neumann extension for singular, general (i.e., three-coefficient) Sturm-Li
ouville operators on arbitrary intervals. In particular, the boundary conditions for the Krein-von Neumann extension of the strictly positive minimal Sturm-Liouville operator are explicitly expressed in terms of generalized boundary values adapted to the (possible) singularity structure of the coefficients near an interval endpoint.
The properties of quantum probabilities are linked to the geometry of quantum mechanics, described by the Birkhoff-von Neumann lattice. Quantum probabilities violate the additivity property of Kolmogorov probabilities, and they are interpreted as Dem
pster-Shafer probabilities. Deviations from the additivity property are quantified with the Mobius (or non-additivity) operators which are defined through Mobius transforms, and which are shown to be intimately related to commutators. The lack of distributivity in the Birkhoff-von Neumann lattice Lambda , causes deviations from the law of the total probability (which is central in Kolmogorovs probability theory). Projectors which quantify the lack of distributivity in Lambda , and also deviations from the law of the total probability, are introduced. All these operators, are observables and they can be measured experimentally. Constraints for the Mobius operators, which are based on the properties of the Birkhoff-von Neumann lattice (which in the case of finite quantum systems is a modular lattice), are derived.Application of this formalism in the context of coherent states, generalizes coherence to multi-dimensional structures.
We prove the unitary equivalence of the inverse of the Krein--von Neumann extension (on the orthogonal complement of its kernel) of a densely defined, closed, strictly positive operator, $Sgeq epsilon I_{mathcal{H}}$ for some $epsilon >0$ in a Hilber
t space $mathcal{H}$ to an abstract buckling problem operator. In the concrete case where $S=bar{-Delta|_{C_0^infty(Omega)}}$ in $L^2(Omega; d^n x)$ for $Omegasubsetmathbb{R}^n$ an open, bounded (and sufficiently regular) domain, this recovers, as a particular case of a general result due to G. Grubb, that the eigenvalue problem for the Krein Laplacian $S_K$ (i.e., the Krein--von Neumann extension of $S$), [ S_K v = lambda v, quad lambda eq 0, ] is in one-to-one correspondence with the problem of {em the buckling of a clamped plate}, [ (-Delta)^2u=lambda (-Delta) u text{in} Omega, quad lambda eq 0, quad uin H_0^2(Omega), ] where $u$ and $v$ are related via the pair of formulas [ u = S_F^{-1} (-Delta) v, quad v = lambda^{-1}(-Delta) u, ] with $S_F$ the Friedrichs extension of $S$. This establishes the Krein extension as a natural object in elasticity theory (in analogy to the Friedrichs extension, which found natural applications in quantum mechanics, elasticity, etc.).
Is is shown here that the simple test of quantumness for a single system of arXiv:0704.1962 (for a recent experimental realization see arXiv:0804.1646) has exactly the same relation to the discussion of to the problem of describing the quantum system
via a classical probabilistic scheme (that is in terms of hidden variables, or within a realistic theory) as the von Neumann theorem (1932). The latter one was shown by Bell (1966) to stem from an assumption that the hidden variable values for a sum of two non-commuting observables (which is an observable too) have to be, for each individual system, equal to sums of eigenvalues of the two operators. One cannot find a physical justification for such an assumption to hold for non-commeasurable variables. On the positive side. the criterion may be useful in rejecting models which are based on stochastic classical fields. Nevertheless the example used by the Authors has a classical optical realization.
Quantum measurements can be interpreted as a generalisation of probability vectors, in which non-negative real numbers are replaced by positive semi-definite operators. We extrapolate this analogy to define a generalisation of doubly stochastic matri
ces that we call doubly normalised tensors (DNTs), and formulate a corresponding version of Birkhoff-von Neumanns theorem, which states that permutations are the extremal points of the set of doubly stochastic matrices. We prove that joint measurability arises as a mathematical feature of DNTs in this context, needed to establish a characterisation similar to Birkhoff-von Neumanns. Conversely, we also show that DNTs emerge naturally from a particular instance of a joint measurability problem, remarking its relevance in general operator theory.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
