On the number of independent sets in simple hypergraphs. (English. Russian original) Zbl 1390.05156
Math. Notes 103, No. 1, 33-41 (2018); translation from Mat. Zametki 103, No. 1, 38-48 (2018).
Summary: Extremal problems on the number of \(j\)-independent sets in uniform simple hypergraphs are studied. Nearly optimal results on the maximum number of independent sets for the class of simple regular hypergraphs and on the minimum number of independent sets for the class of simple hypergraphs with given average degree of vertices are obtained.
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C65 | Hypergraphs |
References:
| [1] | Dainyak, A. B.; Sapozhenko, A. A., Independent sets in graphs, Diskretn. Mat., 28, 44-77, (2016) · Zbl 1352.05144 · doi:10.4213/dm1357 |
| [2] | Alon, N., Independent sets in regular graphs and sum-free subsets of finite groups, Israel J. Math., 73, 247-256, (1991) · Zbl 0762.05050 · doi:10.1007/BF02772952 |
| [3] | Kahn, J., An entropy approach to the hard-core model on bipartite graphs, Combin. Probab. Comput., 10, 219-237, (2001) · Zbl 0985.60088 · doi:10.1017/S0963548301004631 |
| [4] | Zhao, Y., The number of independent sets in a regular graph, Combin. Probab. Comput., 19, 315-320, (2010) · Zbl 1215.05140 · doi:10.1017/S0963548309990538 |
| [5] | Copper, J.; Mubayi, D., Counting independent sets in triangle-free graphs, Proc. Amer. Math. Soc., 142, 3325-3334, (2014) · Zbl 1300.05169 · doi:10.1090/S0002-9939-2014-12068-5 |
| [6] | Cutler, J.; Radcliffe, A. J., Hypergraph independent sets, Combin. Probab. Comput., 22, 9-20, (2013) · Zbl 1257.05104 · doi:10.1017/S0963548312000454 |
| [7] | Ordentlich, E.; Roth, R., Independent sets in regular hypergraphs and multidimensional runlength-limited constraints, SIAMJ. Discrete Math., 17, 615-623, (2004) · Zbl 1055.05108 · doi:10.1137/S0895480102419767 |
| [8] | Saxton, D.; Thomason, A., Hypergraph containers, Invent. Math., 201, 925-992, (2015) · Zbl 1320.05085 · doi:10.1007/s00222-014-0562-8 |
| [9] | Copper, J.; Dutta, K.; Mubayi, D., Counting independent sets in hypergraphs, Combin. Probab. Comput., 23, 539-550, (2014) · Zbl 1304.05105 · doi:10.1017/S0963548314000182 |
| [10] | Duke, R.; Lefmann, H.; Rödl, V., On uncrowded hypergraphs, Random Structures Algorithms, 6, 209-213, (1995) · Zbl 0822.05051 · doi:10.1002/rsa.3240060208 |
| [11] | O. Ore, Theory of Graphs, in Amer. Math. Soc. Colloquium Publications (Amer. Math. Soc., Providence, RI, 1967; Nauka, Moscow, 1980), Vol. 38. |
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.
