tag:blogger.com,1999:blog-3722233.post2633931148902548357..comments2022-12-07T07:34:35.444-06:00Comments on Computational Complexity: Requst for Info on Prob HypergraphsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-4778540465198760502009-05-11T20:42:00.000-05:002009-05-11T20:42:00.000-05:00Having used some of both (hypergraphs and simplici...Having used some of both (hypergraphs and simplicial complexes), I would say that the extra structure afforded by the use of simplicial complexes far outweighs any notion that "hypergraphs are simpler." I'm not even sure I agree with that notion, particularly in the case when your hypergraph's edges are explicitly downward closed, which is exactly the condition needed for it to be a simplicial complex.<br /><br />--Anon. 2Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11459234864539428192009-05-11T17:52:00.000-05:002009-05-11T17:52:00.000-05:00I agree -- abstract simplicial complexes can be mo...I agree -- abstract simplicial complexes can be modeled by graphs, although it may well be less technically tricky to just use a hypergraph.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49567188723490840482009-05-11T14:52:00.000-05:002009-05-11T14:52:00.000-05:00any particular reason not to model this situation ...any particular reason not to model this situation using (random) bipartite graphs?KönigHallnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15059569513959302652009-05-11T12:58:00.000-05:002009-05-11T12:58:00.000-05:00Such a hypergraph would have the following propert...<I>Such a hypergraph would have the following properties: non-regular (edges can have any number of nodes, and different edges in the same graph can have different numbers of nodes) down-set (the existence of an edge implies the existence of all edges that are a subset of that edge)</I>It would be more natural to call this object a random simplicial complex (which is what it is) rather than call it a hypergraph. (Btw, this of course leads to the philosophical question of why call one dimensional complexes "graphs", especially since the word graph is already overloaded in mathematics by its use as in "graph of a map"). Coming back to the original question: I believe that I have seen some work on the expected Betti numbers of such random complexes. In fact its probably worthwhile to check out the following reference:<br /><br />R. Meshulam and N. Wallach, Homological connectivity of<br />random k-dimensional complexes, <br />Random Struct. Algorithms 34(2009) 408-417.Saugata Basuhttps://www.blogger.com/profile/13295092939775521282noreply@blogger.com