{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:50:50Z","timestamp":1740124250057,"version":"3.37.3"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,7,4]],"date-time":"2024-07-04T00:00:00Z","timestamp":1720051200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,7,4]],"date-time":"2024-07-04T00:00:00Z","timestamp":1720051200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100020998","name":"University of Pannonia","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100020998","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Period Math Hung"],"published-print":{"date-parts":[[2024,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A set <jats:italic>S<\/jats:italic> of vertices in a hypergraph is <jats:italic>strongly independent<\/jats:italic> if every hyperedge shares at most one vertex with <jats:italic>S<\/jats:italic>. We prove a sharp result for the number of maximal strongly independent sets in a 3-uniform hypergraph analogous to the Moon-Moser theorem. Given an <jats:italic>r<\/jats:italic>-uniform hypergraph <jats:inline-formula><jats:alternatives><jats:tex-math>$${{\\mathcal {H}}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>H<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and a non-empty set <jats:italic>A<\/jats:italic> of non-negative integers, we say that a set <jats:italic>S<\/jats:italic> is an <jats:italic>A<\/jats:italic>-<jats:italic>transversal<\/jats:italic> of <jats:inline-formula><jats:alternatives><jats:tex-math>$${{\\mathcal {H}}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>H<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> if for any hyperedge <jats:italic>H<\/jats:italic> of <jats:inline-formula><jats:alternatives><jats:tex-math>$${{\\mathcal {H}}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>H<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, we have <jats:inline-formula><jats:alternatives><jats:tex-math>$$|H\\cap S| \\in A$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>|<\/mml:mo>\n                    <mml:mi>H<\/mml:mi>\n                    <mml:mo>\u2229<\/mml:mo>\n                    <mml:mi>S<\/mml:mi>\n                    <mml:mo>|<\/mml:mo>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:mi>A<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Independent sets are <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\{0,1,\\dots ,r{-}1\\}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>{<\/mml:mo>\n                    <mml:mn>0<\/mml:mn>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mo>\u22ef<\/mml:mo>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>r<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>}<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-transversals, while strongly independent sets are <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\{0,1\\}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>{<\/mml:mo>\n                    <mml:mn>0<\/mml:mn>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>}<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-transversals. Note that for some sets <jats:italic>A<\/jats:italic>, there may exist hypergraphs without any <jats:italic>A<\/jats:italic>-transversals. We study the maximum number of <jats:italic>A<\/jats:italic>-transversals for every <jats:italic>A<\/jats:italic>, but we focus on the more natural sets, <jats:inline-formula><jats:alternatives><jats:tex-math>$$A=\\{a\\}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>A<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mo>{<\/mml:mo>\n                    <mml:mi>a<\/mml:mi>\n                    <mml:mo>}<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, <jats:inline-formula><jats:alternatives><jats:tex-math>$$A=\\{0,1,\\dots ,a\\}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>A<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mo>{<\/mml:mo>\n                    <mml:mn>0<\/mml:mn>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mo>\u22ef<\/mml:mo>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>a<\/mml:mi>\n                    <mml:mo>}<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> or <jats:italic>A<\/jats:italic> being the set of odd integers or the set of even integers.\n<\/jats:p>","DOI":"10.1007\/s10998-024-00586-1","type":"journal-article","created":{"date-parts":[[2024,7,4]],"date-time":"2024-07-04T15:02:33Z","timestamp":1720105353000},"page":"107-115","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the number of A-transversals in hypergraphs"],"prefix":"10.1007","volume":"89","author":[{"given":"J\u00e1nos","family":"Bar\u00e1t","sequence":"first","affiliation":[]},{"given":"D\u00e1niel","family":"Gerbner","sequence":"additional","affiliation":[]},{"given":"Anastasia","family":"Halfpap","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,7,4]]},"reference":[{"key":"586_CR1","unstructured":"G.J. Chang, M.J. Jou. Survey on counting maximal independent sets. In Proceedings of the Second Asian Mathematical Conference (1995) 265\u2013275"},{"issue":"4","key":"586_CR2","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1002\/jgt.3190110403","volume":"11","author":"Z F\u00fcredi","year":"1987","unstructured":"Z. F\u00fcredi, The number of maximal independent sets in connected graphs. J. Graph Theory 11(4), 463\u2013470 (1987)","journal-title":"J. Graph Theory"},{"issue":"3","key":"586_CR3","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1017\/S0963548314000546","volume":"24","author":"W Gan","year":"2015","unstructured":"W. Gan, P.-S. Loh, B. Sudakov, Maximizing the number of independent sets of a fixed size. Combinatorics, Probability and Computing 24(3), 521\u2013527 (2015)","journal-title":"Combinatorics, Probability and Computing"},{"issue":"2\u20133","key":"586_CR4","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/0012-365X(88)90114-8","volume":"68","author":"JM Griggs","year":"1988","unstructured":"J.M. Griggs, C.M. Grinstead, D.R. Guichard, The number of maximal independent sets in a connected graph. Discrete Mathematics 68(2\u20133), 211\u2013220 (1988)","journal-title":"Discrete Mathematics"},{"issue":"20","key":"586_CR5","doi-asserted-by":"publisher","first-page":"2105","DOI":"10.1016\/j.disc.2011.06.015","volume":"311","author":"D Galvin","year":"2011","unstructured":"D. Galvin, Two problems on independent sets in graphs. Discrete Mathematics 311(20), 2105\u20132112 (2011)","journal-title":"Discrete Mathematics"},{"issue":"16","key":"586_CR6","doi-asserted-by":"publisher","first-page":"3668","DOI":"10.1016\/j.disc.2007.07.024","volume":"308","author":"Z Lonc","year":"2008","unstructured":"Z. Lonc, M. Truszczy\u0144ski, On the number of minimal transversals in 3-uniform hypergraphs. Discrete Mathematics 308(16), 3668\u20133687 (2008)","journal-title":"Discrete Mathematics"},{"key":"586_CR7","unstructured":"R.E. Miller, D.E. Muller. A problem of maximum consistent subsets. IBM Research Report RC-240, J.T. Watson Research Center, New York, USA (1960)"},{"key":"586_CR8","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"JW Moon","year":"1965","unstructured":"J.W. Moon, L. Moser, On cliques in graphs. Israel J. Math. 3, 23\u201328 (1965)","journal-title":"Israel J. Math."},{"issue":"1","key":"586_CR9","first-page":"123","volume":"3","author":"V Napolitano","year":"2007","unstructured":"V. Napolitano, Two-character sets in finite linear spaces. Contributions to Discrete Mathematics 3(1), 123\u2013133 (2007)","journal-title":"Contributions to Discrete Mathematics"},{"key":"586_CR10","doi-asserted-by":"crossref","unstructured":"J.M. Nielsen. On the number of maximal independent sets in a graph. BRICS Report Series 9(15) (2002)","DOI":"10.7146\/brics.v9i15.21733"},{"key":"586_CR11","unstructured":"C. Palmer. Problem booklet of the 11th Eml\u00e9kt\u00e1bla Workshop held in 2022. https:\/\/www.renyi.hu\/~emlektab\/emlektabla11.pdf"},{"issue":"2\u20133","key":"586_CR12","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0012-365X(81)90225-9","volume":"37","author":"I Tomescu","year":"1981","unstructured":"I. Tomescu, Le nombre maximum de cliques et de recouvrements par cliques des hypergraphes chromatiques complets. Discrete Mathematics 37(2\u20133), 263\u2013277 (1981)","journal-title":"Discrete Mathematics"},{"issue":"3","key":"586_CR13","first-page":"17","volume":"13","author":"DR Wood","year":"2011","unstructured":"D.R. Wood, On the number of maximal independent sets in a graph. Discrete Maths. & Theoretical Computer Science 13(3), 17\u201320 (2011)","journal-title":"Discrete Maths. & Theoretical Computer Science"}],"container-title":["Periodica Mathematica Hungarica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10998-024-00586-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10998-024-00586-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10998-024-00586-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,13]],"date-time":"2024-08-13T13:03:09Z","timestamp":1723554189000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10998-024-00586-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,4]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["586"],"URL":"https:\/\/doi.org\/10.1007\/s10998-024-00586-1","relation":{},"ISSN":["0031-5303","1588-2829"],"issn-type":[{"type":"print","value":"0031-5303"},{"type":"electronic","value":"1588-2829"}],"subject":[],"published":{"date-parts":[[2024,7,4]]},"assertion":[{"value":"25 August 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 July 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}