×

Matching criticality in intersecting hypergraphs. (English) Zbl 1423.05110

Summary: The transversal number \(\tau(H)\) of a hypergraph \(H\) is the minimum cardinality of a set of vertices that intersects all edges of \(H\). The matching number \(\alpha' (H)\) of \(H\) is the maximum cardinality of a matching in \(H\). A hypergraph \(H\) is intersecting if and only if \(\alpha'(H)=1\). For an intersecting hypergraph \(H\) of rank \(r\) without isolated vertex, clearly \(\tau (H)\leq r\). \(H\) is called 1-special if \(\tau (H)=r\), and \(H\) is maximal 1-special if \(H\) is 1-special and adding any missing \(r\)-edge to \(H\) increases the matching number. \(n^2(r)\) and \(n^3(r)\) are the maximum orders of a 1-special hypergraph and a maximal 1-special hypergraph, respectively. Furthermore, the intersecting hyper-graph \(H\) is called 1-edge-critical if for any \(e\in E (H)\) and any \(v\in e,v\)-shrinking \(e\) increases the matching number; \(H\) is called 1-vertex-critical if for any \(v\in V(H)\) deleting the vertex \(v\) and \(v\)-shrinking all edges incident with \(v\) increases the matching number. \(n^4(r)\) and \(n^5(r)\) are the maximum orders of a 1-edge-critical hypergraph and a 1-vertex-critical hypergraph, respectively. The intersecting hypergraphs, as defined above, are said to be matching critical [M. A. Henning and A. Yeo, Quaest. Math. 37, No. 1, 127–138 (2014; Zbl 1397.05129)]. In this paper we study the extremal behavior of matching critical intersecting hypergraphs. We show that \(n^2(r)=n^3(r)\) and \(n^4(r)=n^5(r)\) for all \(r\geq 2\), which partly answers an open problem on matching critical intersecting hypergraphs posed by Henning and Yeo. We also give a strengthening of the result \(n^4(r)=n^5(r)\) for intersecting \(r\)-uniform hypergraphs.

MSC:

05C65 Hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Citations:

Zbl 1397.05129
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aharoni, Ron; Argue, C. J., Covers in partitioned intersecting hypergraphs, European J. Combin., 51, 222-226 (2016) · Zbl 1321.05171 · doi:10.1016/j.ejc.2015.05.005
[2] Alon, N., Transversal numbers of uniform hypergraphs, Graphs Combin., 6, 1-4 (1990) · Zbl 0742.05065 · doi:10.1007/BF01787474
[3] Chvátal, V.; Mcdiarmid, C., Small transversals in hypergraphs, Combinatorica., 12, 19-26 (1992) · Zbl 0776.05080 · doi:10.1007/BF01191201
[4] Cockayne, E. J.; Hedetniemi, S. T.; Slater, P. J., Matchings and transversals in hypergraphs, domination and independence-in trees, J. Combin. Theory Ser. B, 27, 78-80 (1979) · Zbl 0414.05036 · doi:10.1016/0095-8956(79)90044-3
[5] Das, S.; Sudakov, B., Most probably intersecting hypergraphs, Electron. J. Combin., 22, 1 (2015) · Zbl 1310.05150
[6] Dorfling, M.; Henning, M. A., Linear hypergraphs with large transversal number and maximum degree two, European J. Combin., 36, 231-236 (2014) · Zbl 1284.05188 · doi:10.1016/j.ejc.2013.07.016
[7] Erdös, P.; Ko, C.; Rado, R., Intersection theorems for systems of finite sets, Quart. J. Math. Oxford, 12, 2, 313-320 (1961) · Zbl 0100.01902 · doi:10.1093/qmath/12.1.313
[8] Erodös, P. and Lovász, L., Problems and results on 3-chromatic hypergraphs and some related questions. Infinite and finit sets, (Colloq., Keszthely, 1973; dedicated to P. Erdös on his 60th birthday), Vol. II, pp. 609-627, Colloq. Math. Soc. Janos Bolyai 10 North-Holland, Amsterdam, 1975. · Zbl 0315.05117
[9] Frankl, P.; Füredi, Z., Finite projective spaces and intersecting hypergraphs, Combinatorica, 6, 335-354 (1986) · Zbl 0643.05018 · doi:10.1007/BF02579260
[10] Füredi, Z., Matchings and covers in hypergraphs, Graphs Combin., 4, 115-206 (1988) · Zbl 0820.05051 · doi:10.1007/BF01864160
[11] Gallai, T., Neuer Beweis eines Tutteschen Satzes, Magyar Tud. Akad. Mat. Kut. Int. Közl., 8, 135-139 (1963) · Zbl 0129.39802
[12] Guiduli, B.; Kirfily, Z., On intersecting hypergraphs, Discrete Math., 182, 139-151 (1998) · Zbl 0902.05053 · doi:10.1016/S0012-365X(97)00136-2
[13] Hanson, D.; Toft, B., On the maximum number of vertices in n-uniform cliques, Ars. Combin., 16A, 205-216 (1983) · Zbl 0555.05056
[14] Haxell, P. E., A condition for matchability in hypergraphs, Graphs. Combin., 11, 245-248 (1995) · Zbl 0837.05082 · doi:10.1007/BF01793010
[15] Henning, M. A.; Löwenstein, C., Hypergraphs with large transversal number and with edge sizes at least four, Cent. Eur. J. Math., 10, 3, 1133-1140 (2012) · Zbl 1242.05192 · doi:10.2478/s11533-012-0023-9
[16] Henning, M. A.; Yeo, A., Hypergraphs with large transversal number and with edge sizes at least three, J. Graph Theory, 59, 326-348 (2008) · Zbl 1211.05091
[17] Henning, M. A.; Yeo, A., Transversals and matchings in 3-uniform hypergraphs, European J. Combin., 34, 217-228 (2013) · Zbl 1255.05126 · doi:10.1016/j.ejc.2012.07.001
[18] Henning, M. A.; Yeo, A., Matching critical intersecting hypergraphs, Quest. Math., 37, 127-138 (2014) · Zbl 1397.05129 · doi:10.2989/16073606.2013.779991
[19] Hilton, A. J.W.; Milner, E. C., Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford, 18, 2, 369-384 (1967) · Zbl 0168.26205 · doi:10.1093/qmath/18.1.369
[20] Kühn, D.; Osthus, D., Matchings in hypergraphs of large minimum degree, J. Graph Theory, 51, 269-280 (2006) · Zbl 1087.05041 · doi:10.1002/jgt.20139
[21] Lai, F. C.; Chang, G. J., An upper bound for the transversal numbers of 4-uniform hypergraphs, J. Combin. Theory Ser. B, 50, 129-133 (1990) · Zbl 0739.05068 · doi:10.1016/0095-8956(90)90101-5
[22] Mansour, T.; Song, C.; Yuster, R., A comment on Ryser’s conjecture for intersecting hypergraphs, Graphs Combin., 25, 101-109 (2009) · Zbl 1211.05094 · doi:10.1007/s00373-008-0821-9
[23] Tuza, Zs., Critical hypergraphs and intersecting set-pair systems, J. Combin. Theory Ser. B, 39, 134-145 (1985) · Zbl 0586.05029 · doi:10.1016/0095-8956(85)90043-7
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.