On vertex independence number of uniform hypergraphs

Tariq A. Chishti; Guofei Zhou; Shariefuddin Pirzada; Antal Iványi

doi:10.2478/ausi-2014-0022

Abstract

Let H be an r-uniform hypergraph with r ≥ 2 and let α(H) be its vertex independence number. In the paper bounds of α(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.

References

[1] V. Abraham, Independence in hypergraphs. J. Indian Math. Soc. (N.S.), 78, 1-4 (2011) 1-7. ⇒141
Search in Google Scholar
[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
Search in Google Scholar
[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
Search in Google Scholar
[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, 14110.1007/978-3-642-02927-1_3
Search in Google Scholar
[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, 14110.1016/j.tcs.2012.11.025
Search in Google Scholar
[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. ⇒13410.1007/BF02579451
Search in Google Scholar
[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. ⇒13410.1016/S0195-6698(81)80014-5
Search in Google Scholar
[8] M. Ajtai, J. Komlós and E. Szemerédi, A note on Ramsey numbers, J. Combin. Theory Ser. A 29 (1980) 354-360. ⇒13410.1016/0097-3165(80)90030-8
Search in Google Scholar
[9] A. Alon, A fast and simple randomized parallel algorithm for the maximal independent set problem, J. Algorithms 7, 4 (1986) 567-583. ⇒133, 13810.1016/0196-6774(86)90019-2
Search in Google Scholar
[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, 14210.1016/j.jcta.2012.02.004
Search in Google Scholar
[11] N. Alon, J. H. Spencer, The Probabilistic Method, Wiley-Interscience, New York, 1992. ⇒134
Search in Google Scholar
[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. ⇒14110.1007/978-3-540-48413-4_3
Search in Google Scholar
[13] N. Alon, R. Yuster, On a hypergraph matching problem, Graphs Comb. 21 (2005) 377-384. ⇒14210.1007/s00373-005-0628-x
Search in Google Scholar
[14] E. Angel, R. Campigotto, C. Laforest, A new lower bound on the independence number of graphs, Discrete Appl. 161, 6 (2013) 847-852. ⇒13410.1016/j.dam.2012.10.001
Search in Google Scholar
[15] G. Ausiello, A. D’Atri, D. Sacc`a, Minimal representation of directed hypergraphs, SIAM J. Comput. 15 (1986) 418-431. ⇒13910.1137/0215029
Search in Google Scholar
[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
Search in Google Scholar
[17] J. Balogh, J. Butterfield, P. Hu, J. Lenz, D. Mubayi, On the chromatic thresholds of hypergraphs arXiv:1103.1416, 2013, 37 pages. ⇒142
Search in Google Scholar
[18] J. Balogh, R. Morris, W. Samotij, Independent sets in hypergraphs, arXiv:1204.6530, 2013, 42 pages. ⇒136
Search in Google Scholar
[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
Search in Google Scholar
[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
Search in Google Scholar
[21] M. Behrisch, A. Coja-Oghlan, M. Kang, The asymptotic number of connected d-uniform hypergraphs, Combin. Probab. Comput. 23, 3 (2014) 367-385. ⇒13910.1017/S0963548314000029
Search in Google Scholar
[22] C. Berge, The Theory of Graphs and its Applications, Wiley, London, 1964. ⇒ 137
Search in Google Scholar
[23] E. Berger, R. Ziv, A note on the edge cover number and independence number in hypergraphs, Discrete Math. 308, 12 (2008) 2649-2654. ⇒14110.1016/j.disc.2007.05.006
Search in Google Scholar
[24] C. Bertram-Kretzberg, H. Lefmann, The algorithmic aspects of uncrowded hypergraphs. SIAM J. Comput. 29, 1 (1999) 201-230. ⇒14210.1137/S0097539797323716
Search in Google Scholar
[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. ⇒14110.1016/j.disc.2004.05.003
Search in Google Scholar
[26] V. Blinovsky, Fractional matching in hypergraphs, arXiv:1311.2671, 2013, 6 pages. ⇒141
Search in Google Scholar
[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. ⇒14110.1093/qmath/27.1.25
Search in Google Scholar
[28] A. Bonato, J. I. Brown, D. Mitsche, P. Pralat, Independence densities of hypergraphs, arXiv:1308.2837, 2013, 16 pages. ⇒141
Search in Google Scholar
[29] A. Bonato, J. I. Brown, D. Mitsche, P. Pralat, Independence densities of hypergraphs, Europ. J. Combin. 40 (2014) 124-136. ⇒14110.1016/j.ejc.2014.03.001
Search in Google Scholar
[30] R. Boppana, M. M. Halldórson, Approximating maximum independent set by excluding subsets, BIT, 32 (1992) 160-196. ⇒133, 138
Search in Google Scholar
[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. ⇒14110.1002/rsa.20204
Search in Google Scholar
[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. ⇒14110.1007/978-3-540-24698-5_52
Search in Google Scholar
[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. ⇒14110.1142/S0129626400000251
Search in Google Scholar
[34] M. Borowiecki, D. Michalak, The independence graphs of hypergraphs and middle graphs, Discuss. Math. 7 (1985) 31-37. ⇒141
Search in Google Scholar
[35] Cs. Bujtás, Zs. Tuza, Uniform mixed hypergraphs: The possible numbers of colors, Graphs Combin., 24 (2008) 1-12. ⇒14210.1007/s00373-007-0765-5
Search in Google Scholar
[36] Y. Caro, New results on the independence number, Technical Report, 1979, Tel- Aviv University. ⇒134
Search in Google Scholar
[37] Y. Caro, A. Hansberg, New approach to the k-independence number of a graph. Electron. J. Combin. 20, 1 (2013) #P33, 17 pages. ⇒13510.37236/2646
Search in Google Scholar
[38] Y. Caro, Zs. Tuza, Improved lower bounds on k-independence, J. Graph Theory 15 (1991) 99-107. ⇒13510.1002/jgt.3190150110
Search in Google Scholar
[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. ⇒14210.2172/764804
Search in Google Scholar
[40] G. Chartrand, S. Schuster, On the independence number of complementary graphs, Trans. New York Acad. Sci., Series II 36, 3 (1974) 247-251. ⇒13910.1111/j.2164-0947.1974.tb01571.x
Search in Google Scholar
[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, 13710.1007/s00373-011-1040-3
Search in Google Scholar
[42] M. Chellali, N. J. Rad, On k-independence critical graphs. Australas. J. Combin. 53 (2012) 289-298. ⇒135
Search in Google Scholar
[43] E. J. Cockayne, S. T. Hedetniemi, R. Laskar, Gallai theorems for graphs, hypergraphs and set systems, Discrete Math. 72 (1988) 35-47. ⇒14210.1016/S0167-5060(08)70769-6
Search in Google Scholar
[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
Search in Google Scholar
[45] J. Cutler, A. J. Radcliffe, Hypergraph independent sets, Combin. Probab. Comput. 22, 1 (2013) 9-20. ⇒14110.1017/S0963548312000454
Search in Google Scholar
[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. ⇒14110.1016/j.dam.2010.09.006
Search in Google Scholar
[47] A. Dudek, A. Frieze, A. Ruciński, M. ˇSileikis, Approximate counting of regular hypergraphs, Inf. Processing Letters, 113, 1921 (2013) 785-788. ⇒139, 14110.1016/j.ipl.2013.07.018
Search in Google Scholar
[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. ⇒13810.1137/110839023
Search in Google Scholar
[49] J. Edmonds, Paths, trees, and flowers, Canadian J. Math. 17 (1965) 449-467. ⇒133, 138, 14110.4153/CJM-1965-045-4
Search in Google Scholar
[50] J. Edmonds, Maximal matching and a polyhedron with 0, 1-vertices, J. Research Nat. Bureau Standards B-69 (1965) 125-130. ⇒133, 138, 14110.6028/jres.069B.013
Search in Google Scholar
[51] A. Eustis, Hypergraph Independence Numbers, PhD Thesis. University of California, San Diego. 2013. 123 pages. ⇒138
Search in Google Scholar
[52] A. Eustis, J. Verstra¨ete, On the independence number of Steiner systems, Combinatorics, Prob. Comp. 22, 2 (2013) 241-252. ⇒13810.1017/S0963548312000557
Search in Google Scholar
[53] S. Fajtlowicz, Independence, clique size and maximum degree, Combinatorica 4 (1984), 35-38. ⇒13610.1007/BF02579154
Search in Google Scholar
[54] O. Favoron, A. Hansberg, L. Volkmann, On k-domination and minimum degree in graphs, J. Graph Theory 57, 1 (2008) 33-40. ⇒135, 13710.1002/jgt.20279
Search in Google Scholar
[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, 14210.1016/S0166-218X(02)00462-6
Search in Google Scholar
[56] P. Frankl, Improved bounds for Erdős matching conjecture, J. Combin. Theory Ser. A 120, 5 (2013) 1068-1072. ⇒14110.1016/j.jcta.2013.01.008
Search in Google Scholar
[57] P. Frankl, T. Luczak, K.Mieczkowska, On matchings in hypergraphs. Electron. J. Combin. 19, 2 (2012), #P42, 5 pages. ⇒14110.37236/2176
Search in Google Scholar
[58] P. Frankl, V. Rödl, Some Ramsey-Turn type results for hypergraphs. Combinatorica 8, 4 (1988) 323-332. ⇒14210.1007/BF02189089
Search in Google Scholar
[59] P. Frankl, V. Rödl, The uniformity lemma for hypergraphs, Graphs Combin. 8 (1992) 309-312. ⇒14210.1007/BF02351586
Search in Google Scholar
[60] M. Frieze, On the independence number of random graphs, Discrete Math. 81, 2 (1990) 171-175. ⇒13610.1016/0012-365X(90)90149-C
Search in Google Scholar
[61] Z. FÜredi, Matchings and covers in hypergraphs, Graphs Combin. 4 (1988) 115-206. ⇒14110.1007/BF01864160
Search in Google Scholar
[62] Z. Füredi, The number of maximal independent sets in connected graphs, J. Graph Theory, 11, 4 (1995) 463-470. ⇒13710.1002/jgt.3190110403
Search in Google Scholar
[63] Z. FÜredi, Linear trees in uniform hypergraphs, Europ. J. Combin. 35 (2014) 264-272. ⇒14210.1016/j.ejc.2013.06.022
Search in Google Scholar
[64] Z. Füredi, M. Ruszinkó, Uniform hypergraphs containing no grids, Adv. Math. 240 (2013) 302-324. ⇒14210.1016/j.aim.2013.03.009
Search in Google Scholar
[65] H. M. Gabow, An efficient implementation of Edmonds’ algorithm for maximum matching on graphs, J. ACM 23, 2 (1976) 221-234. ⇒14110.1145/321941.321942
Search in Google Scholar
[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
Search in Google Scholar
[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
Search in Google Scholar
[68] G. Gallo, G. Longo, S. Nguyen, S. Pallottino, Directed hypergraphs and applications, Discrete Appl. Math 42, 2-3 (1993) 177-201. ⇒140, 14210.1016/0166-218X(93)90045-P
Search in Google Scholar
[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. ⇒13610.1007/978-3-540-92248-3_16
Search in Google Scholar
[70] C. Greenhill, The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Comput. Complexity 9, 1 (2000) 52-72. ⇒14110.1007/PL00001601
Search in Google Scholar
[71] C. Greenhill, A. Rucinski, N. C. Wormald, Random hypergraph processes with degree restrictions, Graphs Combin. 20 (2004) 319-332. ⇒14110.1007/s00373-004-0571-2
Search in Google Scholar
[72] J. Griggs, Lower bounds on the independence number in terms of the degrees, J. Comb. Theory, Ser. B 34 (1983) 22-39. ⇒134, 14510.1016/0095-8956(83)90003-5
Search in Google Scholar
[73] J. L. Gross, J. Yellen, P. Zhang, Handbook of Graph Theory, CRC Press, Boca Raton, FL, 2014. ⇒133, 13810.1201/b16132
Search in Google Scholar
[74] D. Gunopolus, R. Khardon, H. Mannila, H. Toivonen, Data mining, hypergraph traversals, and machine learning. Proc. PODS’97, 1997, pp. 209-2016. ⇒14210.1145/263661.263684
Search in Google Scholar
[75] M. M. Halldórson, Approximations of weighted independent set and hereditary subset problems, J. Graph Algorithms Appl. 4, 1 (2000) 1-16. ⇒13610.7155/jgaa.00020
Search in Google Scholar
[76] M. M. Halldórson, E. Losievskaja, Independent sets in bounded-degree hypergraphs, Discrete Appl. Math 157, 8 (2009) 1773-1786. ⇒14110.1016/j.dam.2008.11.013
Search in Google Scholar
[77] J. Han, Near perfect matchings in k-uniform hypergraphs, arXiv:1404.1136, 2014, 7 pages. ⇒141
Search in Google Scholar
[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, 14210.1137/080729657
Search in Google Scholar
[79] A. Hansberg, R. Pepper, On k-domination and j-independence in graphs. Discrete Appl. Math 161, 10-11 (2013) 1472-1480. ⇒135, 136, 13710.1016/j.dam.2013.02.008
Search in Google Scholar
[80] J. Harant, A lower bound on independence number of a graph, Discrete Math. 188, 13 (1998) 239243. ⇒13410.1016/S0012-365X(98)00048-X
Search in Google Scholar
[81] J. Harant, A lower bound on independence in terms of degrees, Discrete Appl. Mathematics 159, 10 (2011) 966-970. ⇒134, 13510.1016/j.dam.2011.03.003
Search in Google Scholar
[82] J. Harant, A. Pruchnewski, M. Voigt, On dominating sets and independent sets of graphs, Combinatorics, Prob. Comp. 8, 6 (1999) 547-553. ⇒13710.1017/S0963548399004034
Search in Google Scholar
[83] J. Harant, D. Rautenbach, Independence in connected graphs. Discrete Appl. Math 159, 1 (2011) 79-86. ⇒13510.1016/j.dam.2010.08.029
Search in Google Scholar
[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. ⇒13510.1016/S0012-365X(00)00298-3
Search in Google Scholar
[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. ⇒13510.7151/dmgt.1335
Search in Google Scholar
[86] M. A. Henning, C. Löwenstein, D. Rautenbach, Independent sets and matchings in subcubic graphs. Discrete Math., 312, 11 (2012) 1900-1910. ⇒14110.1016/j.disc.2012.03.002
Search in Google Scholar
[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. ⇒13610.37236/3601
Search in Google Scholar
[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. ⇒14110.1007/s00373-007-0757-5
Search in Google Scholar
[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, 14210.1002/jgt.21640
Search in Google Scholar
[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. ⇒ 14110.1007/BFb0055806
Search in Google Scholar
[91] J. E. Hopcroft, R. M. Karp, An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput., 2 (1973) 225-231. ⇒14110.1137/0202019
Search in Google Scholar
[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, 14210.1017/S096354831100068X
Search in Google Scholar
[93] D. S. Johnson, M. Yannakakis, On generating all maximal independent sets, Inf. Processing Letters 27, 3 (1988) 119-123. ⇒133, 138, 141, 14210.1016/0020-0190(88)90065-8
Search in Google Scholar
[94] T. Johnston, L. Lu, Turn problems on non-uniform hypergraphs, arXiv:1301.1870, 2013. ⇒14210.37236/3901
Search in Google Scholar
[95] T. Johnston, L. Lu, Strong jumps and Lagrangians of non-uniform hypergraphs, arXiv:1403.1220, 2014. ⇒14210.37236/3901
Search in Google Scholar
[96] B. K. Jose, Zs. Tuza, Hypergraph domination and strong independence. Appl. Anal. Discrete Math. 3, 2 (2009) 347-358. ⇒14210.2298/AADM0902347J
Search in Google Scholar
[97] E. Jucovič, F. Olejník, On chromatic and achromatic numbers of uniform hypergraphs, Časopis Pĕstováni Matematiky, 99 (1974) 123-130. ⇒139, 14210.21136/CPM.1974.117834
Search in Google Scholar
[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. ⇒13610.1016/j.dam.2008.08.027
Search in Google Scholar
[99] M. Karonski, T. Luczak, The number of connected sparsely edged uniform hypergraphs, Discrete Math. 171, 1-3 (1997) 153-167. ⇒14210.1016/S0012-365X(96)00076-3
Search in Google Scholar
[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. ⇒14110.1145/100216.100262
Search in Google Scholar
[101] R. M. Karp, A. Widgerson, A fast parallel algorithm for the maximal independent set problem, J. ACM 32, 4 (1985) 762-773. ⇒133, 13810.1145/4221.4226
Search in Google Scholar
[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
Search in Google Scholar
[103] G. O. H. Katona, Continuous versions of some extremal hypergraph problems II, Acta Math. Acad. Sci. Hungar. 35 (1980) 67-77. ⇒14210.1007/BF01896826
Search in Google Scholar
[104] P. Keevash, F. Knox, R. Mycroft, Polynomial-time perfect matchings in dense hypergraphs, arXiv:1307.2608, 2013. 62 pages. ⇒14110.1145/2488608.2488647
Search in Google Scholar
[105] P. Keevash, R. Mycroft, A geometric theory for hypergraph matching, arXiv:1108.1757, 2013, 101 pages. ⇒14110.1007/978-88-7642-475-5_23
Search in Google Scholar
[106] P. Keevash, B. Sudakov, On a hypergraph Turán problem of Frankl, Combinatorica 25, 6 (2005) 673-706. ⇒14210.1007/s00493-005-0042-2
Search in Google Scholar
[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, 14210.1145/129712.129745
Search in Google Scholar
[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. ⇒14110.1142/S0129626407002934
Search in Google Scholar
[109] I. Khan, Perfect matchings in 3-uniform hypergraphs with large vertex degree. SIAM J. Discrete Math. 27, 2 (2013) 1021-1039. ⇒14110.1137/10080796X
Search in Google Scholar
[110] M. A. Khan, S. , K. K. Kayibi, Scores, inequalities and regular hypertournaments, Math. Inequal. Appl. 15, 2 (2012), 343-351. ⇒13910.7153/mia-15-28
Search in Google Scholar
[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. ⇒14210.1006/jcta.2001.3217
Search in Google Scholar
[112] V. Kolmogorov, V. Blossom, A new implementation of a minimum cost perfect matching algorithm, Math. Programming Pomp. 1 (2009) 43-67. ⇒14110.1007/s12532-009-0002-8
Search in Google Scholar
[113] D. Kőnig, Graphs and matrices (Hungarian), Matematikai és Fizikai Lapok 38 (1931) 116-119. ⇒141
Search in Google Scholar
[114] A. Kostochka, D. Mubayi, J. Verstra¨ete, On independent sets in hypergraphs, Random Structures Algorithms 44, 2 (2014) 224-239. ⇒14210.1002/rsa.20453
Search in Google Scholar
[115] M. Krivelevich, Approximate set covering in uniform hypergraphs, J. Algorithms 25, 1 (1997) 118-143. ⇒14210.1006/jagm.1997.0872
Search in Google Scholar
[116] M. Krivelevich, R. Nathaniel, B. Sudakov, Approximating coloring and maximum independent sets in 3-uniform hypergraphs, J. Algorithms 41, 1 (2001) 99-113. ⇒14210.1006/jagm.2001.1173
Search in Google Scholar
[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. ⇒14210.1016/j.jctb.2006.02.004
Search in Google Scholar
[118] D. KÜhn, D. Osthus, A. Treglown, Matchings in 3-uniform hypergraphs, J. Combinatorial Theory Series B 103 (2013) 291-305. ⇒14110.1016/j.jctb.2012.11.005
Search in Google Scholar
[119] D. KÜhn, D. Osthus, T. Townsend, Fractional and integer matchings in uniform hypergraphs, Europ. J. Combin. 38 (2014) 83-96. ⇒14110.1016/j.ejc.2013.11.006
Search in Google Scholar
[120] R. Laskar, B. Auerbach, On complementary graphs with no isolated vertices, Discrete Math. 24, 2 (1978) 113-118. ⇒14010.1016/0012-365X(78)90189-9
Search in Google Scholar
[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, 13810.1137/0209042
Search in Google Scholar
[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
Search in Google Scholar
[123] Y. Li, C. Rousseau, On book-complete graph Ramsey numbers, J. Comb. Theory, Ser. B 68, 1 (1996) 36-44. ⇒14210.1006/jctb.1996.0055
Search in Google Scholar
[124] Y. Li, C. Rousseau, W. Zang, Asymptotic upper bound for Ramsey functions, Graphs Combin., 17 (2001) 123-128. ⇒14210.1007/s003730170060
Search in Google Scholar
[125] Y. Li, W. Zang, Differential methods for finding independent sets in hypergraphs, SIAM J. Discrete Math. 20 (2006) 96-104. ⇒141, 14210.1137/S0895480104442571
Search in Google Scholar
[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
Search in Google Scholar
[127] L. Lovász, M. D. Plummer, Matching Theory, North Holland, Amsterdam, 1986. ⇒141
Search in Google Scholar
[128] M. Luby, A simple parallel algorithm for the maximal independent set problem, SIAM J. Comput. 15, 1 (1976) 1036-1053. ⇒133, 13810.1137/0215074
Search in Google Scholar
[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. ⇒14210.1006/jagm.1997.0884
Search in Google Scholar
[130] D. Maier, Minimum covers in the relational data base model, J. Assoc. Comp. Mach. 27 (1980) 664-674. ⇒14210.1145/322217.322223
Search in Google Scholar
[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. ⇒14110.1016/j.ejc.2011.02.001
Search in Google Scholar
[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. ⇒14110.1109/SFCS.1980.12
Search in Google Scholar
[133] K. Mulmuley, U.V. Vazirani, V.V. Vazirani, Matching is as easy as matrix inversion, Combinatorica 7, 1 (1987) 105-114. ⇒14110.1007/BF02579206
Search in Google Scholar
[134] V. Nikiforov, An analytic theory of extremal hypergraph problems, arXiv:1305.1073, 2013, 31 pages. ⇒142
Search in Google Scholar
[135] F. Olejník, On total matching numbers and total covering numbers for k-uniform hypergraphs. Math. Slovaca 34, 3 (1984), 319-328. ⇒141
Search in Google Scholar
[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
Search in Google Scholar
[137] L. özkahiya, M. E. Young, Anti-Ramsey number of matchings in hypergraphs, Discrete Math., 313, 20 (2013), 2359-2364. ⇒14110.1016/j.disc.2013.06.015
Search in Google Scholar
[138] S. Pirzada, Hypertournaments-scores, losing scores, total scores and degrees. J. Combin. Math. Combin. Comput. 84 (2013) 99-112. ⇒139
Search in Google Scholar
[139] S. Pirzada, G. Zhou, On k-hypertournament losing scores, Acta Univ. Sapientiae, Informatica 2, 1 (2010) 5-9. ⇒139
Search in Google Scholar
[140] S. Pirzada, G. Zhou, A. Iványi, Score lists in multipartite hypertournaments, Acta Univ. Sapientiae, Informatica 2, 2 (2010) 184-193. ⇒139
Search in Google Scholar
[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. ⇒14110.1007/978-3-540-85238-4_44
Search in Google Scholar
[142] M. D. Plummer, Matching theory-a sampler: from Dénes König to the present, Discrete Math. 100 (1992) 172-219. ⇒14110.1016/0012-365X(92)90640-2
Search in Google Scholar
[143] A. Pruchnewski, On the domination number of graphs, Discrete Math., 251, 1-3 (2002) 129-136. ⇒13710.1016/S0012-365X(01)00334-X
Search in Google Scholar
[144] J. Qian, Enumeration of unlabeled uniform hypergraphs, Electronic J. Combin 20, 1 (2013), P46, 10 pages ⇒13910.37236/2766
Search in Google Scholar
[145] J. Qian, Enumeration of unlabeled uniform hypergraphs. Discrete Math. 326 (2014), 66-74. ⇒13910.1016/j.disc.2014.03.005
Search in Google Scholar
[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
Search in Google Scholar
[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. ⇒14110.1016/j.ejc.2006.05.008
Search in Google Scholar
[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. ⇒14110.1016/j.jcta.2008.10.002
Search in Google Scholar
[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. ⇒13610.1016/S0166-218X(02)00205-6
Search in Google Scholar
[150] S. M. Selkow, A probabilistic lower bound on the independence number of graphs. Discrete Math. 132 (1994) 363-365. ⇒134, 13510.1016/0012-365X(93)00102-B
Search in Google Scholar
[151] H. Shachnai, A. Srinivasan, Finding large independent sets in graphs and hypergraphs. SIAM J. Discrete Math. 18, 3 (2004/05) 488-500. ⇒14110.1137/S0895480102419731
Search in Google Scholar
[152] J. Shearer, A note on the independence number of triangle-free graphs, Discrete Math. 46 (1983) 83-87. ⇒134, 136, 141, 14510.1016/0012-365X(83)90273-X
Search in Google Scholar
[153] J. Spencer, Turán’s theorem for k-graphs, Discrete Math. 2 (1972) 183-186. ⇒ 13610.1016/0012-365X(72)90084-2
Search in Google Scholar
[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, 14210.46298/dmtcs.596
Search in Google Scholar
[155] R. E. Tarjan, A. E. Trojanowski, Finding a maximum independent set, SIAM J. Comput. 6, 3 (1977) 537-546. ⇒133, 138, 14110.1137/0206038
Search in Google Scholar
[156] T. Thiele, A lower bound on the independence number of arbitrary hypergraphs, J. Graph Theory 30, 3 (1999) 213-221. ⇒13510.1002/(SICI)1097-0118(199903)30:3<;213::AID-JGT6>3.0.CO;2-Q
Search in Google Scholar
[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, 14210.1016/j.jcta.2012.04.006
Search in Google Scholar
[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, 14210.1016/j.jcta.2013.04.008
Search in Google Scholar
[159] P. Turán, On the theory of graphs, Colloq. Math. 3 (1954) 19-30. ⇒133, 13410.4064/cm-3-1-19-30
Search in Google Scholar
[160] Zs. Tuza, Extensions of Gallai’s graph covering theorems for uniform hypergraphs, J. Combin. Theory, Series B 52, 1 (1991) 92-96. ⇒139, 14210.1016/0095-8956(91)90094-Z
Search in Google Scholar
[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. ⇒13310.1007/BF01305952
Search in Google Scholar
[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
Search in Google Scholar
[163] A. Vietri, The complexity of arc-colorings for directed hypergraphs, Discrete Appl. Math 143,1-3 (2004) 266-271. ⇒14010.1016/j.dam.2004.04.002
Search in Google Scholar
[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
Search in Google Scholar
[165] V. Wei, A lower bound on the stability number of a simple graph, Bell Laboratories Technical Memorandum, 1981, No. 81-11217-9. ⇒134
Search in Google Scholar
[166] E. W. Weisstein, Independent Edge Set. Downloaded 9 May 2014. ⇒133
Search in Google Scholar
[167] Wikipedia, Independent Set. Downloaded 9 May 2014. ⇒133, 138
Search in Google Scholar
[168] R. Yuster, Finding and counting cliques and independent sets in r-uniform hypergraphs. Inf. Processing Letters 99, 4 (2006) 130-134. ⇒14110.1016/j.ipl.2006.04.005
Search in Google Scholar
[169] R. Yuster, Maximum matching in regular and almost regular graphs, Algorithmica 66, 1 (2013) 87-92. ⇒141, 14210.1007/s00453-012-9625-7
Search in Google Scholar
[170] G. Zhou, Y. Li, Independence numbers of hypergraphs with sparse neighborhoods, Europ. J. Combin. 25, 3 (2004) 355-362. ⇒134, 140, 141, 14210.1016/j.ejc.2003.09.008
Search in Google Scholar
[171] G. Zhou, S. Pirzada, Degree sequence of oriented k-hypergraphs, J. Appl. Math. Comput. 27, 1-2 (2008) 149158. ⇒13910.1007/s12190-008-0047-2
Search in Google Scholar
[172] G. Zhou, T. Yao, K. Zhang, On score sequences of k-hypertournaments, Europ. J. Combin. 21, 8 (2000) 993-1000. ⇒13910.1006/eujc.2000.0393
Search in Google Scholar

On vertex independence number of uniform hypergraphs

Abstract

Paradigm

My account