Editing Hypergraph (section)

==Partitions==
A partition theorem due to E. Dauber<ref>{{cite book |first=F. |last=Harary |title=Graph Theory |url=https://books.google.com/books?id=AmhQDwAAQBAJ |date=2018 |publisher=CRC Press |isbn=978-0-429-96231-8 |orig-year=1969 |page=172 |quote=We next state a theorem due to Elayne Dauber whose corollaries describe properties of line-symmetric graphs. Note the obvious but important observation that every line-symmetric graph is line-regular. |access-date=2021-06-12 |archive-date=2023-02-04 |archive-url=https://web.archive.org/web/20230204155708/https://books.google.com/books?id=AmhQDwAAQBAJ |url-status=live }}</ref> states that, for an edge-transitive hypergraph <math>H=(X,E)</math>, there exists a [[partition of a set|partition]]

:<math>(X_1, X_2,\cdots,X_K)</math>

of the vertex set <math>X</math> such that the subhypergraph <math>H_{X_k}</math> generated by <math>X_k</math> is transitive for each <math>1\le k \le K</math>, and such that

:<math>\sum_{k=1}^K r\left(H_{X_k} \right) = r(H)</math>

where <math>r(H)</math> is the rank of ''H''.

As a corollary, an edge-transitive hypergraph that is not vertex-transitive is bicolorable.

[[Graph partitioning]] (and in particular, hypergraph partitioning) has many applications to IC design<ref>{{Citation |title=Multilevel hypergraph partitioning: applications in VLSI domain |author=Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S. |journal=IEEE Transactions on Very Large Scale Integration (VLSI) Systems |date=March 1999 |volume=7 |issue=1 |pages=69–79 |doi=10.1109/92.748202 |postscript=.|citeseerx=10.1.1.553.2367 }}</ref> and [[parallel computing]].<ref>{{Citation |doi=10.1016/S0167-8191(00)00048-X |title=Graph partitioning models for parallel computing |author=Hendrickson, B., Kolda, T.G. |journal=Parallel Computing |year=2000 |volume=26 |issue=12 |pages=1519–1545 |osti=4179 |postscript=. |url=https://digital.library.unt.edu/ark:/67531/metadc684945/ |type=Submitted manuscript |access-date=2018-10-13 |archive-date=2021-01-26 |archive-url=https://web.archive.org/web/20210126021713/https://digital.library.unt.edu/ark:/67531/metadc684945/ |url-status=live }}</ref><ref>{{Cite conference |last1=Catalyurek |first1=U.V. |last2=Aykanat |first2=C. |title=A Hypergraph Model for Mapping Repeated Sparse Matrix–Vector Product Computations onto Multicomputers |conference=Proc. International Conference on Hi Performance Computing (HiPC'95) |year=1995}}</ref><ref>{{Citation |last1=Catalyurek |first1=U.V. |last2=Aykanat |first2=C. |title=Hypergraph-Partitioning Based Decomposition for Parallel Sparse-Matrix Vector Multiplication |journal=IEEE Transactions on Parallel and Distributed Systems |volume=10 |issue=7 |pages=673–693 |year=1999|doi=10.1109/71.780863 |postscript=. |citeseerx=10.1.1.67.2498 }}</ref> Efficient and scalable [[Graph partition|hypergraph partitioning algorithms]] are also important for processing large scale hypergraphs in machine learning tasks.<ref name=hyperx>{{cite book|last1=Huang|first1=Jin|last2=Zhang|first2=Rui|last3=Yu|first3=Jeffrey Xu|title=2015 IEEE International Conference on Data Mining |chapter=Scalable Hypergraph Learning and Processing |year=2015|url=https://www.ruizhang.info/publications/Icdm2015-hyperx.pdf|pages=775–780|doi=10.1109/ICDM.2015.33|isbn=978-1-4673-9504-5|s2cid=5130573|access-date=2021-01-08|archive-date=2021-01-26|archive-url=https://web.archive.org/web/20210126233924/https://ruizhang.info/publications/Icdm2015-hyperx.pdf|url-status=live}}</ref>