{"entities":{"Q2107505":{"pageid":2118248,"ns":120,"title":"Item:Q2107505","lastrevid":74106966,"modified":"2026-04-14T18:23:26Z","type":"item","id":"Q2107505","labels":{"en":{"language":"en","value":"Almost unimodal and real-rooted graph polynomials"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7625990"}},"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":"Q2107505$5A0F44B8-6C15-4F49-8A33-EDDD80F1CCB5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"61862fe44f96f9b208e307c7d9e3392875c9fe1b","datavalue":{"value":{"text":"Almost unimodal and real-rooted graph polynomials","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2107505$5626EEE2-51F8-43E7-A12D-28B358247511","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e494fbe798a5d78ac9ba195d35072f88633a1484","datavalue":{"value":{"entity-type":"item","numeric-id":2107504,"id":"Q2107504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$115F4565-B8D2-4C00-8490-210B9DCC13F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"32ead6a624fee23dc1dc37cfe2dcec3766470899","datavalue":{"value":{"entity-type":"item","numeric-id":452475,"id":"Q452475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$A15FCEC6-3673-4A65-8300-0F43B192446F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$B01CAA0E-2E2C-444D-8C1D-48C356D13996","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a206234ecf9f356a8958c964ff6117c1452a9511","datavalue":{"value":{"time":"+2022-12-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2107505$3024CD54-2665-418F-9A98-55D9BC6449E5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d7cdeff50b8a6f2fbb9ec32a268e019030e01714","datavalue":{"value":"https://arxiv.org/abs/2102.00268","type":"string"},"datatype":"url"},"type":"statement","id":"Q2107505$C2183557-CF75-4522-8460-EBCFCFAEC8CB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"020f57c59f2d2d3b2d71a99e82918862bd4abe47","datavalue":{"value":"This paper proves two rather general statements about the unimodality and real-rootedness of polynomials associated with graphs. Let \\(\\mathcal{A}\\) be a graph property and let \\(c_i^{\\mathcal{A}}(G)\\) denote, for a graph \\(G\\), the number of \\(i\\)-vertex induced subgraphs of \\(G\\) that have property \\(\\mathcal{A}\\). The polynomial associated with property \\(\\mathcal{A}\\) is defined as  \\[ P_{\\mathcal{A}}(G;x) = \\sum_i c_i^{\\mathcal{A}}(G)x^i. \\] Recall that a property \\(\\mathcal{A}\\) is called hereditary if it is closed under taking induced subgraphs: in other words, if a graph \\(G\\) has property \\(\\mathcal{A}\\), then so does every induced subgraph \\(H\\) of \\(G\\). The complement \\(\\mathcal{A}'\\) of a property \\(\\mathcal{A}\\) is the property of not satisfying \\(\\mathcal{A}\\). The first main theorem reads as follows:  Theorem. If \\(\\mathcal{A}\\) is the complement of a hereditary property, then for almost all graphs, the sequence \\(c_i^{\\mathcal{A}}(G)\\) is unimodal (in other words, the probability that the sequence is unimodal for a random graph \\(G(n,1/2)\\) tends to \\(1\\) as \\(n \\to \\infty\\)).  Second, the following theorem on real-rootedness is shown:  Theorem. If \\(\\mathcal{A}\\) is hereditary and satisfied by a graph that is neither complete nor edgeless, then \\(P_{\\mathcal{A}}(G;x)\\) is real-rooted if and only if \\(G\\) has property \\(\\mathcal{A}\\).  These extend results on, e.g., the domination polynomial and the forest polynomial.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2107505$0E8287EF-DA24-472B-BFF7-A4AEA15E143C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"26ba4f06ff5c7e92bd3a85f32aa625ae214ffe0f","datavalue":{"value":"05C31","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2107505$2759BCBA-08B2-40A6-A2DE-5CD87F5C97BA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"67e7abda06e9edc44c59ac1c2424e1ef4a6a604d","datavalue":{"value":"7625990","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2107505$4FA683AF-287B-4227-A710-54E776F920C1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4c58746c65b498a296790abd170bc3398210afd","datavalue":{"value":"graph polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q2107505$0B38162F-EA5D-492B-96E1-8319C26207CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f0597477c9240f11192d2132ed9468375af8d8f0","datavalue":{"value":"unimodality","type":"string"},"datatype":"string"},"type":"statement","id":"Q2107505$C545D8B3-2062-4237-BF35-EFD96D43B1D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7508f4d99ce79ab5786997fe11549761e62079a2","datavalue":{"value":"real-rootedness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2107505$9866AF7A-DA4D-402E-A9DE-AA47D474F894","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"46a0cb44285546404dd2ce5b1a8cee708a9f6a15","datavalue":{"value":"hereditary property","type":"string"},"datatype":"string"},"type":"statement","id":"Q2107505$E729C148-2936-4072-AA34-418FB36AFD87","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c64205db3e72cd3f2a1bf2c8789683d0b7a6b64e","datavalue":{"value":{"entity-type":"item","numeric-id":1028036,"id":"Q1028036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$6C3460C1-C5D5-4A10-8724-C4B4C1C30680","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":"Q2107505$88DD77F3-BF0F-445B-95F5-8F583418F35A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"685bb59ff72a652c875a815e398d775fc0e042a7","datavalue":{"value":"W3165153639","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2107505$57AA85D9-D175-4AA5-B702-8EB5B5429961","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"75eb24da16d5e5c62cb15873b2b4a6db1eb14ffd","datavalue":{"value":{"entity-type":"item","numeric-id":1015377,"id":"Q1015377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$A9148415-61C2-44C9-B27F-8CFAEE599301","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c92e513c4ecbf7a3693b096cea2b76dc3a7e1fc","datavalue":{"value":{"entity-type":"item","numeric-id":2949151,"id":"Q2949151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$1F77CF5F-AADC-4775-B972-9F220FDB9A2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f6b77dc10b35f29f15cefcd625288c4006311c0","datavalue":{"value":{"entity-type":"item","numeric-id":1257030,"id":"Q1257030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$F24AAE34-2035-4850-87E3-3A8C8858F266","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20a3e028a89d6602847e0d7a328ed65a85782f59","datavalue":{"value":{"entity-type":"item","numeric-id":4965364,"id":"Q4965364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$34992C8C-C529-41D8-959E-306541212CAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b91129aef2cdf66425a79ddc3e16c5ae8144d623","datavalue":{"value":{"entity-type":"item","numeric-id":1699567,"id":"Q1699567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$3EE053AB-519B-4DDD-B63E-A6341614B21D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e79b66a1a0ca08d0dabbebe6c77870438a05718c","datavalue":{"value":{"entity-type":"item","numeric-id":507795,"id":"Q507795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$89060FD4-24F0-4A0E-85AB-4F786898FA9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d11b04a023ea64ead77856f41516030fe62332e","datavalue":{"value":{"entity-type":"item","numeric-id":3087098,"id":"Q3087098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$CC8CAD40-CF5C-4F2C-BCDB-E29E05008A44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c894f1dd679421e4ade6a2bc68b0eae40fb3b8b0","datavalue":{"value":{"entity-type":"item","numeric-id":3424783,"id":"Q3424783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$ECF94E3B-3B02-4F92-BFA8-DF3DF2B68FAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1116c5978dd2fc904d8458a525ecf2c89e84389d","datavalue":{"value":{"entity-type":"item","numeric-id":3835498,"id":"Q3835498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$0D959F98-84BC-488F-8197-55623E73DDC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1c57f73b19247e7b85f86627fabdbc5d33eb0b8","datavalue":{"value":{"entity-type":"item","numeric-id":875937,"id":"Q875937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$ACDEA9A0-988C-47C9-861C-10583A05460B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec0cd0f4cd765b85f09d8b28678a9dc72c278705","datavalue":{"value":{"entity-type":"item","numeric-id":4962587,"id":"Q4962587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$FBB2D119-1DA6-492C-ABDB-ED95788C7DDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c025ec80459931f899d1946429af83bd4521c24","datavalue":{"value":{"entity-type":"item","numeric-id":5560915,"id":"Q5560915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$9AC4C637-B520-44A5-98E7-8E847F4C6039","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1783e7fdd80a1eb089f678d78159c960f6eaa1d","datavalue":{"value":{"entity-type":"item","numeric-id":2892821,"id":"Q2892821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$402DE1FA-C2D4-4509-B22F-FFBAF5EE8F7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c1759566441d66866fb3455fca574bbfaca39ef","datavalue":{"value":{"entity-type":"item","numeric-id":1732095,"id":"Q1732095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$E8B06E72-61D2-410A-B76D-A861AE9A8D3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24f07bec420ae5704de2abc82523e9b480192802","datavalue":{"value":{"entity-type":"item","numeric-id":2273013,"id":"Q2273013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$DBD862B7-5B2E-48F0-84C7-0A842CF7A0C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5da45a3a86133e385c0f9a074481898bfec0ca0","datavalue":{"value":{"entity-type":"item","numeric-id":2673493,"id":"Q2673493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$1C778910-D24C-40C6-B1F5-6712FFDCF2F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55f199b9a1345d032f8f0af28791c6464047a2ec","datavalue":{"value":{"entity-type":"item","numeric-id":5080911,"id":"Q5080911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$2A0FED55-5A2E-4935-A832-D7D2780A48CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6793e177d807b877a3f8d40ddd5473decd8f841","datavalue":{"value":{"entity-type":"item","numeric-id":3360223,"id":"Q3360223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$F811CE11-A22D-4E37-958A-8D0DA3BF194F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28588578bb09af0b4bf0a3281ab6c8d321eb619b","datavalue":{"value":{"entity-type":"item","numeric-id":4519896,"id":"Q4519896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$2136C77E-BF54-4C71-8030-3240DA1053A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f325c2ef7a8d6f12909f7b0827b329a4b0dfeba9","datavalue":{"value":{"entity-type":"item","numeric-id":5198669,"id":"Q5198669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$C7F3C20A-C8CA-4521-8CEB-42074DF660C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25ae01012e656d0bae282bb10dcbc843637ff552","datavalue":{"value":{"entity-type":"item","numeric-id":2949990,"id":"Q2949990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$4D47815D-201C-4D2A-9334-C2959AC7F46B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"725fa82e5a8f8abc24680414f87dc3b2d6509028","datavalue":{"value":{"entity-type":"item","numeric-id":5461524,"id":"Q5461524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$6E3A7C55-7CEB-4E49-ACCC-FE5DCAEFCE30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88117ded6e81d532ac770aa65ea4966417cb9989","datavalue":{"value":{"entity-type":"item","numeric-id":5907025,"id":"Q5907025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2107505$485AAF6D-10AA-4ED0-BB7E-8DC8745D1676","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d2a8a9e2996f31e6d209420240936c3a56a72286","datavalue":{"value":"10.1016/J.EJC.2022.103637","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2107505$BE12756D-E331-406B-B998-E5B2A0CA9F18","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9699bc2357aed2e4d1e7ff809fcc70959f9de63d","datavalue":{"value":{"entity-type":"item","numeric-id":1983147,"id":"Q1983147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b65860710b2781077ca129751feac4185b0d7704","datavalue":{"value":{"amount":"+0.8216473460197449","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":"Q2107505$14078E87-37EB-4B53-B155-F2F28A4E488E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0fcbdab760f6c95f22494c58906dd8a68a6d471d","datavalue":{"value":{"entity-type":"item","numeric-id":1840487,"id":"Q1840487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5cb0fbcc1d9b87f1a67b1f15b2dd00e2c8070d49","datavalue":{"value":{"amount":"+0.82059246301651","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":"Q2107505$6D990A12-C47B-494D-9BA5-9F30B4E99725","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e1fa54580d0b25f45343aa93939510e25377b05","datavalue":{"value":{"entity-type":"item","numeric-id":712199,"id":"Q712199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23307defb253f7bbcb47ea68e45acd68ee40a909","datavalue":{"value":{"amount":"+0.7842315435409546","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":"Q2107505$6E3B7AC3-2DB0-427B-ADE5-6D6F4957D6B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b63b93db23cec402b5624a24e15e9cb43a87718","datavalue":{"value":{"entity-type":"item","numeric-id":4253130,"id":"Q4253130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"922a69b3f9a49bc3c03db3e5256aaba3d37664e0","datavalue":{"value":{"amount":"+0.7526794075965881","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":"Q2107505$F8DD8936-B511-4754-BD85-EAE5608F9FDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04fe9f59719d7e1852a568c561c7e9c5646e5d64","datavalue":{"value":{"entity-type":"item","numeric-id":3739891,"id":"Q3739891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76a16eb997c7898052402e49a68eac20c01482ed","datavalue":{"value":{"amount":"+0.7392779588699341","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":"Q2107505$49B72889-0DA2-4C5A-B549-A334812F658A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Almost unimodal and real-rooted graph polynomials","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Almost_unimodal_and_real-rooted_graph_polynomials"}}}}}