{"entities":{"Q1114718":{"pageid":1125467,"ns":120,"title":"Item:Q1114718","lastrevid":49240192,"modified":"2026-01-06T20:15:41Z","type":"item","id":"Q1114718","labels":{"en":{"language":"en","value":"The number of linear extensions of bipartite graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4083686"}},"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":"Q1114718$985D5CC8-52A0-4B37-BE40-25C4DF73C196","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5f23eed5d05a91ad7542e5c2fe38f70ebb503c75","datavalue":{"value":{"text":"The number of linear extensions of bipartite graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1114718$571550EE-3A5B-4AF4-BC47-3DD9B71E236C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4e7a7798c63ec25441ca6fa899ed8b883e332c69","datavalue":{"value":"0663.06001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114718$CE4E44B0-6929-49EF-9C4B-C26B8CA4886A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"86e156db84b32c2af0ad0b488ab5ed5acd1b12f9","datavalue":{"value":"10.1007/BF00354893","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114718$568F5049-74B4-4096-97E8-EC2992CED3DA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a5c969dfa2f927a5ae1e039b2c8bd67fe1245b02","datavalue":{"value":{"entity-type":"item","numeric-id":910419,"id":"Q910419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114718$2F1BB3EF-B247-445F-A03B-223E2DFC7CD7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e2599ed8061d57585b4363072a1afceea2452436","datavalue":{"value":{"entity-type":"item","numeric-id":172073,"id":"Q172073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114718$0A8A43F1-9DE9-48E7-887A-4031603E9C05","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1114718$9301087C-81E8-4CCA-9D8E-6659EFC7352C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4c9a0a6db7a636757c5dda74d993e96fb19fc15b","datavalue":{"value":"A linear extension of a partially ordered set P is a total order L of elements of P such that \\(x\\leq y\\) in P implies \\(x\\leq y\\) in L. An acyclic directed graph G can be considered as a partial order on its vertex set; we have \\(x\\leq y\\) in this order if and only if a directed path in G goes from x to y. A natural orientation of a bipartite graph with the bipartition classes \\(V_ 1\\), \\(V_ 2\\) is the orientation such that one of the sets \\(V_ 1\\), \\(V_ 2\\) is the set of initial vertices of all edges and the other is the set of all terminal ones. It is proved that any acyclic orientation of a bipartite graph G has a smaller number of linear extensions than a natural one. This was a conjecture of M. D. Atkinson.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114718$7243E31C-1B9A-4FE3-A999-8ACAA62AF1A6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e037813de56311048f7e0a208650360505bf4d4e","datavalue":{"value":"06A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114718$C7D03A25-BCD5-404B-B6F9-D26FE673961D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114718$FDC48E37-133B-4A14-8FA1-C18A11FCE92F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"24363e421bb7b6dfa7fe7a9b1ee54d8da8a06bf1","datavalue":{"value":"06A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114718$066CC17E-79F9-4C4A-8BE6-7506222A2A08","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a57e4a4f9c9a8f3306672924442a5bceeddb17af","datavalue":{"value":"4083686","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114718$CF93C9B3-2F33-47AB-9901-7EE936DB74F8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8ec9aaccfbefca3a6796892d946098699de2fa2","datavalue":{"value":"acyclic directed graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114718$55971C90-68BF-4848-ABB6-00E1B832C717","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"76a2a64acc1cfe7602e2d19a5c639865f830279c","datavalue":{"value":"natural orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114718$16547F6D-C28F-4D17-9F7A-D66BFEF80D5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3187e84c5efaed03d0bd9515713a70084404d3ee","datavalue":{"value":"bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114718$3D13A2C3-031E-496C-8865-6059E197BCD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd08082ecfb3b93b17c9a46ab514e0f78e6b2bec","datavalue":{"value":"acyclic orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114718$B9CC2655-9B58-4914-B04E-F10498C91F6F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d9b462d071c33d7d83486f9fef57845bb41d7acf","datavalue":{"value":{"entity-type":"item","numeric-id":190573,"id":"Q190573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114718$2B51A878-D3C9-4E93-A0DB-36B6F336FB9D","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":"Q1114718$2DEC5D25-A7F0-431E-AA3C-FA8810B3B62A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"98cdc2b46bca48296a0310f69a141d26c73c66a9","datavalue":{"value":{"entity-type":"item","numeric-id":752307,"id":"Q752307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114718$96C14A44-A845-4CB4-946B-453AB7BFFE95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee5f105bb81e09df604b06a5b4cc35194199aa53","datavalue":{"value":{"entity-type":"item","numeric-id":1077721,"id":"Q1077721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114718$5DDFFBFA-408B-4BD3-A656-E6E5DCC3D8CE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7062535dd18987c398f2b56831df7fcfc418fc29","datavalue":{"value":{"entity-type":"item","numeric-id":4584164,"id":"Q4584164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d05c95b56afa94703415f109b094824fb1349230","datavalue":{"value":{"amount":"+0.8212171196937561","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":"Q1114718$8D1DA909-317F-4754-9D1A-D7DC0C10024B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba2e9459187a2982228eb1647d6fb1ad85c7cd7e","datavalue":{"value":{"entity-type":"item","numeric-id":583247,"id":"Q583247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"601c17ab5fd41890a6cf188becb316b073f076d5","datavalue":{"value":{"amount":"+0.7928159832954407","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":"Q1114718$60EA02AF-F46A-43E3-8D3E-6AE1FAA5459E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89656be55431d2fc103542e575ddea8f544c4b94","datavalue":{"value":{"entity-type":"item","numeric-id":4595964,"id":"Q4595964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12aaa77d7f946d6a779ef2c6de481494716ef623","datavalue":{"value":{"amount":"+0.7851265668869019","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":"Q1114718$F48BFD29-4AB4-485C-B503-CF4E99C194B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2201702dafac54a0e24a28534d1808a99b57509","datavalue":{"value":{"entity-type":"item","numeric-id":1906134,"id":"Q1906134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80e7040072d649b69088d93341b537714c6c0e02","datavalue":{"value":{"amount":"+0.7847973108291626","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":"Q1114718$38AAE219-533F-497F-AD13-43B570D9C4B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d158787ad92e746b96600b3533a9c627974df7d0","datavalue":{"value":{"entity-type":"item","numeric-id":4490791,"id":"Q4490791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80e7040072d649b69088d93341b537714c6c0e02","datavalue":{"value":{"amount":"+0.7847973108291626","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":"Q1114718$053408F5-1383-4220-A668-B935187317E8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1114718","badges":[]}}}}}