{"entities":{"Q2121776":{"pageid":2132519,"ns":120,"title":"Item:Q2121776","lastrevid":57733341,"modified":"2026-04-01T04:04:24Z","type":"item","id":"Q2121776","labels":{"en":{"language":"en","value":"Subgraph complementation and minimum rank"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7503041"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$3D073502-D8F6-4603-8B83-100E2B770151","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ef575975e58f1f3ea0698ed08d0772a85260b21a","datavalue":{"value":{"text":"Subgraph complementation and minimum rank","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2121776$5750CA82-5E8D-423D-B260-0B71FD7F49EE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8e8abecf6906abc9683f55c3c09ee4faf7d434fc","datavalue":{"value":"1486.05205","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121776$91F3AEFA-4F00-4494-AF82-69F3117DAA9D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5851bd76319152e9749e987299c38925d715ad07","datavalue":{"value":"10.37236/10383","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121776$09D3D2C2-735E-4CAB-B6C4-6ECEE35EB130","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0cff33d83b0c72369097b85fccb2fae4809f42c9","datavalue":{"value":{"entity-type":"item","numeric-id":2121775,"id":"Q2121775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$0D87E6C3-03B7-4C27-8447-CBF1F7D8D35B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a9f89610981366b09de72088a71e505406a8490d","datavalue":{"value":{"entity-type":"item","numeric-id":742579,"id":"Q742579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$D3C088B7-0027-4CFF-9A52-EB43C81CB701","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d36984850a1b5b0787ddd1e3103be649672d7d33","datavalue":{"value":{"entity-type":"item","numeric-id":521365,"id":"Q521365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$A2AA681F-4C62-4108-9395-0DAB1425C39C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$1ECD7CD3-62B6-487D-8DCA-78C410C1B7CD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d249924fb2575f70cd1998ce670af4e4c548d4a2","datavalue":{"value":{"time":"+2022-04-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2121776$2719D58F-9B45-4D46-815E-75FA00BFEFA7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e4abecb3772b00f75b9540739e788cf634dab692","datavalue":{"value":"https://arxiv.org/abs/2101.06180","type":"string"},"datatype":"url"},"type":"statement","id":"Q2121776$2C552544-1541-4F31-85F8-60790AFF52E7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2ad0af5d1dc0b8854613211e0b6e957520983e99","datavalue":{"value":"Summary: Any finite simple graph \\(G = (V,E)\\) can be represented by a collection \\(\\mathscr{C}\\) of subsets of \\(V\\) such that \\(uv\\in E\\) if and only if \\(u\\) and \\(v\\) appear together in an odd number of sets in \\(\\mathscr{C}\\). Let \\(c_2(G)\\) denote the minimum cardinality of such a collection. This invariant is equivalent to the minimum dimension of a faithful orthogonal representation of \\(G\\) over \\(\\mathbb{F}_2\\) and is closely connected to the minimum rank of \\(G\\). We show that \\(c_2 (G) = \\operatorname{mr}(G,\\mathbb{F}_2)\\) when \\(\\operatorname{mr}(G,\\mathbb{F}_2)\\) is odd, or when \\(G\\) is a forest. Otherwise, \\( \\operatorname{mr}(G,\\mathbb{F}_2)\\leqslant c_2 (G)\\leqslant \\operatorname{mr}(G,\\mathbb{F}_2)+1\\). Furthermore, we show that the following are equivalent for any graph \\(G\\) with at least one edge: i) \\(c_2(G)=\\operatorname{mr}(G,\\mathbb{F}_2)+1\\); ii) the adjacency matrix of \\(G\\) is the unique matrix of rank \\(\\operatorname{mr}(G,\\mathbb{F}_2)\\) which fits \\(G\\) over \\(\\mathbb{F}_2\\); iii) there is a minimum collection \\(\\mathscr{C}\\) as described in which every vertex appears an even number of times; and iv) for every component \\(G^\\prime\\) of \\(G, c_2(G^\\prime) = \\operatorname{mr}(G^\\prime,\\mathbb{F}_2) + 1\\). We also show that, for these graphs, \\(\\operatorname{mr}(G,\\mathbb{F}_2)\\) is twice the minimum number of tricliques whose symmetric difference of edge sets is \\(E\\). Additionally, we provide a set of upper bounds on \\(c_2(G)\\) in terms of the order, size, and vertex cover number of \\(G\\). Finally, we show that the class of graphs with \\(c_2(G)\\leqslant k\\) is hereditary and finitely defined. For odd \\(k\\), the sets of minimal forbidden induced subgraphs are the same as those for the property \\(\\operatorname{mr}(G,\\mathbb{F}_2)\\leq k\\), and we exhibit this set for \\(c_2(G) \\leqslant 2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2121776$FB3A8631-9B4D-4880-B0A2-EE81E765D65E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"82e8efd6e51c28a954a2ab0c3ccebf86d2ac5eb3","datavalue":{"value":"05C62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121776$CED028FE-203C-4F45-B21F-CC03A0BC8BFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121776$52115D86-9C62-4963-AA59-0A40C7ED2A58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121776$A4B8A9CC-B9C9-4AE5-919A-7578897AC66B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b29b3b0a978cf91ac9a61127140e8b528a09e774","datavalue":{"value":"7503041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121776$D2FE88D0-34C9-4E8E-8177-565C96B755A0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5eef6f7f632beb9bc36faf96f1bfd3cb51b4878e","datavalue":{"value":"faithful orthogonal representation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2121776$66454FE8-E0FB-48FF-A56F-85FFBE107F84","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"eecff7672d98ddd92e9f59bf72dece031571efe6","datavalue":{"value":{"entity-type":"item","numeric-id":35496,"id":"Q35496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$9C486A49-8A55-44E2-9957-CFE752EEF511","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$44AA6B19-58F6-4CAC-84FA-9D4099EAF0F2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"05c4120aafeea0c1108e24880c3a9ac986ea4748","datavalue":{"value":"W4213448819","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121776$EEAEE2CF-3D8A-46E4-B46E-2B4312367C0D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"083f10f6635559ba81199f219ab0fb640c2b5e78","datavalue":{"value":{"entity-type":"item","numeric-id":1841919,"id":"Q1841919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$7741B4A8-4420-475E-84BF-616E48506831","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dfef7ce43d53da0e4b67aa30bf97045102346946","datavalue":{"value":{"entity-type":"item","numeric-id":2477541,"id":"Q2477541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$8285A37D-9B5E-499F-8FAE-E0CDAE496DF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a77a45743c04d732efaf2dd5dccd56248e4a7af2","datavalue":{"value":{"entity-type":"item","numeric-id":999773,"id":"Q999773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$5B135476-A427-462A-A6B1-5D5C3BB277D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5729450c3387e8cc17f27d08f86eeedc20e9ee6","datavalue":{"value":{"entity-type":"item","numeric-id":1322010,"id":"Q1322010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$7BD19D3A-A569-4A94-B01F-1D9A82ADB39F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"478f409b26f6d97924ed1a5c907a84eea0f90920","datavalue":{"value":{"entity-type":"item","numeric-id":3497884,"id":"Q3497884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$6C699875-5CC8-4021-BAC7-FBE90C019BA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90c95fa25a5d73cb505c40e3e61c69d937ec805d","datavalue":{"value":{"entity-type":"item","numeric-id":3497853,"id":"Q3497853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$AC119478-65D2-497D-90E9-B8BE01CE0645","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e97db40ee47a660a4cffd9785b2c7c510549e90","datavalue":{"value":{"entity-type":"item","numeric-id":996311,"id":"Q996311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$A7AF2829-EAFB-4D79-A275-6953CD82F5B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0328713185ee80b2fb9fdcd1a9625eaee53ec51b","datavalue":{"value":{"entity-type":"item","numeric-id":2538694,"id":"Q2538694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$F029A83B-7752-4A65-A56F-6156E00D0BE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"765044b0ce99a6042eca6d96fc360d165408c7e3","datavalue":{"value":{"entity-type":"item","numeric-id":2182091,"id":"Q2182091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$BD467FBD-0EC9-479D-9B4F-FE94C986CE9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae5f118087a936a7738ca1f2551c9940d317c000","datavalue":{"value":{"entity-type":"item","numeric-id":810529,"id":"Q810529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$71001CC0-829A-44F2-8C0A-18C11B482A96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d956ab31b4de4533790426e93cff62e24c7a17d0","datavalue":{"value":{"entity-type":"item","numeric-id":765180,"id":"Q765180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$AD5204D4-D9B8-495F-B5A2-64DB1775BC3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1daf5e771e122dca1faece28b059debbdd5ff648","datavalue":{"value":{"entity-type":"item","numeric-id":848577,"id":"Q848577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$14EB46B0-1000-4FAD-B950-1A57D5F30D2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"727ec314cbc255ef284278c2cc0002ea2050ce4e","datavalue":{"value":{"entity-type":"item","numeric-id":4264405,"id":"Q4264405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$299727BF-C6C8-4A6E-A0D9-706D839BB6B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9001c5ea90a954557f0ac10357c47c6f8c94b6a","datavalue":{"value":{"entity-type":"item","numeric-id":967317,"id":"Q967317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$A65D9580-CDE2-4667-9EA8-66B10F7C5FF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c57448c3511c30ed92e5fbbbe68c6f2b95237a20","datavalue":{"value":{"entity-type":"item","numeric-id":2554710,"id":"Q2554710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$DBBBF4B0-CCB6-4F13-8E4B-2FA755156F60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a48c289367846d2e6cbf6ff475cf182266d6c35","datavalue":{"value":{"entity-type":"item","numeric-id":4178914,"id":"Q4178914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$58A773F4-AC08-4063-86AE-A040DF8857C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"230f1b49618b61f68774b8d8878ffad64e376284","datavalue":{"value":{"entity-type":"item","numeric-id":1823259,"id":"Q1823259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$02D0F93E-AA90-4083-B753-74F9FA9137AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0b7192879fa6e2b09c989b5998dda3efdd008aa","datavalue":{"value":{"entity-type":"item","numeric-id":584287,"id":"Q584287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$BD3DEEAC-7BB8-4812-B074-AB018F075D1B","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"c4eb16ca382f3ed76517fbc835c00e039b545e3f","datavalue":{"value":"bafkreifssbroosojnlmjeor32h5aeetbo5pdk4vujgigo5nr4zqzba3vry","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121776$9FBC6A7A-7519-4036-9175-EF89907AAAEE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"279fc538d786eb46fa7f734d15a77e71905e76b1","datavalue":{"value":{"entity-type":"item","numeric-id":924328,"id":"Q924328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"edff24e900c8a3e6a6b16e7f04f1268db77379dc","datavalue":{"value":{"amount":"+0.8111571669578552","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2121776$570B3243-302D-41DB-A14C-789927BA0B75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e38d1536fa0b861038f949aa01382d9810d28ee","datavalue":{"value":{"entity-type":"item","numeric-id":4656586,"id":"Q4656586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bcbcbf88dcb58526acfa707be188d627d0c9b981","datavalue":{"value":{"amount":"+0.8051315546035767","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2121776$9D6FC579-8B70-4377-AECE-43E282261467","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8049dcaebbc0cf50a6771994c57220545837e9fa","datavalue":{"value":{"entity-type":"item","numeric-id":4656572,"id":"Q4656572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d57ca212c6cfce3fad41df9d03977534daa83385","datavalue":{"value":{"amount":"+0.7876531481742859","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2121776$0BB0B861-507D-4EE8-9BDF-83608D71A7FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0deae3e34c703808d5cc2c896dad1091c1da1973","datavalue":{"value":{"entity-type":"item","numeric-id":765180,"id":"Q765180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5ced22cf99007956759a7effd32d8691bee0988","datavalue":{"value":{"amount":"+0.7711418271064758","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2121776$F1400EF5-BC80-40DA-8F5E-8A6B17F069A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe853403c27a86a697be890b3ff52cb57d881473","datavalue":{"value":{"entity-type":"item","numeric-id":999773,"id":"Q999773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cb4f3e4e19b2331e2355ab7315241573790179f","datavalue":{"value":{"amount":"+0.7646942734718323","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2121776$8B5A07E1-52F2-4F67-8432-C531EAD73641","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121776$8B968CC9-9116-4438-A647-23356505493D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2121776","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2121776"}}}}}