×

On vertex independence number of uniform hypergraphs. (English) Zbl 1297.05116

Summary: Let \(H\) be an \(r\)-uniform hypergraph with \(r \geq 2\) and let \(\alpha(H)\) be its vertex independence number. In the paper bounds of \(\alpha(H)\) are given for different uniform hypergraphs: if \(H\) has no isolated vertex, then in terms of the degrees, and for triangle-free linear \(H\) in terms of the order and average degree.

MSC:

05C30 Enumeration in graph theory
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C65 Hypergraphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C07 Vertex degrees

Software:

Blossom V
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] V. Abraham, Independence in hypergraphs. J. Indian Math. Soc. (N.S.), 78, 1-4 (2011) 1-7. ⇒141; · Zbl 1247.05165
[2] B. D. Acharya, Interrelations among the notions of independence, domination and full sets in a hypergraph, Nat. Acad. Sci. Lett. 13, 11 (1990) 421-422. ⇒ 142; · Zbl 0863.05062
[3] G. Agnarsson, A. Egilsson, M. M. Halldórson, Vertex coloring acyclic digraphs and their corresponding hypergraphs, Discrete Appl. Math. 156, 10 (2008) 1918-1928. ⇒142; · Zbl 1152.05324
[4] G. Agnarsson, M. M. Halldórson, E. Losievskaja, SDP-based algorithms for maximum independent set problems on hypergraphs, in: Automata, Languages and Programming. Part I, Lecture Notes in Comput. Sci. 5555, Springer, Berlin, 2009, 12-23. ⇒133, 138, 141; · Zbl 1248.68549
[5] G. Agnarsson, M. M. Halldórson, E. Losievskaja, SDP-based algorithms for maximum independent set problems on hypergraphs, Theoret. Comp. Sci. 470 (2013) 1-9. ⇒133, 138, 141; · Zbl 1258.05089
[6] M. Ajtai, P. Erdős, J. Komlós and E. Szemerédi, On Turán theorem for sparse graphs, Combinatorica 1, 3 (1981) 313-317. ⇒134; · Zbl 0491.05038
[7] M. Ajtai, P. Erdős, J. Komlós, E. Szemerédi, A dense infinite Sidon sequence, European J. Combin. 2, 1 (1981) 1-11. ⇒134; · Zbl 0474.10038
[8] M. Ajtai, J. Komlós and E. Szemerédi, A note on Ramsey numbers, J. Combin. Theory Ser. A 29 (1980) 354-360. ⇒134; · Zbl 0455.05045
[9] A. Alon, A fast and simple randomized parallel algorithm for the maximal independent set problem, J. Algorithms 7, 4 (1986) 567-583. ⇒133, 138; · Zbl 0631.68063
[10] N. Alon, P. Frankl, H. Huang, V. Rödl, A. Ruciński, Large matchings in uniform hypergraphs and the conjectures of Erdős and Samuels, J. Combin. Theory Ser. A 119, 6 (2012) 1200-1215. ⇒133, 138, 142; · Zbl 1242.05189
[11] N. Alon, J. H. Spencer, The Probabilistic Method, Wiley-Interscience, New York, 1992. ⇒134; · Zbl 0767.05001
[12] A. Alon, A. Uri, Y. Azar, Independent sets in hypergraphs with applications to routing via fixed paths. In: Randomization, approximation, and combinatorial optimization (Berkeley, CA, 1999), Lecture Notes in Comput. Sci. 1671, Springer, Berlin, 1999, 16-27. ⇒141; · Zbl 0949.68172
[13] N. Alon, R. Yuster, On a hypergraph matching problem, Graphs Comb. 21 (2005) 377-384. ⇒142; · Zbl 1090.05051
[14] E. Angel, R. Campigotto, C. Laforest, A new lower bound on the independence number of graphs, Discrete Appl. 161, 6 (2013) 847-852. ⇒134; · Zbl 1262.05114
[15] G. Ausiello, A. D’Atri, D. Sacc‘a, Minimal representation of directed hypergraphs, SIAM J. Comput. 15 (1986) 418-431. ⇒139; · Zbl 0602.68056
[16] J. Bailey, T. Manoukian, K. Ramamohanaro, A fast algorithm for computing hypergraph transversals and its application in mining emerging patterns, in: Proc. of the Third IEEE Int.l Conf. on Data Mining (ICDM03), 2003, 485-488. ⇒142;
[17] J. Balogh, J. Butterfield, P. Hu, J. Lenz, D. Mubayi, On the chromatic thresholds of hypergraphs arXiv:1103.1416, 2013, 37 pages. ⇒142; · Zbl 1372.05105
[18] J. Balogh, R. Morris, W. Samotij, Independent sets in hypergraphs, arXiv:1204.6530, 2013, 42 pages. ⇒136; · Zbl 1310.05154
[19] Zs. Baranyai, On the factorization of the complete uniform hypergraph, in: A. Hajnal, R. Rado, V. T. Sós (Eds.), Infinite and Finite Sets, Proc. Coll. Keszthely, 1973, North-Holland, Amsterdam, Netherlands, 1975, pp. 91-108. ⇒142; · Zbl 0306.05137
[20] S. Behrens, C. Erbes, M. Ferrara, S. G. Hartke, B. Reiniger, H. Spinoza, C. Tomlinson, New results on degree sequences of uniform hypergraphs. Electron. J. Combin. 20, 4 (2013) #P14, 18 pages. ⇒139; · Zbl 1295.05081
[21] M. Behrisch, A. Coja-Oghlan, M. Kang, The asymptotic number of connected d-uniform hypergraphs, Combin. Probab. Comput. 23, 3 (2014) 367-385. ⇒139; · Zbl 1288.05243
[22] C. Berge, The Theory of Graphs and its Applications, Wiley, London, 1964. ⇒ 137; · Zbl 0097.38903
[23] E. Berger, R. Ziv, A note on the edge cover number and independence number in hypergraphs, Discrete Math. 308, 12 (2008) 2649-2654. ⇒141; · Zbl 1166.05004
[24] C. Bertram-Kretzberg, H. Lefmann, The algorithmic aspects of uncrowded hypergraphs. SIAM J. Comput. 29, 1 (1999) 201-230. ⇒142; · Zbl 0937.68056
[25] T. Biedl, E. D. Demaine, C. A. Duncan, R. Fleischer, S. G. Kobourov, Tight bounds on maximal and maximum matchings, Discrete Math. 285 (2004) 7-15. ⇒141; · Zbl 1044.05056
[26] V. Blinovsky, Fractional matching in hypergraphs, arXiv:1311.2671, 2013, 6 pages. ⇒141; · Zbl 0907.94035
[27] B. Bollobás, D. E. Daykin, P. Erdős, Sets of independent edges of a hypergraph, Quart. J. Math. Oxford Ser. (2) 27, 1 (1976), 25-32. ⇒141; · Zbl 0337.05135
[28] A. Bonato, J. I. Brown, D. Mitsche, P. Pralat, Independence densities of hypergraphs, arXiv:1308.2837, 2013, 16 pages. ⇒141; · Zbl 1300.05194
[29] A. Bonato, J. I. Brown, D. Mitsche, P. Pralat, Independence densities of hypergraphs, Europ. J. Combin. 40 (2014) 124-136. ⇒141; · Zbl 1300.05194
[30] R. Boppana, M. M. Halldórson, Approximating maximum independent set by excluding subsets, BIT, 32 (1992) 160-196. ⇒133, 138;
[31] M. Bordewich, M. Dyer, M. Karpiński, Path coupling using stopping times and counting independent sets and colorings in hypergraphs Random Structures Alg. 32, 3 (2008) 375-399. ⇒141; · Zbl 1181.05061
[32] E. Boros, K. Elbassioni, V. Gurvich, L. Khachiyan,Generating maximal independent sets for hypergraphs with bounded edge-intersections. In: LATIN 2004: Theoretical informatics, Lecture Notes in Comput. Sci. 2976, Springer, Berlin, 2004, 488-498. ⇒141; · Zbl 1196.05057
[33] E. Boros, V. Gurvich, K. Elbassioni, L. Khachiyan, An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension. Parallel Process. Lett. 10, 4 (2000) 253-266. ⇒141;
[34] M. Borowiecki, D. Michalak, The independence graphs of hypergraphs and middle graphs, Discuss. Math. 7 (1985) 31-37. ⇒141; · Zbl 0639.05049
[35] Cs. Bujtás, Zs. Tuza, Uniform mixed hypergraphs: The possible numbers of colors, Graphs Combin., 24 (2008) 1-12. ⇒142; · Zbl 1147.05025
[36] Y. Caro, New results on the independence number, Technical Report, 1979, Tel- Aviv University. ⇒134;
[37] Y. Caro, A. Hansberg, New approach to the k-independence number of a graph. Electron. J. Combin. 20, 1 (2013) #P33, 17 pages. ⇒135; · Zbl 1266.05110
[38] Y. Caro, Zs. Tuza, Improved lower bounds on k-independence, J. Graph Theory 15 (1991) 99-107. ⇒135; · Zbl 0753.68079
[39] R. D. Carr, G. Lancia, S. Istrail, C. Genomics, Branch-and-Cut algorithms for independent set problems: Integrality gap and an application to protein structure alignment. SAND Report SAND2000-2171, Sandia National Laboratories, 2000. ⇒142;
[40] G. Chartrand, S. Schuster, On the independence number of complementary graphs, Trans. New York Acad. Sci., Series II 36, 3 (1974) 247-251. ⇒139; · Zbl 0275.05110
[41] M. Chellali, O. Favaron, A. Hansberg, L. Volkmann, k-domination and kindependence in graphs: a survey, Graphs Combin. 28, 1 (2012) 1-55. ⇒135, 137; · Zbl 1234.05174
[42] M. Chellali, N. J. Rad, On k-independence critical graphs. Australas. J. Combin. 53 (2012) 289-298. ⇒135; · Zbl 1256.05162
[43] E. J. Cockayne, S. T. Hedetniemi, R. Laskar, Gallai theorems for graphs, hypergraphs and set systems, Discrete Math. 72 (1988) 35-47. ⇒142; · Zbl 0728.05050
[44] B. Csaba, T. A. Pick, A Shokoufandeh, A note on the Caro-Tuza bound on the independence number of uniform hypergraphs, Australas. J. Combin. 52 (2012) 235-242. ⇒135; · Zbl 1248.05130
[45] J. Cutler, A. J. Radcliffe, Hypergraph independent sets, Combin. Probab. Comput. 22, 1 (2013) 9-20. ⇒141; · Zbl 1257.05104
[46] B. C. Dean, S. M. Hedetniemi, S. T. Hedetniemii, J. Lewis, A. McRae, Matchability and k-maximal matchings. Discrete Math. 159, 1 (2011) 15-22. ⇒141; · Zbl 1203.05125
[47] A. Dudek, A. Frieze, A. Ruciński, M. ˇSileikis, Approximate counting of regular hypergraphs, Inf. Processing Letters, 113, 1921 (2013) 785-788. ⇒139, 141; · Zbl 1285.05092
[48] K. Dutta, D. Mubayi, C. R. Subramanian, New lower bounds for the independence number of sparse graphs and hypergraphs. SIAM J. Discrete Math. 26, 3 (2012) 1134-1147. ⇒138; · Zbl 1256.05166
[49] J. Edmonds, Paths, trees, and flowers, Canadian J. Math. 17 (1965) 449-467. ⇒133, 138, 141; · Zbl 0132.20903
[50] J. Edmonds, Maximal matching and a polyhedron with 0, 1-vertices, J. Research Nat. Bureau Standards B-69 (1965) 125-130. ⇒133, 138, 141; · Zbl 0141.21802
[51] A. Eustis, Hypergraph Independence Numbers, PhD Thesis. University of California, San Diego. 2013. 123 pages. ⇒138; · Zbl 1260.05017
[52] A. Eustis, J. Verstra¨ete, On the independence number of Steiner systems, Combinatorics, Prob. Comp. 22, 2 (2013) 241-252. ⇒138; · Zbl 1260.05017
[53] S. Fajtlowicz, Independence, clique size and maximum degree, Combinatorica 4 (1984), 35-38. ⇒136; · Zbl 0576.05025
[54] O. Favoron, A. Hansberg, L. Volkmann, On k-domination and minimum degree in graphs, J. Graph Theory 57, 1 (2008) 33-40. ⇒135, 137; · Zbl 1211.05110
[55] A. Frank, T. Király, Z. Király, On the orientation of graphs and hypergraphs, Discrete Appl. Math 131, 2 (2003) 385-400. ⇒140, 142; · Zbl 1030.90099
[56] P. Frankl, Improved bounds for Erdős matching conjecture, J. Combin. Theory Ser. A 120, 5 (2013) 1068-1072. ⇒141; · Zbl 1277.05123
[57] P. Frankl, T. Luczak, K.Mieczkowska, On matchings in hypergraphs. Electron. J. Combin. 19, 2 (2012), #P42, 5 pages. ⇒141; · Zbl 1252.05092
[58] P. Frankl, V. Rödl, Some Ramsey-Turn type results for hypergraphs. Combinatorica 8, 4 (1988) 323-332. ⇒142; · Zbl 0658.05041
[59] P. Frankl, V. Rödl, The uniformity lemma for hypergraphs, Graphs Combin. 8 (1992) 309-312. ⇒142; · Zbl 0777.05084
[60] M. Frieze, On the independence number of random graphs, Discrete Math. 81, 2 (1990) 171-175. ⇒136; · Zbl 0712.05052
[61] Z. FÜredi, Matchings and covers in hypergraphs, Graphs Combin. 4 (1988) 115-206. ⇒141; · Zbl 0820.05051
[62] Z. Füredi, The number of maximal independent sets in connected graphs, J. Graph Theory, 11, 4 (1995) 463-470. ⇒137; · Zbl 0647.05032
[63] Z. FÜredi, Linear trees in uniform hypergraphs, Europ. J. Combin. 35 (2014) 264-272. ⇒142; · Zbl 1296.05140
[64] Z. Füredi, M. Ruszinkó, Uniform hypergraphs containing no grids, Adv. Math. 240 (2013) 302-324. ⇒142; · Zbl 1278.05161
[65] H. M. Gabow, An efficient implementation of Edmonds’ algorithm for maximum matching on graphs, J. ACM 23, 2 (1976) 221-234. ⇒141; · Zbl 0327.05121
[66] H. M. Gabow, Data structures for weighted matchings and nearest nearest common ancestors with linking, in: Proc. 1st Annual ACM-SIAM Symp. Discrete Algorithms 1990, 434-443. ⇒141; · Zbl 0800.68617
[67] T. Gallai, Über extreme Punkt- und Kantenmengen, Ann. Univ. Sci. Budapest. de Rolando Eötvös Nominatae, Sect. Math. 2 (1959) 133-138. ⇒139; · Zbl 0094.36105
[68] G. Gallo, G. Longo, S. Nguyen, S. Pallottino, Directed hypergraphs and applications, Discrete Appl. Math 42, 2-3 (1993) 177-201. ⇒140, 142; · Zbl 0771.05074
[69] S.. Gaspers, D. Kratsch, M. Liedloff, Independent sets and bicliques in graphs, in: H. Broersma, T. Erlebach, T. Friedetzky, D. Paulusma (eds.) Graph-Theoretic Concepts in Computer Science (Int. Workshop WG2008, Durham, UK, June 30, 2008-July 2, 2008), Lecture Notes in Comput. Sci. 5344, Springer, 2008, 171-182. ⇒136; · Zbl 1202.05096
[70] C. Greenhill, The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Comput. Complexity 9, 1 (2000) 52-72. ⇒141; · Zbl 0963.68082
[71] C. Greenhill, A. Rucinski, N. C. Wormald, Random hypergraph processes with degree restrictions, Graphs Combin. 20 (2004) 319-332. ⇒141; · Zbl 1053.05112
[72] J. Griggs, Lower bounds on the independence number in terms of the degrees, J. Comb. Theory, Ser. B 34 (1983) 22-39. ⇒134, 145; · Zbl 0505.05037
[73] J. L. Gross, J. Yellen, P. Zhang, Handbook of Graph Theory, CRC Press, Boca Raton, FL, 2014. ⇒133, 138; · Zbl 1278.05001
[74] D. Gunopolus, R. Khardon, H. Mannila, H. Toivonen, Data mining, hypergraph traversals, and machine learning. Proc. PODS’97, 1997, pp. 209-2016. ⇒142;
[75] M. M. Halldórson, Approximations of weighted independent set and hereditary subset problems, J. Graph Algorithms Appl. 4, 1 (2000) 1-16. ⇒136;
[76] M. M. Halldórson, E. Losievskaja, Independent sets in bounded-degree hypergraphs, Discrete Appl. Math 157, 8 (2009) 1773-1786. ⇒141; · Zbl 1173.05035
[77] J. Han, Near perfect matchings in k-uniform hypergraphs, arXiv:1404.1136, 2014, 7 pages. ⇒141; · Zbl 1371.05228
[78] H. Hàn, Y. Person, M. Schaht, On perfect matchings in uniform hypergraphs with large minimum vertex degree, SIAM J. Discrete Math. 23, 2 (2009) 732-748. ⇒141, 142; · Zbl 1191.05074
[79] A. Hansberg, R. Pepper, On k-domination and j-independence in graphs. Discrete Appl. Math 161, 10-11 (2013) 1472-1480. ⇒135, 136, 137; · Zbl 1287.05102
[80] J. Harant, A lower bound on independence number of a graph, Discrete Math. 188, 13 (1998) 239243. ⇒134; · Zbl 0958.05067
[81] J. Harant, A lower bound on independence in terms of degrees, Discrete Appl. Mathematics 159, 10 (2011) 966-970. ⇒134, 135; · Zbl 1218.05036
[82] J. Harant, A. Pruchnewski, M. Voigt, On dominating sets and independent sets of graphs, Combinatorics, Prob. Comp. 8, 6 (1999) 547-553. ⇒137; · Zbl 0959.05080
[83] J. Harant, D. Rautenbach, Independence in connected graphs. Discrete Appl. Math 159, 1 (2011) 79-86. ⇒135; · Zbl 1208.05098
[84] J. Harant, I. Schiermeyer, On the independence number of a graph in terms of order and size, Discrete Math., 232, 1-3 (2001) 131-138. ⇒135; · Zbl 1030.05091
[85] J. Harant, I. Schiermeyer, A lower bound on the independence number of a graph in terms of degrees. Discuss. Math. Graph Theory 26, 3 (2006), 431-437. ⇒135; · Zbl 1138.05051
[86] M. A. Henning, C. Löwenstein, D. Rautenbach, Independent sets and matchings in subcubic graphs. Discrete Math., 312, 11 (2012) 1900-1910. ⇒141; · Zbl 1244.05177
[87] M. A. Henning, C. Löwenstein, J. Southey, A. Yeo. A new lower bound on the independence number of a graph and applications, Electron. J. Comb. 21, 1 (2014) #P1.38. ⇒136; · Zbl 1300.05226
[88] M. A. Henning, A. Yeo, Tight lower bounds on the size of a maximum matching in a regular graph. Graphs Combin. 3, 6 (2007) 647-657. ⇒141; · Zbl 1143.05065
[89] M. A. Henning, A. Yeo, Lower bounds on the size of maximum independent sets and matchings in hypergraphs of rank three. J. Graph Theory, 72, 1-2 (2013) 220-245. ⇒135, 141, 142; · Zbl 1262.05111
[90] T. Hofmeister, H. Lefmann, Approximating maximum independent sets in uniform hypergraphs. In: Mathematical Foundations of Computer Science, 1998, Brno, Lecture Notes in Comput. Sci. 1450, Springer, Berlin, 1998, 562-570. ⇒ 141; · Zbl 0917.05055
[91] J. E. Hopcroft, R. M. Karp, An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput., 2 (1973) 225-231. ⇒141; · Zbl 0266.05114
[92] H. Huang, P.-S. Loh, B. Sudakov, The size of a hypergraph and its matching number, Combin. Probab. Comput. 21, 3 (2012) 442-450. ⇒141, 142; · Zbl 1242.05268
[93] D. S. Johnson, M. Yannakakis, On generating all maximal independent sets, Inf. Processing Letters 27, 3 (1988) 119-123. ⇒133, 138, 141, 142; · Zbl 0654.68086
[94] T. Johnston, L. Lu, Turn problems on non-uniform hypergraphs, arXiv:1301.1870, 2013. ⇒142; · Zbl 1302.05128
[95] T. Johnston, L. Lu, Strong jumps and Lagrangians of non-uniform hypergraphs, arXiv:1403.1220, 2014. ⇒142;
[96] B. K. Jose, Zs. Tuza, Hypergraph domination and strong independence. Appl. Anal. Discrete Math. 3, 2 (2009) 347-358. ⇒142; · Zbl 1199.05261
[97] E. Jucovič, F. Olejník, On chromatic and achromatic numbers of uniform hypergraphs, Časopis Pĕstováni Matematiky, 99 (1974) 123-130. ⇒139, 142; · Zbl 0278.05120
[98] A. Kako, T. Ono, T. Hirata, M. M. Halldórson, Approximation algorithms for the weighted independent set problem in sparse graphs, Discrete Appl. Math 157, 4 (2009) 617-626. ⇒136; · Zbl 1173.05352
[99] M. Karonski, T. Luczak, The number of connected sparsely edged uniform hypergraphs, Discrete Math. 171, 1-3 (1997) 153-167. ⇒142; · Zbl 0876.05041
[100] R.M. Karp, U.V. Vazirani, V.V. Vazirani, An optimal online algorithm for optimal bipartite matching, in: Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing (STOC ’90), ACM, New York, NY, 1990, 352-358. ⇒141;
[101] R. M. Karp, A. Widgerson, A fast parallel algorithm for the maximal independent set problem, J. ACM 32, 4 (1985) 762-773. ⇒133, 138; · Zbl 0633.68026
[102] G. O. H. Katona, Continuous versions of some extremal hypergraph problems, in: Combinatorics (Keszthely, Hungary, 1976), Coll. Math. Soc. J. Bolyai 18 (Math. Soc. J. Bolyai, Budapest, 1978), 653-678. ⇒142;
[103] G. O. H. Katona, Continuous versions of some extremal hypergraph problems II, Acta Math. Acad. Sci. Hungar. 35 (1980) 67-77. ⇒142; · Zbl 0466.05052
[104] P. Keevash, F. Knox, R. Mycroft, Polynomial-time perfect matchings in dense hypergraphs, arXiv:1307.2608, 2013. 62 pages. ⇒141; · Zbl 1293.05297
[105] P. Keevash, R. Mycroft, A geometric theory for hypergraph matching, arXiv:1108.1757, 2013, 101 pages. ⇒141; · Zbl 1306.05172
[106] P. Keevash, B. Sudakov, On a hypergraph Turán problem of Frankl, Combinatorica 25, 6 (2005) 673-706. ⇒142; · Zbl 1089.05075
[107] P. Kelsen, On the parallel complexity of computing a maximal independent set in a hypergraph. In: Proc. Twenty-fourth Annual ACM Symp. Theory Comp. (STOC’92), ACM New York, NY, 1992, 339-350. ⇒138, 142;
[108] L. Khachiyan, E. Boros, V. Gurvich, K. Elbassioni, Computing many maximal independent sets for hypergraphs in parallel, Parallel Process. Lett. 17, 2 (2007) 141-152. ⇒141;
[109] I. Khan, Perfect matchings in 3-uniform hypergraphs with large vertex degree. SIAM J. Discrete Math. 27, 2 (2013) 1021-1039. ⇒141; · Zbl 1272.05160
[110] M. A. Khan, S. , K. K. Kayibi, Scores, inequalities and regular hypertournaments, Math. Inequal. Appl. 15, 2 (2012), 343-351. ⇒139; · Zbl 1238.05107
[111] Y. Kohayakawa, V. Rödl, J. Skokan, Hypergraphs, quasi-randomness, and conditions for regularity, J. Combin. Theory Ser. A 97, 2 (2002) 307-352. ⇒142; · Zbl 0990.05111
[112] V. Kolmogorov, V. Blossom, A new implementation of a minimum cost perfect matching algorithm, Math. Programming Pomp. 1 (2009) 43-67. ⇒141; · Zbl 1171.05429
[113] D. Kőnig, Graphs and matrices (Hungarian), Matematikai és Fizikai Lapok 38 (1931) 116-119. ⇒141; · JFM 57.1340.04
[114] A. Kostochka, D. Mubayi, J. Verstra¨ete, On independent sets in hypergraphs, Random Structures Algorithms 44, 2 (2014) 224-239. ⇒142; · Zbl 1303.05141
[115] M. Krivelevich, Approximate set covering in uniform hypergraphs, J. Algorithms 25, 1 (1997) 118-143. ⇒142; · Zbl 0888.68089
[116] M. Krivelevich, R. Nathaniel, B. Sudakov, Approximating coloring and maximum independent sets in 3-uniform hypergraphs, J. Algorithms 41, 1 (2001) 99-113. ⇒142; · Zbl 1002.68112
[117] D. KÜhn, D. Loose, Hamilton cycles in 3-uniform hypergraphs of high minimum degree, J. Comb. Theory, Ser. B 96, 6 (2006) 767-821. ⇒142; · Zbl 1109.05065
[118] D. KÜhn, D. Osthus, A. Treglown, Matchings in 3-uniform hypergraphs, J. Combinatorial Theory Series B 103 (2013) 291-305. ⇒141; · Zbl 1262.05128
[119] D. KÜhn, D. Osthus, T. Townsend, Fractional and integer matchings in uniform hypergraphs, Europ. J. Combin. 38 (2014) 83-96. ⇒141; · Zbl 1282.05172
[120] R. Laskar, B. Auerbach, On complementary graphs with no isolated vertices, Discrete Math. 24, 2 (1978) 113-118. ⇒140; · Zbl 0393.05047
[121] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, Generating all maximal independent sets: NP-hardness and polynomial-time algorithms, SIAM J. Comput. 9, 3 (1980), 558-565. ⇒133, 138; · Zbl 0445.68054
[122] V. V. Lepin, An algorithm for finding the independence number of a recursively generated hypergraph (Russian), Dokl. Nats. Akad. Nauk Belarusi 49, 2 (2005), 22-25, 125. ⇒141; · Zbl 1178.05067
[123] Y. Li, C. Rousseau, On book-complete graph Ramsey numbers, J. Comb. Theory, Ser. B 68, 1 (1996) 36-44. ⇒142; · Zbl 0861.05046
[124] Y. Li, C. Rousseau, W. Zang, Asymptotic upper bound for Ramsey functions, Graphs Combin., 17 (2001) 123-128. ⇒142; · Zbl 0979.05078
[125] Y. Li, W. Zang, Differential methods for finding independent sets in hypergraphs, SIAM J. Discrete Math. 20 (2006) 96-104. ⇒141, 142; · Zbl 1112.05071
[126] E. Losievskaja, Approximation Algorithms for Independent Set Problems on Hypergraphs, PhD Dissertation, School of Computer Science Reykjavik University, Reykyavik, 2009, XV + 80 pages. ⇒133, 138, 141;
[127] L. Lovász, M. D. Plummer, Matching Theory, North Holland, Amsterdam, 1986. ⇒141;
[128] M. Luby, A simple parallel algorithm for the maximal independent set problem, SIAM J. Comput. 15, 1 (1976) 1036-1053. ⇒133, 138; · Zbl 0619.68058
[129] T. Luczak, E. Szymańska, A parallel randomized algorithm for finding a maximal independent set in a linear hypergraph, J. Algorithms 25, 2 (1997) 311-320. ⇒142; · Zbl 0887.68048
[130] D. Maier, Minimum covers in the relational data base model, J. Assoc. Comp. Mach. 27 (1980) 664-674. ⇒142; · Zbl 0466.68085
[131] K. Markström, A. Ruciński, Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees, Europ. J. Combin. 32, 5 (2011) 677-687. ⇒141; · Zbl 1229.05231
[132] S. Micali, V.V. Vazirani, An O( √ VE) algorithm for finding maximum matching in general graphs, Proc. 21st Annual IEEE Symposium on Foundations of Computer Science (1980) 17-27. ⇒141;
[133] K. Mulmuley, U.V. Vazirani, V.V. Vazirani, Matching is as easy as matrix inversion, Combinatorica 7, 1 (1987) 105-114. ⇒141; · Zbl 0632.68041
[134] V. Nikiforov, An analytic theory of extremal hypergraph problems, arXiv:1305.1073, 2013, 31 pages. ⇒142;
[135] F. Olejník, On total matching numbers and total covering numbers for k-uniform hypergraphs. Math. Slovaca 34, 3 (1984), 319-328. ⇒141; · Zbl 0608.05062
[136] F. Olejník, On edge independence numbers and edge covering numbers of kuniform hypergraph, Math. Slovaca 39, 1 (1989) 21-26. ⇒138, 139, 140; · Zbl 0736.05058
[137] L. özkahiya, M. E. Young, Anti-Ramsey number of matchings in hypergraphs, Discrete Math., 313, 20 (2013), 2359-2364. ⇒141; · Zbl 1281.05111
[138] S. Pirzada, Hypertournaments-scores, losing scores, total scores and degrees. J. Combin. Math. Combin. Comput. 84 (2013) 99-112. ⇒139; · Zbl 1274.05197
[139] S. Pirzada, G. Zhou, On k-hypertournament losing scores, Acta Univ. Sapientiae, Informatica 2, 1 (2010) 5-9. ⇒139; · Zbl 1217.05102
[140] S. Pirzada, G. Zhou, A. Iványi, Score lists in multipartite hypertournaments, Acta Univ. Sapientiae, Informatica 2, 2 (2010) 184-193. ⇒139; · Zbl 1220.05082
[141] K. Plociennik, Approximating independent set and coloring in random uniform hypergraphs. In: Mathematical Foundations of Computer Science (2008), Lecture Notes in Comput. Sci. 5162, Springer, Berlin, 2008, 539-550. ⇒141; · Zbl 1173.05341
[142] M. D. Plummer, Matching theory-a sampler: from Dénes König to the present, Discrete Math. 100 (1992) 172-219. ⇒141; · Zbl 0774.05080
[143] A. Pruchnewski, On the domination number of graphs, Discrete Math., 251, 1-3 (2002) 129-136. ⇒137; · Zbl 0999.05083
[144] J. Qian, Enumeration of unlabeled uniform hypergraphs, Electronic J. Combin 20, 1 (2013), P46, 10 pages ⇒139; · Zbl 1266.05067
[145] J. Qian, Enumeration of unlabeled uniform hypergraphs. Discrete Math. 326 (2014), 66-74. ⇒139; · Zbl 1288.05128
[146] V. Rödl, A. Ruci´ski, M. Schacht, E. Szemerédi, A note on perfect matchings in uniform hypergraphs with large minimum collective degree, Comment. Math. Univ. Carolin. 49, 4 (2008) 633-636. ⇒141; · Zbl 1212.05215
[147] V. Rödl, A. Ruciński, E. Szemerédi, Perfect matchings in uniform hypergraphs with large minimum degree, Europ. J. Combin. 27 (2006) 1333-1349. ⇒141; · Zbl 1104.05051
[148] V. Rödl, A. Ruciński, E. Szemerédi, Perfect matchings in large uniform hypergraphs with large minimum collective degree, J. Combin. Theory Ser. A 116, 3 (2009), 613-636. ⇒141; · Zbl 1214.05130
[149] S. Sakai, M. Mitsunori, K. Yamazaki, A note on greedy algorithms for the maximum weighted independent set problem. Discrete Appl. Math 126, 2-3 (2003) 313-322. ⇒136; · Zbl 1013.90108
[150] S. M. Selkow, A probabilistic lower bound on the independence number of graphs. Discrete Math. 132 (1994) 363-365. ⇒134, 135; · Zbl 0810.05039
[151] H. Shachnai, A. Srinivasan, Finding large independent sets in graphs and hypergraphs. SIAM J. Discrete Math. 18, 3 (2004/05) 488-500. ⇒141; · Zbl 1069.05057
[152] J. Shearer, A note on the independence number of triangle-free graphs, Discrete Math. 46 (1983) 83-87. ⇒134, 136, 141, 145; · Zbl 0516.05053
[153] J. Spencer, Turán’s theorem for k-graphs, Discrete Math. 2 (1972) 183-186. ⇒ 136; · Zbl 0237.05116
[154] E. Szymańska, The complexity of 2-coloring and strong coloring in uniform hypergraphs of high minimum degre, Discrete Math. Theor. Comput. Sci. 15, 3 (2013) 121-137. ⇒141, 142; · Zbl 1281.68137
[155] R. E. Tarjan, A. E. Trojanowski, Finding a maximum independent set, SIAM J. Comput. 6, 3 (1977) 537-546. ⇒133, 138, 141; · Zbl 0357.68035
[156] T. Thiele, A lower bound on the independence number of arbitrary hypergraphs, J. Graph Theory 30, 3 (1999) 213-221. ⇒135; · Zbl 0926.05022
[157] A. Treglown, Y. Zhao, Exact minimum degree thresholds for perfect matchings in uniform hypergraphs, J. Combin. Theory Ser. A 119, 7 (2012) 1500-1522. ⇒141, 142; · Zbl 1305.05194
[158] A. Treglown, Y. Zhao, Exact minimum degree thresholds for perfect matchings in uniform hypergraphs II., J. Combin. Theory Ser. A 120, 7 (2013) 1463-1482. ⇒141, 142; · Zbl 1314.05168
[159] P. Turán, On the theory of graphs, Colloq. Math. 3 (1954) 19-30. ⇒133, 134; · Zbl 0055.17004
[160] Zs. Tuza, Extensions of Gallai’s graph covering theorems for uniform hypergraphs, J. Combin. Theory, Series B 52, 1 (1991) 92-96. ⇒139, 142; · Zbl 0758.05070
[161] V. V. Vazirani, A theory of alternating paths and blossoms for proving correctness of the O( √ VE) maximum matching algorithm, Combinatorica 14, 1 (1994) 71-109. ⇒133; · Zbl 0806.05058
[162] V. V. Vazirani, An improved definition of blossoms and a simpler proof of the MV matching algorithm, arXiv:1210.4594, 2013, 32 pages. ⇒133;
[163] A. Vietri, The complexity of arc-colorings for directed hypergraphs, Discrete Appl. Math 143,1-3 (2004) 266-271. ⇒140; · Zbl 1125.05308
[164] C. Wang, G. Zhou, Note on the degree sequences of k-hypertournaments, Note on the degree sequences of k-hypertournaments, Discrete Math. 308, 11 (2008) 2292-2296. ⇒139; · Zbl 1140.05044
[165] V. Wei, A lower bound on the stability number of a simple graph, Bell Laboratories Technical Memorandum, 1981, No. 81-11217-9. ⇒134;
[166] E. W. Weisstein, Independent Edge Set. Downloaded 9 May 2014. ⇒133;
[167] Wikipedia, Independent Set. Downloaded 9 May 2014. ⇒133, 138;
[168] R. Yuster, Finding and counting cliques and independent sets in r-uniform hypergraphs. Inf. Processing Letters 99, 4 (2006) 130-134. ⇒141; · Zbl 1184.05088
[169] R. Yuster, Maximum matching in regular and almost regular graphs, Algorithmica 66, 1 (2013) 87-92. ⇒141, 142; · Zbl 1263.05081
[170] G. Zhou, Y. Li, Independence numbers of hypergraphs with sparse neighborhoods, Europ. J. Combin. 25, 3 (2004) 355-362. ⇒134, 140, 141, 142; · Zbl 1034.05038
[171] G. Zhou, S. Pirzada, Degree sequence of oriented k-hypergraphs, J. Appl. Math. Comput. 27, 1-2 (2008) 149158. ⇒139; · Zbl 1160.05042
[172] G. Zhou, T. Yao, K. Zhang, On score sequences of k-hypertournaments, Europ. J. Combin. 21, 8 (2000) 993-1000. ⇒139; · Zbl 0966.05037
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.