Systems of Representatives

K. D. Kovalenko ; A. M. Raigorodskii

Matematičeskie zametki, Tome 106 (2019) no. 3, pp. 387-394.

Résumé

Lower and upper bounds are obtained for the size $\zeta(n,r,s,k)$ of a minimum system of common representatives for a system of families of $k$-element sets. By $\zeta(n,r,s,k)$ we mean the maximum (over all systems $\Sigma=\{M_1,\dots,M_r\}$ of sets $M_i$ consisting of at least $s$ subsets of $\{1,\dots,n\}$ of cardinality not exceeding $k$) of the minimum size of a system of common representatives of $\Sigma$. The obtained results generalize previous estimates of $\zeta(n,r,s,1)$.

Détail

Keywords: systems of common representatives, minimum systems of common representatives.

Bibliographie

[1] V. E. Tarakanov, Kombinatornye zadachi i $(0,1)$-matritsy, Nauka, M., 1985 | MR

[2] A. M. Raigorodskii, Sistemy obschikh predstavitelei v kombinatorike i ikh prilozheniya v geometrii, MTsNMO, M., 2009

[3] P. Erdesh, Dzh. Spenser, Veroyatnostnye metody v kombinatorike, Mir, M., 1976 | MR

[4] J. Balogh, D. Cherkashin, S. Kiselev, “Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs”, European J. Combin., 79 (2019), 228–236 | DOI | MR

[5] L. E. Shabanov, “Turán-type results for distance graphs in an infinitesimal plane layer”, J. Math. Sci. (N.Y.), 236:5 (2019), 554–578 | DOI

[6] N. N. Kuzyurin, “Asimptoticheskoe issledovanie zadachi o pokrytii”, Problemy kibernetiki, 37 (1980), 19–56

[7] A. M. Raigorodskii, “Problema Borsuka dlya tselochislennykh mnogogrannikov”, Matem. sb., 193:10 (2002), 139–160 | DOI | MR | Zbl

[8] A. M. Raigorodskii, “Problemy Borsuka i Gryunbauma dlya reshetchatykh mnogogrannikov”, Izv. RAN. Ser. matem., 69:3 (2005), 81–108 | DOI | MR | Zbl

[9] A. M. Raigorodskii, “Three lectures on the Borsuk partition problem”, Surveys in Contemporary Mathematics, London Math. Soc. Lecture Note Ser., 347, Cambridge Univ. Press, Cambridge, 2007, 202–248 | MR

[10] L. I. Bogolyubskii, A. M. Raigorodskii, “Zamechanie o nizhnikh otsenkakh khromaticheskikh chisel prostranstv maloi razmernosti s metrikami $\ell_1$ i $\ell_2$”, Matem. zametki, 105:2 (2019), 187–213 | DOI

[11] A. M. Raigorodskii, “Combinatorial geometry and coding theory”, Fund. Inform., 145:3 (2016), 359–369 | DOI | MR

[12] A. M. Raigorodskii, “Defekt dopustimykh sharov i oktaedrov v reshetke i sistemy obschikh predstavitelei”, Matem. sb., 189:6 (1998), 117–141 | DOI | MR | Zbl

[13] A. M. Raigorodskii, “Veroyatnostnyi podkhod k zadache o defektakh dopustimykh mnozhestv v reshetke”, Matem. zametki, 68:6 (2000), 910–916 | DOI | MR | Zbl

[14] A. M. Raigorodskii, “On a problem in the geometry of numbers”, Tr. In-ta matem., 15:1 (2007), 111–117

[15] A. A. Bagan, A. M. Raigorodskii, “Defekt dopustimogo oktaedra v tsentrirovke tselochislennoi reshetki, porozhdennoi zadannym chislom vektorov”, Matem. zametki, 99:3 (2016), 457–459 | DOI | MR

[16] A. A. Bagan, “Defect of an admissible octahedron in a centering obtained by adding rational vectors to an integer lattice”, Mosc. J. Comb. Number Theory, 5:1-2 (2015), 3–13 | MR

[17] M. A. Fadin, “Defect of an octahedron in a rational lattice”, Discrete Math., 2019 (to appear)

[18] M. A. Fadin, A. M. Raigorodskii, “Maksimalnyi defekt dopustimogo oktaedra v ratsionalnoi reshetke”, UMN, 74:3 (447) (2019), 191–192 | DOI