Eric -- Thank you for the thank you.
The research certainly seems to be all over the place. The article sounded like the voice of an NSF program officer seeking more proposals to fund, too. This reminded me of my first published paper (Roger E Critchlow Jr and Steven Stearns, *The Structure of Food Webs*, *The American Naturalist* 1982, Vol. 120, pp. 478-499, which was a response to Joel Cohen's *Food Webs and Niche Space*. *Monographs in Population Biology* 11. 1978. Princeton, NJ: Princeton University Press. 190 pp. Cohen adapted an algorithm for analysing the overlaps of archaeological finds in sedimentary deposits to asking if food web relations had the structure of overlapping intervals. A very clever idea, but Cohen didn't program the algorithm, he had someone write an APL program that he used to analyse a collection of food webs. And he found that lots of food webs had the structure of overlapping intervals, which he identified as one-dimensional niche descriptors Working from the original source for the algorithm, D.R. Fulkerson, O.A. Gross, *Incidence matrices and interval graphs*, *Pacific J. Math.* I5 (3) (1965) 835-855, I recoded the algorithm from scratch and obtained results that agreed with Cohen's for most of the data set, but disagreed on a few instances. It turned out that I had simplified the algorithm by omitting the step which reduced the food web incidence matrix to its maximal clique matrix, but I had correctly coded the algorithm for testing an incidence matrix for consecutive ones (CIP). An incidence matrix has a 1 if the row eats the column and 0 otherwise. An incidence matrix has CIP if you can permute the columns so each row has all its ones in consecutive columns. A food web with CIP always produces a maximal clique with CIP, hence the agreement in results, but maximal cliques with CIP can arise from food webs without CIP, hence the disagreements in results. Many of Cohen's food webs can permute to consecutive ones in both rows and columns, which gives you a block structured matrix where the ones are all neatly organized. The block structure comes from the maximal cliques, the transitive closure of predator A and B have a common prey, or the transitive closure of prey C and D have a common predator. Consecutive ones in a component might be evidence that the relation grew by diversification from a founder seed. I hadn't thought about this for a long while. Tracking down the Fulkerson & Gross citation via google I found João Meidanis, OscarPorto, Guilherme P.Telles, *On the consecutive ones property*, *Discrete Applied Mathematics *Volume 88, Issues 1–3, 9 November 1998, Pages 325-354, and discovered the applications of consecutive ones to sequencing contig assembly and chip circuit floor planning. -- rec -- On Thu, Feb 24, 2022 at 12:02 PM David Eric Smith <[email protected]> wrote: > Thank you for this, Roger, > > Very good to have. > > Eric > > > > On Feb 24, 2022, at 11:26 AM, Roger Critchlow <[email protected]> wrote: > > There's a little news burp about hypergraphs in this month's CACM, mostly > about how hard they are, except when they reduce to graphs, and that the > NSF is funding some research efforts. > > CACM, MARCH 2022, VOL . 65, NO. 3, DOI:10.1145/3510550 > Chris Edwards, A Group Effort, Researchers look for new insights in the > world of hypergraphs > > Further Reading > Agarwal, S., Branson, K., and Belongie, S. Higher-Order Learning with > Graphs, Proceedings of the 23rd International Conference on Machine > Learning (ICML 2006), pages 17–24 > > Jost, J. and Mulas, R., Normalized Laplace Operators for Hypergraphs with > Real Coefficients, Journal of Complex Networks, Volume 9, Issue 1, February > 2021, cnab009 > > Hillar, C.J., and Lim, L.-H., Most Tensor Problems are NP-Hard, Journal of > the ACM, 60, 6, Article 45, November 2013 > > Veldt, N., Benson, A.R., and Kleinberg, J. Higher-order Homophily is > Combinatorially Impossible, arXiv: 2103.11818 (2021), https://arxiv.org/ > abs/2103.1181 > > -- rec -- > Further ReadingAgarwal, S., Branson, K., and Belongie, S.Higher-Order > Learning with GraphsProceedings of the 23rd International Conference on > Machine Learning (ICML 2006), pages 17–24Jost, J. and Mulas, R.Normalized > Laplace Operators for Hypergraphs with Real CoefficientsJournal of > Complex Networks, Volume 9, Issue 1, February 2021, cnab009Hillar, C.J., > and Lim, L.-H.Most Tensor Problems are NP-HardJournal of the ACM, 60, 6, > Article 45, November 2013Veldt, N., Benson, A.R., and Kleinberg, > J.Higher-order > Homophilyis Combinatorially ImpossiblearXiv: 2103.11818 (2021), > https://arxiv.org/abs/2103.11818 > > .-- .- -. - / .- -.-. - .. --- -. ..--.. / -.-. --- -. .--- ..- --. .- - . > FRIAM Applied Complexity Group listserv > Zoom Fridays 9:30a-12p Mtn UTC-6 > https://linkprotect.cudasvc.com/url?a=https%3a%2f%2f%2f%2fbit.ly%2fvirtualfriam&c=E,1,wESXHLhF_A9fMgD1_PYGHFY4lKSdDoNrN_I23_B5OgTdlhrFbN1sYHxd1P4_5Gd1TPkdpHocQ30zMHI_S3D0j3Kh6MFNq8vCpEVdxn3mtIrhRQU2&typo=1 > un/subscribe > https://linkprotect.cudasvc.com/url?a=http%3a%2f%2fredfish.com%2fmailman%2flistinfo%2ffriam_redfish.com&c=E,1,gbR3NW7yvh6njQjIm3mwfCyWde1zchF6xw-hiORaZXDPAOOPSB2Lue-k0ml57EHVTf43W2y6b1JTdC9u0DCD8Lb_vXSr3FAlD_SWeS0ZEg,,&typo=1 > FRIAM-COMIC > https://linkprotect.cudasvc.com/url?a=http%3a%2f%2ffriam-comic.blogspot.com%2f&c=E,1,jnDXzQpquRiGHWw_bpK81A-V0LrQtWWVZXyNsb0bDiK60I1ZdCSP4XyI6mKCm5Jm7bZrNcM5mO16cJgdz8Tpc8Jp6lNscF-XMmtKrUuhaUsx4Cv-4IMDsXE,&typo=1 > archives: > 5/2017 thru present > https://linkprotect.cudasvc.com/url?a=https%3a%2f%2fredfish.com%2fpipermail%2ffriam_redfish.com%2f&c=E,1,XzgeCCgWXbci1RFJi0qrfDM_Vl_ixyh1EDxsZnBoDE4a2xT07FVU6b8B8abjydqCEKgL1SOU2Ywz5JQVkLDO3FgrNyTzQZlHELrUnH0Kd1NnSwF7dKEtuJKQ24k,&typo=1 > 1/2003 thru 6/2021 http://friam.383.s1.nabble.com/ > > > > .-- .- -. - / .- -.-. - .. --- -. ..--.. / -.-. --- -. .--- ..- --. .- - . > FRIAM Applied Complexity Group listserv > Zoom Fridays 9:30a-12p Mtn UTC-6 bit.ly/virtualfriam > un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com > FRIAM-COMIC http://friam-comic.blogspot.com/ > archives: > 5/2017 thru present https://redfish.com/pipermail/friam_redfish.com/ > 1/2003 thru 6/2021 http://friam.383.s1.nabble.com/ >
.-- .- -. - / .- -.-. - .. --- -. ..--.. / -.-. --- -. .--- ..- --. .- - . FRIAM Applied Complexity Group listserv Zoom Fridays 9:30a-12p Mtn UTC-6 bit.ly/virtualfriam un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com FRIAM-COMIC http://friam-comic.blogspot.com/ archives: 5/2017 thru present https://redfish.com/pipermail/friam_redfish.com/ 1/2003 thru 6/2021 http://friam.383.s1.nabble.com/
