اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRecognizing Graph Theoretic Properties with Polynomial Ideals
165
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Many hard combinatorial problems can be modeled by a system of polynomial equations. N. Alon coined the term polynomial method to describe the use of nonlinear polynomials when solving combinatorial problems. We continue the exploration of the polynomial method and show how the algorithmic theory of polynomial ideals can be used to detect k-colorability, unique Hamiltonicity, and automorphism rigidity of graphs. Our techniques are diverse and involve Nullstellensatz certificates, linear algebra over finite fields, Groebner bases, toric algebra, convex programming, and real algebraic geometry.
قيم البحث
اقرأ أيضاً
In this article, we study the weak and strong Lefschetz properties, and the related notion of almost revlex ideal, in the non-Artinian case, proving that several results known in the Artinian case hold also in this more general setting. We then apply
the obtained results to the study of the Jacobian algebra of hyperplane arrangements.
It is proved that a finite intersection of special preenveloping ideals in an exact category $({mathcal A}; {mathcal E})$ is a special preenveloping ideal. Dually, a finite intersection of special precovering ideals is a special precovering ideal. A
counterexample of Happel and Unger shows that the analogous statement about special preenveloping subcategories does not hold in classical approximation theory. If the exact category has exact coproducts, resp., exact products, these results extend to intersections of infinite families of special peenveloping, resp., special precovering, ideals. These techniques yield the Bongartz-Eklof-Trlifaj Lemma: if $a colon A to B$ is a morphism in ${mathcal A},$ then the ideal $a^{perp}$ is special preenveloping. This is an ideal version of the Eklof-Trlifaj Lemma, but the proof is based on that of Bongartz Lemma. The main consequence is that the ideal cotorsion pair generated by a small ideal is complete.
Following Britz, Johnsen, Mayhew and Shiromoto, we consider demi-ma-troids as a(nother) natural generalization of matroids. As they have shown, demi-ma-troids are the appropriate combinatorial objects for studying Weis duality. Our results here appor
t further evidence about the trueness of that observation. We define the Hamming polynomial of a demimatroid $M$, denoted by $W(x,y,t)$, as a generalization of the extended Hamming weight enumerator of a matroid. The polynomial $W(x,y,t)$ is a specialization of the Tutte polynomial of $M$, and actually is equivalent to it. Guided by work of Johnsen, Roksvold and Verdure for matroids, we prove that Betti numbers of a demimatroid and its elongations determine the Hamming polynomial. Our results may be applied to simplicial complexes since in a canonical way they can be viewed as demimatroids. Furthermore, following work of Brylawski and Gordon, we show how demimatroids may be generalized one step further, to combinatroids. A combinatroid, or Brylawski structure, is an integer valued function $rho$, defined over the power set of a finite ground set, satisfying the only condition $rho(emptyset)=0$. Even in this extreme generality, we will show that many concepts and invariants in coding theory can be carried on directly to combinatroids, say, Tutte polynomial, characteristic polynomial, MacWilliams identity, extended Hamming polynomial, and the $r$-th generalized Hamming polynomial; this last one, at least conjecturelly, guided by the work of Jurrius and Pellikaan for linear codes. All this largely extends the notions of deletion, contraction, duality and codes to non-matroidal structures.
We propose an algebraic framework for generalized graph Laplacians which unifies the study of resistor networks, the critical group, and the eigenvalues of the Laplacian and adjacency matrices. Given a graph with boundary $G$ together with a generali
zed Laplacian $L$ with entries in a commutative ring $R$, we define a generalized critical group $Upsilon_R(G,L)$. We relate $Upsilon_R(G,L)$ to spaces of harmonic functions on the network using the Hom, Tor, and Ext functors of homological algebra. We study how these algebraic objects transform under combinatorial operations on the network $(G,L)$, including harmonic morphisms, layer-stripping, duality, and symmetry. In particular, we use layer-stripping operations from the theory of resistor networks to systematize discrete harmonic continuation. This leads to an algebraic characterization of the graphs with boundary that can be completely layer-stripped, an algorithm for simplifying computation of $Upsilon_R(G,L)$, and upper bounds for the number of invariant factors in the critical group and the multiplicity of Laplacian eigenvalues in terms of geometric quantities.
We graph-theoretically characterize the class of graphs $G$ such that $I(G)^2$ are Buchsbaum.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
