<div dir="ltr">Eric --<div><br></div><div>Thank you for the thank you.</div><div><br></div><div>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.</div><div><br></div><div>This reminded me of my first published paper (<span style="color:rgb(73,73,73);font-family:Verdana,sans-serif">Roger E Critchlow Jr and Steven Stearns, </span><i style="color:rgb(73,73,73);font-family:Verdana,sans-serif">The Structure of Food Webs</i><span style="color:rgb(73,73,73);font-family:Verdana,sans-serif">, </span><b style="color:rgb(73,73,73);font-family:Verdana,sans-serif">The American Naturalist</b><span style="color:rgb(73,73,73);font-family:Verdana,sans-serif"> 1982, Vol. 120, pp. 478-499, which was a response to Joel Cohen's </span><i>Food Webs and Niche Space</i>. <b>Monographs in Population Biology</b> 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</div><div><br></div><div>Working from the original source for the algorithm, D.R. Fulkerson, O.A. Gross, <i>Incidence matrices and interval graphs</i>, <b>Pacific J. Math.</b> 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.</div><div><br></div><div>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.</div><div><br></div><div>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, <i>On the consecutive ones property</i>, <b>Discrete Applied Mathematics </b>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.</div><div><br></div><div>-- rec --</div><br class="gmail-Apple-interchange-newline"></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Feb 24, 2022 at 12:02 PM David Eric Smith <<a href="mailto:desmith@santafe.edu">desmith@santafe.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="overflow-wrap: break-word;">Thank you for this, Roger,<div><br></div><div>Very good to have.</div><div><br></div><div>Eric</div><div><br></div><div><br><div><br><blockquote type="cite"><div>On Feb 24, 2022, at 11:26 AM, Roger Critchlow <<a href="mailto:rec@elf.org" target="_blank">rec@elf.org</a>> wrote:</div><br><div><div dir="ltr">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.<div><br></div><div>CACM, MARCH 2022, VOL . 65, NO. 3, DOI:10.1145/3510550<br>Chris Edwards, A Group Effort, Researchers look for new insights in the world of hypergraphs<br><div><br></div><div>Further Reading<br>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</div><div><br></div><div>Jost, J. and Mulas, R., Normalized Laplace Operators for Hypergraphs with Real Coefficients, Journal of Complex Networks, Volume 9, Issue 1, February 2021, cnab009</div><div><br>Hillar, C.J., and Lim, L.-H., Most Tensor Problems are NP-Hard, Journal of the ACM, 60, 6, Article 45, November 2013</div><div><br>Veldt, N., Benson, A.R., and Kleinberg, J. Higher-order Homophily is Combinatorially Impossible, arXiv: 2103.11818 (2021), <a href="https://arxiv.org/" target="_blank">https://arxiv.org/</a><br>abs/2103.1181<br><div><br></div><div>-- rec --</div><div><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:sans-serif">Further Reading</span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:serif">Agarwal, S., Branson, K., and Belongie, S.</span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:sans-serif">Higher-Order Learning with Graphs</span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:serif">Proceedings of the 23rd International </span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:serif">Conference on Machine Learning (ICML </span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:serif">2006)</span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:sans-serif">, pages 17–24</span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:serif">Jost, J. and Mulas, R.</span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:sans-serif">Normalized Laplace Operators for </span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:sans-serif">Hypergraphs with Real Coefficients</span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:serif">Journal of Complex Networks</span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:sans-serif">, Volume 9, </span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:sans-serif">Issue 1, February 2021, cnab009</span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:serif">Hillar, C.J., and Lim, L.-H.</span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:sans-serif">Most Tensor Problems are NP-Hard</span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:serif">Journal of the ACM</span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:sans-serif">, 60, 6, Article 45, </span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:sans-serif">November 2013</span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:serif">Veldt, N., Benson, A.R., and Kleinberg, J.</span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:sans-serif">Higher-order Homophily</span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:sans-serif">is Combinatorially Impossible</span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:serif">arXiv: 2103.11818 (2021)</span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:sans-serif">, <a href="https://arxiv.org/" target="_blank">https://arxiv.org/</a></span><span style="padding:0px;margin:0px;color:transparent;white-space:pre-wrap;font-size:13.3333px;font-family:sans-serif">abs/2103.11818</span></div></div></div></div>
<br>.-- .- -. - / .- -.-. - .. --- -. ..--.. / -.-. --- -. .--- ..- --. .- - .<br>FRIAM Applied Complexity Group listserv<br>Zoom Fridays 9:30a-12p Mtn UTC-6  <a href="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" target="_blank">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</a><br>un/subscribe <a href="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" target="_blank">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</a><br>FRIAM-COMIC <a href="https://linkprotect.cudasvc.com/url?a=http%3a%2f%2ffriam-comic.blogspot.com%2f&c=E,1,jnDXzQpquRiGHWw_bpK81A-V0LrQtWWVZXyNsb0bDiK60I1ZdCSP4XyI6mKCm5Jm7bZrNcM5mO16cJgdz8Tpc8Jp6lNscF-XMmtKrUuhaUsx4Cv-4IMDsXE,&typo=1" target="_blank">https://linkprotect.cudasvc.com/url?a=http%3a%2f%2ffriam-comic.blogspot.com%2f&c=E,1,jnDXzQpquRiGHWw_bpK81A-V0LrQtWWVZXyNsb0bDiK60I1ZdCSP4XyI6mKCm5Jm7bZrNcM5mO16cJgdz8Tpc8Jp6lNscF-XMmtKrUuhaUsx4Cv-4IMDsXE,&typo=1</a><br>archives:<br> 5/2017 thru present <a href="https://linkprotect.cudasvc.com/url?a=https%3a%2f%2fredfish.com%2fpipermail%2ffriam_redfish.com%2f&c=E,1,XzgeCCgWXbci1RFJi0qrfDM_Vl_ixyh1EDxsZnBoDE4a2xT07FVU6b8B8abjydqCEKgL1SOU2Ywz5JQVkLDO3FgrNyTzQZlHELrUnH0Kd1NnSwF7dKEtuJKQ24k,&typo=1" target="_blank">https://linkprotect.cudasvc.com/url?a=https%3a%2f%2fredfish.com%2fpipermail%2ffriam_redfish.com%2f&c=E,1,XzgeCCgWXbci1RFJi0qrfDM_Vl_ixyh1EDxsZnBoDE4a2xT07FVU6b8B8abjydqCEKgL1SOU2Ywz5JQVkLDO3FgrNyTzQZlHELrUnH0Kd1NnSwF7dKEtuJKQ24k,&typo=1</a><br> 1/2003 thru 6/2021  <a href="http://friam.383.s1.nabble.com/" target="_blank">http://friam.383.s1.nabble.com/</a><br></div></blockquote></div><br></div></div><br>
.-- .- -. - / .- -.-. - .. --- -. ..--.. / -.-. --- -. .--- ..- --. .- - .<br>
FRIAM Applied Complexity Group listserv<br>
Zoom Fridays 9:30a-12p Mtn UTC-6  <a href="http://bit.ly/virtualfriam" rel="noreferrer" target="_blank">bit.ly/virtualfriam</a><br>
un/subscribe <a href="http://redfish.com/mailman/listinfo/friam_redfish.com" rel="noreferrer" target="_blank">http://redfish.com/mailman/listinfo/friam_redfish.com</a><br>
FRIAM-COMIC <a href="http://friam-comic.blogspot.com/" rel="noreferrer" target="_blank">http://friam-comic.blogspot.com/</a><br>
archives:<br>
 5/2017 thru present <a href="https://redfish.com/pipermail/friam_redfish.com/" rel="noreferrer" target="_blank">https://redfish.com/pipermail/friam_redfish.com/</a><br>
 1/2003 thru 6/2021  <a href="http://friam.383.s1.nabble.com/" rel="noreferrer" target="_blank">http://friam.383.s1.nabble.com/</a><br>
</blockquote></div>