×

The m-Bézout bound and distance geometry. (English) Zbl 07497946

Boulier, François (ed.) et al., Computer algebra in scientific computing. 23rd international workshop, CASC 2021, Sochi, Russia, September 13–17, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12865, 6-20 (2021).
Summary: We offer a closed-form bound on the m-Bézout bound for multi-homogeneous systems whose equations include two variable subsets of the same degree. Our bound is expectedly not tight, since computation of the m-Bézout number is #P-hard by reduction to the permanent. On the upside, our bound is tighter than the existing closed-form bound derived from the permanent, which applies only to systems characterized by further structure.
Our work is inspired by the application of the m-Bézout bound to counting Euclidean embeddings of distance graphs. Distance geometry and rigidity theory study graphs with a finite number of configurations, up to rigid transformations, which are prescribed by the edge lengths. Counting embeddings is an algebraic question once one constructs a system whose solutions correspond to the different embeddings. Surprisingly, the best asymptotic bound on the number of embeddings had for decades been Bézout’s, applied to the obvious system of quadratic equations expressing the length constraints. This is essentially \(2^{dn}\), for graphs of \(n\) vertices in \(d\) dimensions, and implies a bound of \(4^n\) for the most famous case of Laman graphs in the plane. However, the best lower bound is about \(2.5^n\), which follows by numerically solving appropriate instances.
In [3], the authors leverage the m-Bézout bound and express it by the number of certain constrained orientations of simple graphs. A combinatorial process on these graphs has recently improved the bound on orientations and, therefore, has improved the bounds on the number of distance graph embeddings [4]. For Laman graphs the new bound is inferior to \(3.8^n\) thus improving upon Bézout’s bound for the first time. In this paper, we obtain a closed-form bound on the m-Bézout number of a class of multi-homogeneous systems that subsumes the systems encountered in distance graph embeddings.
For the entire collection see [Zbl 1482.68009].

MSC:

