Abstract:
We study the quantity p(n,k,t1,t2) equal to the maximum number of edges in a k-uniform hypergraph having the property that all cardinalities of pairwise intersections of edges lie in the interval [t1,t2]. We present previously known upper and lower bounds on this quantity and analyze their interrelations. We obtain new bounds on p(n,k,t1,t2) and consider their possible applications in combinatorial geometry problems. For some values of the parameters we explicitly evaluate the quantity in question. We also give a new bound on the size of a constant-weight error-correcting code.
Citation:
A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “On the number of edges of a uniform hypergraph with a range of allowed intersections”, Probl. Peredachi Inf., 53:4 (2017), 16–42; Problems Inform. Transmission, 53:4 (2017), 319–342
\Bibitem{BobKupRai17}
\by A.~V.~Bobu, A.~E.~Kupriyanov, A.~M.~Raigorodskii
\paper On the number of edges of a~uniform hypergraph with a~range of allowed intersections
\jour Probl. Peredachi Inf.
\yr 2017
\vol 53
\issue 4
\pages 16--42
\mathnet{http://mi.mathnet.ru/ppi2250}
\elib{https://elibrary.ru/item.asp?id=30729589}
\transl
\jour Problems Inform. Transmission
\yr 2017
\vol 53
\issue 4
\pages 319--342
\crossref{https://doi.org/10.1134/S0032946017040020}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000424343800002}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85041497702}
Linking options:
https://www.mathnet.ru/eng/ppi2250
https://www.mathnet.ru/eng/ppi/v53/i4/p16
This publication is cited in the following 12 articles:
Evgeniya Egorova, Vladislav Leonov, Aleksey Mokryakov, Vladimir Tsurkov, “Finding Set Extreme 3-Uniform Hypergraphs Cardinality through Second-Order Signatures”, Axioms, 13:6 (2024), 364
I. S. Beretskii, E. K. Egorova, A. V. Mokryakov, V. I. Tsurkov, “Combination of Bases and an Evaluation of the Set of Extremal 3-Uniform Hypergraphs”, J. Comput. Syst. Sci. Int., 62:5 (2023), 827
Evgeniya Egorova, Aleksey Mokryakov, Vladimir Tsurkov, “The Algebra of Signatures for Extreme Two-Uniform Hypergraphs”, Axioms, 12:12 (2023), 1123
T. Yu. Goltsova, E. K. Egorova, V. Yu. Leonov, A. V. Mokryakov, “First and Second Order Signatures of Extreme Uniform Hypergraphs and Their Relationship with Vectors of the Vertex Degrees”, J. Comput. Syst. Sci. Int., 62:4 (2023), 675
D. A. Zakharov, “Chromatic Numbers of Some Distance Graphs”, Math. Notes, 107:2 (2020), 238–246
Ph. A. Pushnyakov, A. M. Raigorodskii, “Estimate of the Number of Edges in Special Subgraphs of a Distance Graph”, Math. Notes, 107:2 (2020), 322–332
A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “A Generalization of Kneser Graphs”, Math. Notes, 107:3 (2020), 392–403
D. A. Zakharov, A. M. Raigorodskii, “Clique Chromatic Numbers of Intersection Graphs”, Math. Notes, 105:1 (2019), 137–139
A. V. Bobu, A. E. Kupriyanov, “Refinement of Lower Bounds of the Chromatic Number of a Space with Forbidden One-Color Triangles”, Math. Notes, 105:3 (2019), 329–341
Ph. A. Pushnyakov, “The Number of Edges in Induced Subgraphs of Some Distance Graphs”, Math. Notes, 105:4 (2019), 582–591
A. Sagdeev, “On the Frankl–Rödl theorem”, Izv. Math., 82:6 (2018), 1196–1224
A. A. Sagdeev, “Exponentially Ramsey sets”, Problems Inform. Transmission, 54:4 (2018), 372–396