{"entities":{"Q2500963":{"pageid":2511706,"ns":120,"title":"Item:Q2500963","lastrevid":49906768,"modified":"2026-01-11T22:29:13Z","type":"item","id":"Q2500963","labels":{"en":{"language":"en","value":"Bounding the number of edges in permutation graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5050762"}},"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":"Q2500963$669D677D-848E-4096-B094-BC3D125A07B4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"aa0382f435a4d1d93e13fe5c46bee342a165cc8d","datavalue":{"value":{"text":"Bounding the number of edges in permutation graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2500963$B590D277-674F-4383-BBBF-8FB2AB4272FA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"14b30eaea3c32460b20f57671fc6433f1011739d","datavalue":{"value":"1098.05042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2500963$42847003-4535-4A76-80B7-0CE8110EF86B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ab64f168d56fc1e080fce2dc4a26498cba4f5c3f","datavalue":{"value":{"entity-type":"item","numeric-id":405192,"id":"Q405192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2500963$2CA2F4D7-E685-4F9A-A70C-06D46483A23C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c8544897e6932c56e44cf54474ee3f0a2bbb124f","datavalue":{"value":{"entity-type":"item","numeric-id":388724,"id":"Q388724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2500963$16CD915F-351C-4B35-9BA7-779E42832EEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"502bbb6d3842faa7531646862d34737b11134d06","datavalue":{"value":{"entity-type":"item","numeric-id":1584432,"id":"Q1584432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2500963$3F80B77B-9482-486F-9FD6-85173005FB3D","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":"Q2500963$E335AA6A-8BEB-4C2B-B24E-A2F9C5C4B855","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ce041d4734364c3a206df997bf620f42fb038366","datavalue":{"value":{"time":"+2006-08-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2500963$BEF27164-536F-48F1-A58C-AB5DB8E21DED","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2fc353a1e7379f85c4c17eb4aa6e176b58daff98","datavalue":{"value":"https://eudml.org/doc/126513","type":"string"},"datatype":"url"},"type":"statement","id":"Q2500963$93EBB9E2-0B88-4042-9184-051DFB8EE7E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"fda4299f44c2b32f296f9d67bd9502765a6c14f9","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_13/Abstracts/v13i1r44.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q2500963$2CD6AC64-C962-4936-9CF2-ABDB62D8CA6B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4cc886e615ed5ae8fca03645752f014fbe4194a0","datavalue":{"value":"Summary: Given an integer \\(s\\geq 0\\) and a permutation \\(\\pi \\in S_n\\), let \\(\\Gamma_{\\pi,s}\\) be the graph on \\(n\\) vertices \\(1, \\dots, n\\) where two vertices \\(i<j\\) are adjacent if the permutation flips their order and there are at most \\(s\\) integers \\(k\\), \\(i < k< j\\), such that \\(\\pi=[\\dots j \\dots k \\dots i\\ldots]\\). In this short paper we determine the maximum number of edges in \\(\\Gamma_{\\pi,s}\\) for all \\(s\\geq 1\\) and characterize all permutations \\(\\pi\\) which achieve this maximum. This answers an open question of Adin and Roichman, who studied the case \\(s=0\\). We also consider another (closely related) permutation graph, defined by Adin and Roichman, and obtain asymptotically tight bounds on the maximum number of edges in it.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2500963$FEA88FD8-CD96-492F-A7B1-B8F1E593D0B0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2500963$9D6E70A5-115D-45EB-833E-D4398A8ABABB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa3a0cd38ea582d702916ee49599e832f201d954","datavalue":{"value":"20B30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2500963$FDCDA8CF-40BB-41A3-921F-0DCE7FF006FA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b0dc203ad76aa901b35a7b807bee953cd44994fe","datavalue":{"value":"5050762","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2500963$0CDD69BD-549E-4465-A5BD-4F1248225113","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":"Q2500963$73F61DA3-92C1-4CAD-981A-3245388E4720","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"cd6eacad03b1cc570bb9e76494590d5faa92a12a","datavalue":{"value":"bafkreiaju2z62uozkrrhmxlqk7rsfumucvuxgrag3oarlgqz6km3pskiom","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2500963$B9E3ED00-31FA-4986-BB2D-D270967F6465","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ecb0235b7f37b92df230afdfe2e3958422609ad","datavalue":{"value":{"entity-type":"item","numeric-id":1942938,"id":"Q1942938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f10b29b011fb46791a6a0ca956791f6b29f0e0ed","datavalue":{"value":{"amount":"+0.7970010638237","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":"Q2500963$BF3737C5-B6B3-46DC-A9D8-438579AA7336","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afd819cec9c4605ab6eca1ba053600da2dc9946a","datavalue":{"value":{"entity-type":"item","numeric-id":5888419,"id":"Q5888419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1277a853b8085d08bb57f64cecbd6d9cb0ec16d0","datavalue":{"value":{"amount":"+0.7734971642494202","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":"Q2500963$B73DF4C7-2C49-40C3-966C-26BD6FEA4403","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"284f59fb31a359df1b452469f18511bfa0c206aa","datavalue":{"value":{"entity-type":"item","numeric-id":5194623,"id":"Q5194623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7fe346b85f3fae4d1fe0023f3ac7e1353ed8125a","datavalue":{"value":{"amount":"+0.7695034742355347","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":"Q2500963$1128DBF2-3507-47DB-BCA8-676E47665BD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31d8b375bb0a791ecbd428dab13558b37aacf9b7","datavalue":{"value":{"entity-type":"item","numeric-id":4387757,"id":"Q4387757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0aac3970d3793ad39e30a98b36ff6195cf92006","datavalue":{"value":{"amount":"+0.7482282519340515","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":"Q2500963$18EF8BD3-7B71-4DE0-94ED-5708FC9EF240","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b99650daa27e4632f7019d44cbd5bc6a41e1f7e","datavalue":{"value":{"entity-type":"item","numeric-id":388720,"id":"Q388720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b72a0e1d4b1b1d5b9f48184b6a761d8a543afb5","datavalue":{"value":{"amount":"+0.7459133863449097","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":"Q2500963$C8930673-488C-4E88-B48C-40D161363B73","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2500963","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2500963"}}}}}