68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Baglivo, J., Graver, J.: Incidence and Symmetry in Design and Architecture. No. 7 in Cambridge Urban and Architectural Studies, Cambridge University Press (1983)
[2] Bartzos, E.; Emiris, I.; Legerský, J.; Tsigaridas, E., On the maximal number of real embeddings of minimally rigid graphs in \(\mathbb{R}^2, \mathbb{R}^3\) and \(S^2\), J. Symbol. Comput., 102, 189-208 (2021) · Zbl 1448.05144
[3] Bartzos, E., Emiris, I., Schicho, J.: On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs. J. Appl. Algebra Eng. Commun. Comput. 31 (2020). doi:10.1007/s00200-020-00447-7 · Zbl 1464.05266
[4] Bartzos, E., Emiris, I., Vidunas, R.: New upper bounds for the number of embeddings of minimally rigid graphs. arXiv:2010.10578 [math.CO] (2020)
[5] Bernstein, D., Farnsworth, C., Rodriguez, J.: The algebraic matroid of the finite unit norm tight frame (FUNTF) variety. J. Pure Appl. Algebra 224(8) (2020). doi:10.1016/j.jpaa.2020.106351 · Zbl 1437.05037
[6] Bernstein, D., The number of roots of a system of equations, Func. Anal. Appl., 9, 3, 183-185 (1975) · Zbl 0328.32001
[7] Borcea, C.; Streinu, I., The number of embeddings of minimally rigid graphs, Discret. Comput. Geomet., 31, 2, 287-303 (2004) · Zbl 1050.05030
[8] Borcea, C.; Streinu, I., Periodic tilings and auxetic deployments, Math. Mech. Solids, 26, 2, 199-216 (2021) · Zbl 07357398
[9] Brègman, L., Some properties of nonnegative matrices and their permanents, Dokl. Akad. Nauk SSSR, 211, 1, 27-30 (1973) · Zbl 0293.15010
[10] Cifuentes, D.; Parrilo, P., Exploiting chordal structure in polynomial ideals: a Gröbner bases approach, SIAM J. Discret. Math., 30, 3, 1534-1570 (2016) · Zbl 1353.13033
[11] Emiris, I.; Tsigaridas, E.; Varvitsiotis, A.; Mucherino, A.; Lavor, C.; Liberti, L.; Maculan, N., Mixed volume and distance geometry techniques for counting Euclidean embeddings of rigid graphs, Distance Geometry: Theory, Methods and Applications, 23-45 (2013), New York: Springer, New York · Zbl 1269.05077
[12] Emiris, I., Vidunas, R.: Root ounts of semi-mixed systems, and an application to counting Nash equilibria. In: Proceedings of ACM International Symposium Symbolic & Algebraic Computation, pp. 154-161. ISSAC, ACM (2014). doi:10.1145/2608628.2608679 · Zbl 1325.68275
[13] Emmerich, D.: Structures Tendues et Autotendantes. Ecole d’Architecture de Paris, La Villette, France (1988)
[14] Harris, J.; Tu, L., On symmetric and skew-symmetric determinantal varieties, Topology, 23, 71-84 (1984) · Zbl 0534.55010
[15] Jackson, W., Owen, J.: Equivalent realisations of a rigid graph. Discrete Appl. Math. 256, 42-58 (2019). doi:10.1016/j.dam.2017.12.009. Special Issue on Distance Geometry: Theory & Applications’16 · Zbl 1405.05037
[16] Lavor, C., et al.: Minimal NMR distance information for rigidity of protein graphs. Discrete Appl. Math. 256, 91-104 (2019). www.sciencedirect.com/science/article/pii/S0166218X18301793. Special Issue on Distance Geometry Theory & Applications’16 · Zbl 1405.05178
[17] Li, H., Xia, B., Zhang, H., Zheng, T.: Choosing the variable ordering for cylindrical algebraic decomposition via exploiting chordal structure. In: Proceedings of International Symposium on Symbolic and Algebraic Computation, ISSAC 2021. ACM (2021)
[18] Liberti, L., Distance geometry and data science, TOP, 28, 271-339 (2020) · Zbl 1511.51006
[19] Malajovich, G.; Meer, K., Computing minimal multi-homogeneous Bezout numbers is Hard, Theory Comput. Syst., 40, 4, 553-570 (2007) · Zbl 1126.90082
[20] Maxwell, J.: On the calculation of the equilibrium and stiffness of frames. Philos. Mag. 39(12) (1864)
[21] Minc, H.: Upper bounds for permanents of \(\left(0,1 \right)\)-matrices. Bull. AMS 69, 789-791 (1963). doi:10.1090/S0002-9904-1963-11031-9 · Zbl 0116.25202
[22] Rocklin, D., Zhou, S., Sun, K., Mao, X.: Transformable topological mechanical metamaterials. Nat. Commun. 8 (2017). doi:10.1038/ncomms14201
[23] Shafarevich, I., Intersection Numbers, 233-283 (2013), Heidelberg: Springer, Heidelberg
[24] Steffens, R.; Theobald, T., Mixed volume techniques for embeddings of Laman graphs, Comput. Geom., 43, 84-93 (2010) · Zbl 1225.05186
[25] Verschelde, J.: Modernizing PHCpack through phcpy. In: Proceedings of the 6th European Conference on Python in Science (EuroSciPy 2013), pp. 71-76 (2014)
[26] Zelazo, D., Franchi, A., Allgöwer, F., Bülthoff, H.H., Giordano, P.: Rigidity maintenance control for multi-robot systems. In: Proceedings of Robotics: Science & Systems, Sydney, Australia (2012)
[27] Zhu, Z.; So, AC; Ye, Y., Universal rigidity and edge sparsification for sensor network localization, SIAM J. Optim., 20, 6, 3059-3081 (2010) · Zbl 1211.90166
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.