Geodesic
On the matching arrangement of a~graph and properties of its characteristic polynomial
Diskretnaya Matematika, Tome 35 (2023) no. 2, pp. 3-17.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider a hyperplane arrangement constructed from a subset of the set of all simple paths in a graph. A relation of the constructed arrangement to the maximum matching problem is established. In addition, the problem of finding the characteristic polynomial is reduced to the case of a connected original graph. In the case where the original graph is a tree, a formula for the characteristic polynomial is obtained.
Keywords: hyperplane arrangement, graphical arrangement, partially ordered set, matroid, maximal matching problem. 
@article{DM_2023_35_2_a0,
     author = {A. I. Bolotnikov},
     title = {On the matching arrangement of a~graph and properties of its characteristic polynomial},
     journal = {Diskretnaya Matematika},
     pages = {3--17},
     publisher = {mathdoc},
     volume = {35},
     number = {2},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2023_35_2_a0/}
}
TY  - JOUR
AU  - A. I. Bolotnikov
TI  - On the matching arrangement of a~graph and properties of its characteristic polynomial
JO  - Diskretnaya Matematika
PY  - 2023
SP  - 3
EP  - 17
VL  - 35
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2023_35_2_a0/
LA  - ru
ID  - DM_2023_35_2_a0
ER  - 
%0 Journal Article
%A A. I. Bolotnikov
%T On the matching arrangement of a~graph and properties of its characteristic polynomial
%J Diskretnaya Matematika
%D 2023
%P 3-17
%V 35
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2023_35_2_a0/
%G ru
%F DM_2023_35_2_a0
A. I. Bolotnikov. On the matching arrangement of a~graph and properties of its characteristic polynomial. Diskretnaya Matematika, Tome 35 (2023) no. 2, pp. 3-17. http://geodesic.mathdoc.fr/item/DM_2023_35_2_a0/

[1] Zaslavsky T., Facing up to arrangements: face-count formulas for partitions of space by hyperplanes, v. 1, Mem. Amer. Math. Soc., 154, 1975, 102 pp. | MR | Zbl

[2] Irmatov A. A., “Arrangement of hyperplanes and the number of threshold functions”, Acta Appl. Math., 68:1 (2001), 211–226 | DOI | MR

[3] Irmatov A. A., “Otsenki chisla porogovykh funktsii”, Diskretnaya matematika, 8:4 (1996), 92–107 | DOI | MR | Zbl

[4] Irmatov A. A., “Asimptoticheskie otsenki chisla porogovykh funktsii i veroyatnosti vyrozhdennosti sluchainykh $\pm1$-matrits”, Dokl. RAN. Matem., inform., prots. upr., 492 (2020), 89–91 | DOI | MR | Zbl

[5] Greene C., Zaslavsky T., “On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-radon partitions, and orientations of graphs”, Trans. Amer. Math. Soc., 280:1 (1983), 97–126 | DOI | MR | Zbl

[6] Stanley R. P., Enumerative Combinatorics, v. 1, Cambridge University Press, 2011, 626 pp. | MR

[7] Stanley R. P., “An introduction to hyperplane arrangements”, Geometric Combinatorics, Graduate Summer School (Park City, UT, 2004), IAS/Park City Mathematics Series, 13, 2007, 389–496 | DOI | MR | Zbl

[8] Birkhoff G., “Abstract linear dependence and lattices”, Amer. J. Math., 57:4 (1935), 800–804 | DOI | MR | Zbl

[9] Whitney H., “Congruent graphs and the connectivity of graphs”, Amer. J. Math., 54:1 (1932), 150–168 | DOI | MR | Zbl