Non-uniform Hypergraphs

Document Type : Research Paper


1 University of Qom

2 Department of Mathematics and Computer Science, University of Qom, Qom, IRAN.


The non-uniform hypergraph is the general hypergraph in which an edge can join any number of vertices. This makes them more applicable data structure than the uniform hypergraph and also, on the other hand, mathematical relations of the nonuniform hypergraph are usually complicated. In this paper, we study the non-uniform hypergraph more precisely and then analyze some of its spectral properties and compare them with those of the uniform hypergraph.


Main Subjects

     1. D. Achlioptas, T. Gouleakis and F. lliopoulos, Local computation algorithms for the lová sz local lemma, arXiv:1809.07910 (2018).
     2. A. Banerjee and A. Char, On the spectrum of directed uniform and non-uniform hypergraphs, arXiv:1710.06367 (2017).
     3. A. Banerjee, A. Char and B. Mondal, Spectra of general hypergraphs, Linear Algebra Appl. 518 (2017) 14−30.
     4. C. Bu, Y. Fan and J. Zhou, Laplacian and signless Laplacian Z-eigenvalues of uniform hypergraphs, Front. Math. China, 11 (2015) 1−10.
     5. C. Bu, J. Zhou and Y. Wei,  E-cospectral hypergraphs and some hypergraphs determined by their spectra, Linear Algebra Appl. 459 (2014) 397−403.
     6. S. R. Bulo and M. Pelillo, New bounds on the clique number of graphs based on spectral hypergraph theory, International Conference on Learning and Intelligent Optimization, Springer−Verlag, Berlin, (2009) 45−58.
     7. Z. Chen and L. Qi, Circulant tensors with applications to spectral hypergraph theory and stochastic process, JIMO 12 (2016) 1227−1247.
     8. K. C. Chang, K. Pearson, and T. Zhang, Perron-Frobenius theorem for nonnegative tensors. Commun. Math. Sci. 6 (2008) 507−520.
     9. J. Cooper and A. Dutle, Spectra of uniform hypergraphs, Linear Algebra Appl. 436 (2012) 3268−3292.
     10.J. Cooper and A. Dutle, Computing hypermatrix spectra with the Poisson product formula, Linear Multilinear Algebra 63 (2015) 956−970.
     11.R. Cui, W. Li and M. Ng, Primitive tensors and directed hypergraphs, Linear Algebra Appl. 471 (2015) 96−108.
     12.Y. Fan, Y. Tan, X. Peng and A. Liu, Maximizing spectral radii of uniform hypergraphs with few edges, Discuss. Math. Graph Theory 36 (2016) 845−856.
     13.S. Friedland, S. Gaubert and L. Han, Perron-Frobenius theorems for nonnegative multilinear forms and extension, Linear Algebra Appl. 438 (2013) 738−749.
     14.D. Ghoshdastidar and A. Dukkipati, Consistency of spectral partitioning of uniform hypergraphs under planted partition model, Adv. Neural Inf. Process. Sys. (2014) 397−405.
     15.D. Ghoshdastidar and A. Dukkipati, A Provable Generalized Tensor Spectral Method for Uniform Hypergraph Partitioning, Proceedings of the 32nd International Conference on Machine Learning, Lille, France (2015) 400−409.
     16.S. Hu and L. Qi, Algebraic connectivity of an even uniform hypergraph, J. Comb. Optim.  24 (2012) 564−579.
     17.S. Hu and L. Qi, The eigenvectors associated with the zero eigenvalues of the Laplacian and signless Laplacian tensors of a uniform hypergraph, Discrete Appl. Math. 169 (2014) 140−151.
     18.S. Hu and L. Qi, The Laplacian of a uniform hypergraph, J. Comb. Optim. 29 (2015) 331−366.
     19.S. Hu, L. Qi and J. Shao, Cored hypergraphs, power hypergraphs and their Laplacian eigenvalues, Linear Algebra Appl. 439 (2013) 2980−2998.
     20.S. Hu, L. Qi and J. Xie, The largest Laplacian and signless Laplacian H-eigenvalues of a uniform hypergraph, Linear Algebra Appl. 469 (2015) 1−27.
     21.L. Kang, V. Nikiforov and X. Yuan, The p-spectral radius of k-partite and k-chromatic uniform hypergraphs, Linear Algebra Appl. 478 (2015) 81−107.
     22.M. Khan and Y. Fan, On the spectral radius of a class of non-odd-bipartite even uniform hypergraphs, Linear Algebra Appl. 480 (2015) 93−106.
     23.M. Khan, Y. Fan and Y. Tan, The H-spectra of a class of generalized power hypergraphs, Discrete Math. 339 (2016) 1682−1689.
     24.L. Liu and L. Lu, The (p,q)-spectral radii of (r,s)-directed hypergraphs, arXiv:1804.08808 (2018).
     25.G. Li, L. Qi and G. Yu, The Z-eigenvalues of a symmetric tensor and its application to spectral hypergraph theory, Numer. Linear Algebra Appl. 20 (2013) 1001−1029.
     26.H. Li, J. Shao and L. Qi, The extremal spectral radii of k-uniform supertrees, J. Comb. Optim. 32 (2016) 741−764.
     27.Li. Wei, J. Cooper and A. Chang, Analytic connectivity of k-uniform hypergraphs, Linear Multilinear Algebra 65 (2017) 1247−1259.
     28.L. H. Lim, Singular values and eigenvalues of tensors: a variational approach. In: 1st IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, IEEE, (2005) 129−132.
     29.V. Nikiforov, Analytic methods for uniform hypergraphs, Linear Algebra Appl. 457 (2014) 455−535.
     30.V. Nikiforov, Some extremal problems for hereditary properties of graphs, Electro. J. Comb. 21 (2014) 1−17.
     31.K. Pearson, Spectral hypergraph theory of the adjacency hypermatrix and matroids, Linear Algebra Appl. 465 (2015) 176−187.
     32.K. Pearson and T. Zhang, Eigenvalues on the adjacency tensor of products of hypergraphs, Int. J. Contemp. Math. Sci. 8 (2013) 151−158.
     33.K. Pearson and T. Zhang, On spectral hypergraph theory of the adjacency tensor, Graphs Combin. 30 (2014) 1233−1248.
     34.K. Pearson, T. Zhang, The Laplacian tensor of a multi-hypergraph, Discrete Math. 338 (2015) 972−982.
     35.L. Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput. 40 (2005) 1302−1324.
     36.L. Qi, H^+-Eigenvalues of Laplacian and signless Lapaclian tensors, Commun. Math. Sci. 12 (2014) 1045−1064.
     37.L. Qi, J. Shao and Q. Wang, Regular uniform hypergraphs, s-cycles, s-paths and their largest Laplacian H-eigenvalues, Linear Algebra Appl. 443 (2014) 215−227.
     38.J. Y. Shao, A general product of tensors with applications, Linear Algebra Appl. 439 (2013) 2350−2366.
     39.J. Shao, L. Qi and S. Hu, Some new trace formulas of tensors with applications in spectral hypergraph theory, Linear Multilinear Algebra 63 (2015) 971−992.
     40.J. Shao, H. Shan and B. Wu, Some spectral properties and characterizations of connected oddbipartite uniform hypergraphs, Linear Multilinear Algebra 63 (2015) 2359−2372.
     41.J. Xie and A. Chang, H-eigenvalues of the signless Laplacian tensor for an even uniform hypergraph, Front. Math. China 8 (2013) 107−128.
     42.J. Xie and A. Chang, On the Z-eigenvalues of the adjacency tensors for uniform hypergraphs, Linear Algebra Appl. 430 (2013) 2195−2204.
     43.J. Xie and A. Chang, On the Z-eigenvalues of the signless Laplacian tensor for an even uniform hypergraph, Numer. Linear Algebra Appl. 20 (2013) 1030−1045.
     44.J. Xie and L. Qi, The clique and coclique numbers’ bounds based on the H-eigenvalues of uniform hypergraphs, Int. J. Numer. Anal. Model. 12 (2015) 318−327.
     45.J. Xie and L. Qi, Spectral directed hypergraph theory via tensors, Linear Multilinear Algebra 64 (2016) 780−794.
     46.C. Yu, C. Tai, T. Chan and Y. Yang, Modeling multi-way relation with hypergraph embedding, Proceedings of the 27th ACM International Conference on Information and Knowledge Management, (2018) 1707−1710.
     47.X. Yuan, L. Qi and J. Shao, The proof of a conjecture on largest Laplacian and signless Laplacian H-eigenvalues of uniform hypergraphs, Linear Algebra Appl.  490 (2016) 18−30.
     48.X. Yuan, J. Shao and H. Shan, Ordering of some uniform supertrees with larger spectral radii, Linear Algebra Appl.  495 (2016) 206−222.
     49.J. Zhang and J. Li, The maximum spectral radius of k-uniform hypergraphs with r pendent vertices, Linear Multilinear Algebra 67 (2018) 1062−1073.
     50.W. Zhang, L. Liu, L. Kang and Y. Bai, Some properties of the spectral radius for general hypergraphs, Linear Algebra Appl.  513 (2017) 103−119.
     51.X. Yuan, M. Zhang and M. Lu, Some upper bounds on the eigenvalues of uniform hypergraphs, Linear Algebra Appl.  484 (2015) 540−549.
     52.J. Yue, L. Zhang and M. Lu, The largest adjacency, signless Laplacian, and Laplacian H-eigenvalues of loose paths, Front. Math. China 11 (2016) 1−23.
     53.J. Zhou, L. Sun, W. Wang and C. Bu, Some spectral properties of uniform hypergraphs, Electron. J. Comb. 21 (2014) 4−24.