Geodesic
Multidimensional threshold matrices and extremal matrices of order $2$
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 20 (2023) no. 2, pp. 1052-1063.

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

The paper is devoted to multidimensional $(0,1)$-matrices extremal with respect to containing a polydiagonal (a fractional generalization of a diagonal). Every extremal matrix is a threshold matrix, i.e., an entry belongs to its support whenever a weighted sum of incident hyperplanes exceeds a given threshold. Firstly, we prove that nonequivalent threshold matrices have different distributions of ones in hyperplanes. Next, we establish that extremal matrices of order $2$ are exactly selfdual threshold Boolean functions. Using this fact, we find the asymptotics of the number of extremal matrices of order $2$ and provide counterexamples to several conjectures on extremal matrices. Finally, we describe extremal matrices of order $2$ with a small diversity of hyperplanes.
Keywords: extremal matrix, threshold matrix, selfdual Boolean function.
Mots-clés : multidimensional matrix 
@article{SEMR_2023_20_2_a36,
     author = {A. A. Taranenko},
     title = {Multidimensional threshold matrices and extremal matrices of order $2$},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1052--1063},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2023_20_2_a36/}
}
TY  - JOUR
AU  - A. A. Taranenko
TI  - Multidimensional threshold matrices and extremal matrices of order $2$
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2023
SP  - 1052
EP  - 1063
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2023_20_2_a36/
LA  - en
ID  - SEMR_2023_20_2_a36
ER  - 
%0 Journal Article
%A A. A. Taranenko
%T Multidimensional threshold matrices and extremal matrices of order $2$
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2023
%P 1052-1063
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2023_20_2_a36/
%G en
%F SEMR_2023_20_2_a36
A. A. Taranenko. Multidimensional threshold matrices and extremal matrices of order $2$. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 20 (2023) no. 2, pp. 1052-1063. http://geodesic.mathdoc.fr/item/SEMR_2023_20_2_a36/

[1] R. Aharoni, A. Georgakopoulos, Ph. Sprüssel, “Perfect matchings in $r$-partite $r$-graphs”, Eur. J. Comb., 30:1 (2009), 39–42 | DOI | MR | Zbl

[2] C.K. Chow, “On the characterization of threshold functions”, Proceedings of 2nd Annual Symposium on Switching Circuit Theory and Logical Design, SWCT 1961 (Detroit, 1961), 34–38

[3] P. Keevash, R. Mycroft, A geometric theory for hypergraph matching, Mem. Amer. Math. Soc., 1098, 2015 | MR | Zbl

[4] S. Muroga, “Generation of self-dual threshold functions and lower bounds of the number of threshold functions and a maximum weight”, Proceedings of 3rd Annual Symposium on Switching Circuit Theory and Logical Design, SWCT 1962, 169–184

[5] S. Muroga, “Generation and asymmetry of self-dual threshold functions”, IEEE Trans. Electron. Comput., 14 (1965), 125–136 | DOI | Zbl

[6] S. Muroga, T. Tsuboi, C.R. Baugh, “Enumeration of threshold functions of eight variables”, IEEE Trans. Comput., 19 (1970), 818–825 | DOI | Zbl

[7] V. Rödl, A. Ruciński, “Dirac-type questions for hypergraphs – a survey (or more problems for Endre to solve)”, An irregular mind. Szemerédi is 70, Dedicated to Endre Szemerédi on the occasion of his seventieth birthday, Bolyai Society Mathematical Studies, 21, eds. Bárány Imre et al., Springer, Berlin, 2010, 561–590 | DOI | MR | Zbl

[8] D.R. Smith, “Bounds on the number of threshold functions”, IEEE Trans. Electron. Comput., 15 (1966), 368–369 | DOI | Zbl

[9] A. Taranenko, “On the König-Hall-Egerváry theorem for multidimensional matrices and multipartite hypergraphs”, Discrete Math., 344:8 (2021), 112447 | DOI | MR | Zbl

[10] R.O. Winder, “Single stage threshold logic”, 2nd Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1961) (Detroit, 1961), 321–332 | MR

[11] Yu.O. Zuev, “Asymptotics of the logarithm of the number of threshold functions of the algebra of logic”, Sov. Math., Dokl., 39:3 (1989), 512–513 | MR | Zbl