Editing Hypergraph (section)

==Cycles==
In contrast with ordinary undirected graphs for which there is a single natural notion of [[cycle (graph theory)|cycles]] and [[Forest (graph theory)|acyclic graphs]]. For hypergraphs, there are multiple natural non-equivalent definitions of cycles which collapse to the ordinary notion of cycle when the graph case is considered.

===Berge cycles===
A first notion of cycle was introduced by [[Claude Berge]]<ref>{{cite book |first=Claude |last=Berge |title=Graphs and Hypergraphs |location=Amsterdam |publisher=North-Holland |year=1973 |isbn=0-7204-2450-X }}</ref>. A '''Berge cycle''' in a hypergraph is an alternating sequence of distinct vertices and edges <math>(v_1, e_1, \dots , v_n, e_n)</math> where <math>v_i, v_{i+1}</math> are both in <math>e_i</math> for each <math>i \in [n]</math> (with indices taken modulo <math>n</math>).

Under this definition a hypergraph is '''acyclic''' if and only if its [[incidence graph]] (the [[bipartite graph]] defined above) is acyclic. Thus Berge-cyclicity can obviously be tested in [[linear time]] by an exploration of the incidence graph.

===Tight cycles===
This definition is particularly used for <math>k</math>-uniform hypergraphs, where all hyperedges are of size <math>k</math>. A '''tight cycle''' of length <math>n</math> in a hypergraph <math>H</math> is a sequence of distinct vertices <math>v_1,\dots, v_n</math> such that every consecutive <math>k</math>-tuple <math>\{v_i, \dots, v_{i+k-1}\}</math> (indices modulo <math>n</math>) forms a hyperedge in <math>H</math>. 
This notion was introduced by Katona and Kierstead<ref>{{cite journal | author-link1= Gyula O. H. Katona  | first1=G. | last1=Katona |first2=H. A.|last2=Kierstead| title= Hamiltonian chains in hypergraphs |journal=Journal of Graph Theory |volume=30 | issue=3 |pages=205–212 |year=1999 |doi=10.1002/(SICI)1097-0118(199903)30:3<205::AID-JGT5>3.0.CO;2-O |url=https://doi.org/10.1002/(SICI)1097-0118(199903)30:3<205::AID-JGT5>3.0.CO;2-O}}</ref> and has since garnered considerable attention, particularly in the study of Hamiltonicity in extremal combinatorics.<ref>{{cite book | first1=Y. | last1=Zhao | chapter=Recent advances on Dirac-type problems for hypergraphs |title=Recent Trends in Combinatorics | series=The IMA Volumes in Mathematics and its Applications |pages=145–165 |year=2016 | volume=159 |doi=10.1007/978-3-319-24298-9_6 | isbn=978-3-319-24296-5 |chapter-url=https://doi.org/10.1007/978-3-319-24298-9_6}}</ref><ref>{{cite journal | author-link1=Daniela Kühn  | first1=D. | last1=Kühn |author-link2=Deryk Osthus |first2=D.|last2=Osthus| title=Hamilton cycles in graphs and hypergraphs: an extremal perspective |journal=Proceeding of the International Congress of Mathematicans, ICM  |pages=381–406 |year=2014 |isbn=9788961058070 |url=https://web.mat.bham.ac.uk/D.Osthus/icmsurvey4.pdf}}</ref> 

Rödl, Szemerédi, and Ruciński showed that every <math>n</math>-vertex <math>k</math>-uniform hypergraph <math>H</math> in which every <math>(k-1)</math>-subset of vertices is contained in at least <math>n/2 + o(n)</math> hyperedges contains a Hamilton cycle. 
This corresponds to an approximate hypergraph-extension of the celebrated [[Hamiltonian path#Bondy–Chvátal theorem| Dirac's theorem]] about Hamilton cycles in graphs.<ref>{{cite journal | author-link1= Vojtěch Rödl  | first1=V. | last1=Rödl |author-link2=Endre Szemerédi |first2=E.|last2=Szemerédi|first3=A. |last3=Ruciński |title=An approximate Dirac-type theorem for k-uniform hypergraphs |journal=Combinatorica |volume=28 |pages=229–260 |year=2008 | issue=2 |doi=10.1007/s00493-008-2295-z |url=https://doi.org/10.1007/s00493-008-2295-z}}</ref>

The maximum number of hyperedges in a (tightly) acyclic <math>k</math>-uniform hypergraph remains unknown. The best known bounds, obtained by Sudakov and Tomon<ref>{{cite journal | author-link1= Benny Sudakov  | first1=B. | last1=Sudakov |first2=I.|last2=Tomon |title=The Extremal Number of Tight Cycles |journal=International Mathematics Research Notices |volume=2022 |pages=9663–9684 |year=2022 | issue=13 |doi=10.1093/imrn/rnaa396 |url=https://doi.org/10.1093/imrn/rnaa396}}</ref>, show that every <math>n</math>-vertex <math>k</math>-uniform hypergraph with at least <math>n^{k-1+o(1)}</math> hyperedges must contain a tight cycle. This bound is optimal up to the <math>o(1)</math> error term.

An '''<math>\ell</math>-cycle''' generalizes the notion of a tight cycle.
It consists in a sequence of vertices <math>v_1,\dots, v_n </math> and hyperedges <math>e_1,\dots, e_t</math> where each <math>e_i</math> consists of <math>k</math> consecutive vertices in the sequence and <math>|e_i\cap e_{i+1}|=\ell</math> for every <math>1\leq i\leq t</math>. Since every edge of the <math>\ell</math>-cycle contains exactly <math>k-\ell</math> vertices which are not contained in the previous edge, <math>n</math> must be divisible by <math>k-\ell</math>. Note that <math>\ell=k-1</math> recovers the definition of a tight cycle.

===α-acyclicity===
The definition of Berge-acyclicity might seem to be very restrictive: for instance, if a hypergraph has some pair <math>v \neq v'</math> of vertices and some pair <math>f \neq f'</math> of hyperedges such that <math>v, v' \in f</math> and <math>v, v' \in f'</math>, then it is Berge-cyclic. 

We can define a weaker notion of hypergraph acyclicity,<ref name=database>{{cite journal |first1=C. |last1=Beeri |author-link2=Ronald Fagin |first2=R. |last2=Fagin |first3=D. |last3=Maier |author-link4=Mihalis Yannakakis |first4=M. |last4=Yannakakis |title=On the Desirability of Acyclic Database Schemes |journal=Journal of the ACM |volume=30 |issue=3 |pages=479–513 |year=1983 |doi=10.1145/2402.322389 |s2cid=2418740 |url=http://cse.unl.edu/~choueiry/Documents/jacm83a.pdf |access-date=2021-01-03 |archive-date=2021-04-21 |archive-url=https://web.archive.org/web/20210421203326/http://cse.unl.edu/~choueiry/Documents/jacm83a.pdf |url-status=live }}</ref> later termed α-acyclicity. This notion of acyclicity is equivalent to the hypergraph being conformal (every clique of the primal graph is covered by some hyperedge) and its primal graph being [[chordal graph|chordal]]; it is also equivalent to reducibility to the empty graph through the [[GYO algorithm]]<ref>{{cite journal |first1=C. T. |last1=Yu |first2=M. Z. |last2=Özsoyoğlu |url=https://www.computer.org/csdl/proceedings/cmpsac/1979/9999/00/00762509.pdf |title=An algorithm for tree-query membership of a distributed query |journal=Proc. IEEE COMPSAC |pages=306–312 |year=1979 |doi=10.1109/CMPSAC.1979.762509 |access-date=2018-09-02 |archive-date=2018-09-02 |archive-url=https://web.archive.org/web/20180902151638/https://www.computer.org/csdl/proceedings/cmpsac/1979/9999/00/00762509.pdf |url-status=live }}</ref><ref name="graham1979universal">{{cite journal |first=M. H. |last=Graham |title=On the universal relation |journal=Technical Report |publisher=University of Toronto |location=Toronto, Ontario, Canada |year=1979 }}</ref> (also known as Graham's algorithm), a [[confluence (abstract rewriting)|confluent]] iterative process which removes hyperedges using a generalized definition of [[ear (graph theory)|ears]]. In the domain of [[database theory]], it is known that a [[database schema]] enjoys certain desirable properties if its underlying hypergraph is α-acyclic.<ref>{{cite book |author-link=Serge Abiteboul |first1=S. |last1=Abiteboul |author-link2=Richard B. Hull |first2=R. B. |last2=Hull |author-link3=Victor Vianu |first3=V. |last3=Vianu |title=Foundations of Databases |publisher=Addison-Wesley |year=1995 |isbn=0-201-53771-0 }}</ref> Besides, α-acyclicity is also related to the expressiveness of the [[guarded fragment]] of [[first-order logic]].

We can test in [[linear time]] if a hypergraph is α-acyclic.<ref>{{cite journal |author-link=Robert Tarjan |first1=R. E. |last1=Tarjan |author-link2=Mihalis Yannakakis |first2=M. |last2=Yannakakis |title=Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs |journal=SIAM Journal on Computing |volume=13 |issue=3 |pages=566–579 |year=1984 |doi=10.1137/0213035 }}</ref>

Note that α-acyclicity has the counter-intuitive property that adding hyperedges to an α-cyclic hypergraph may make it α-acyclic (for instance, adding a hyperedge containing all vertices of the hypergraph will always make it α-acyclic). Motivated in part by this perceived shortcoming, [[Ronald Fagin]]<ref name="fagin1983degrees">{{cite journal |first=Ronald |last=Fagin |title=Degrees of Acyclicity for Hypergraphs and Relational Database Schemes |journal=Journal of the ACM |year=1983 |volume=30 |issue=3 |pages=514–550 |doi=10.1145/2402.322390 |s2cid=597990 |doi-access=free }}</ref> defined the stronger notions of β-acyclicity and γ-acyclicity. We can state β-acyclicity as the requirement that all subhypergraphs of the hypergraph are α-acyclic, which is equivalent<ref name="fagin1983degrees" /> to an earlier definition by Graham.<ref name="graham1979universal" /> The notion of γ-acyclicity is a more restrictive condition which is equivalent to several desirable properties of database schemas and is related to [[Bachman diagram]]s. Both β-acyclicity and γ-acyclicity can be tested in [[PTIME|polynomial time]].

Those four notions of acyclicity are comparable: γ-acyclicity which implies β-acyclicity which implies α-acyclicity. Moreover, Berge-acyclicity implies all of them. None of the reverse implications hold including the Berge one. In other words, these four notions are different.<ref name="fagin1983degrees" />