{"entities":{"Q581415":{"pageid":583182,"ns":120,"title":"Item:Q581415","lastrevid":62930043,"modified":"2026-04-11T09:03:08Z","type":"item","id":"Q581415","labels":{"en":{"language":"en","value":"Graphs whose every transitive orientation contains almost every relation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4019104"}},"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":"Q581415$D26A09DA-7D8A-480B-8D50-05A607F61910","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2fb663009592609924e8aeba1768163ead95ae13","datavalue":{"value":{"text":"Graphs whose every transitive orientation contains almost every relation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q581415$D6D95D93-013F-420A-9285-83C104C18012","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"421838d138e150043ef72708a0cfa13df4549ebd","datavalue":{"value":"0627.05037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581415$ECEF7437-FA41-4433-8F69-D7293723427A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3d0399595d9d0be029db3527da0b6a9bafdfcd28","datavalue":{"value":"10.1007/BF02779671","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581415$9B80D3DD-C47A-4DB2-A914-1BE0012A0C44","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a14bac90927db699ac4af297f1d406f2762c11d","datavalue":{"value":{"entity-type":"item","numeric-id":168581,"id":"Q168581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581415$EA1A6B1E-2FEC-4FBB-9D3C-A36BE7D85A8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fa1c283669072b9efd9a8b4d0e623734e03b4535","datavalue":{"value":{"entity-type":"item","numeric-id":918998,"id":"Q918998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581415$D4A27600-5C98-4D30-B8FB-AB55FA7E4228","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1d50f9b953eac0b2404563f86ad398ee3823cb48","datavalue":{"value":{"entity-type":"item","numeric-id":173732,"id":"Q173732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581415$519AF342-1224-4FD6-814F-526AD3432FC9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q581415$F6A5BC39-6637-4950-B9BA-7EE4E92CA2C2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0aadc798dd269c5ff060d5bfeac51df81611c24f","datavalue":{"value":"Given a graph G on n vertices and a total ordering \\(\\prec\\) of V(G), the transitive orientations of G associated with \\(\\prec\\), denoted P(G;\\(\\prec)\\), is the partial order on V(G) defined by setting \\(x<y\\) in P(G;\\(\\prec)\\) if there is a path \\(x=x_ 1x_ 2...x_ r=y\\) in G such that \\(x_ 1\\prec x_ j\\) for \\(1\\leq i<j\\leq r\\). We investigate graphs G such that every transitive orientation of G contains \\(\\left( \\begin{matrix} n\\\\ 2\\end{matrix} \\right)-o(n^ 2)\\) relations. We prove that almost every \\(G_{n,p}\\) satisfies this requirement if  \\[  \\frac{pn \\log \\log \\log n}{\\log n \\log \\log n}\\to \\infty,  \\]  but almost no \\(G_{n,p}\\) satisfies the condition if (pn log log log n)/(log n log log n) is bounded. We also show that every graph G with n vertices and at most cn log n edges has some transitive orientation with fewer than \\(\\left( \\begin{matrix} n\\\\ 2\\end{matrix} \\right)-\\delta (c)n^ 2\\) relations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q581415$9E5996F6-1CFD-494F-829F-DE250EEB0715","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581415$31FD11CE-020A-4CB1-B294-59DD45A7D82D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"24363e421bb7b6dfa7fe7a9b1ee54d8da8a06bf1","datavalue":{"value":"06A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581415$4CDABE0E-D482-46E4-9D2C-C0D9D7DF9F43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e037813de56311048f7e0a208650360505bf4d4e","datavalue":{"value":"06A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581415$F3B0DA6D-BA72-4BDD-83DA-609956AF9F91","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"605b263a26be8fb712b78eb70f340d939aa59621","datavalue":{"value":"4019104","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581415$6CB603DA-730F-4515-8EC2-94DEB936E040","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7e273f88828ee87f8c825d5f1750d96895b8c18","datavalue":{"value":"transitive orientations","type":"string"},"datatype":"string"},"type":"statement","id":"Q581415$10AE321B-F425-4842-AB66-7DED13F50002","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"126bc261b4ce15426bca501a6725c284417e2bf6","datavalue":{"value":"partial order","type":"string"},"datatype":"string"},"type":"statement","id":"Q581415$1586D4DB-20C9-422F-9F8B-3AB484878194","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":"Q581415$A81D924D-06B7-4479-97FB-57A1D869D0ED","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b44ed555aed1fbc544de1802074fd0df13fb2c0","datavalue":{"value":{"entity-type":"item","numeric-id":1056541,"id":"Q1056541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581415$F4233AC2-B259-4C86-8377-6DB7B02D4228","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72bdc200c096a90cb093d01083b69c58672a0aa3","datavalue":{"value":{"entity-type":"item","numeric-id":3682518,"id":"Q3682518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581415$8B7BED80-38AB-42B5-8712-6D596AF1EA7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a534102807d89307045e757d282e704cf760213","datavalue":{"value":{"entity-type":"item","numeric-id":3835032,"id":"Q3835032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581415$01665487-4BA2-4AE0-93D2-85C60FCE0A24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f19b6cfdf7551dfd7d6a53c3ab6bf73aed04557","datavalue":{"value":{"entity-type":"item","numeric-id":3702524,"id":"Q3702524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581415$8DAF8BC3-71D4-4D63-B697-E45EB3EFA20D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d48741e4bb1c48bd4005c60c262892523705a2b","datavalue":{"value":{"entity-type":"item","numeric-id":1152382,"id":"Q1152382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581415$CF632332-87D7-4908-B955-7D3B996A14D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d333006ab5f5ba7661a2883dd9548d506c26947b","datavalue":{"value":{"entity-type":"item","numeric-id":1837535,"id":"Q1837535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581415$D4A2A26F-F0EC-45CB-BA55-0554BD74E10A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52d82b9726d79141bad331418bb231f1a1493e0a","datavalue":{"value":{"entity-type":"item","numeric-id":3922725,"id":"Q3922725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581415$63E6A8D1-1B7C-43AB-BE35-37C19F71F362","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a879a355ae8bb3c040f2bbf291ea6168340fae10","datavalue":{"value":{"entity-type":"item","numeric-id":3911406,"id":"Q3911406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581415$EB393B28-F8BB-4811-ABED-E1E3A58AFC3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ab54f9fde1cdfc86d62b3bd2c72ee9f0db9bf62","datavalue":{"value":{"entity-type":"item","numeric-id":3956411,"id":"Q3956411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581415$546F39A4-13C9-42DB-A7EF-646DA9FC7EE2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8e1dfde80764c961682811e90fe603fa31d3669e","datavalue":{"value":"https://doi.org/10.1007/bf02779671","type":"string"},"datatype":"url"},"type":"statement","id":"Q581415$13864483-EDA1-4DB9-BF4F-7A6F49CFE3B6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3fc3b07821f9a2fba99bbb4737990c860cb6291b","datavalue":{"value":"W2004621408","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581415$445AB3E3-301B-4052-A867-936885903FF1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95f7a3c63f69e9157a30240be53c0c01a571c442","datavalue":{"value":{"entity-type":"item","numeric-id":3835032,"id":"Q3835032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73b756ac2cf8b5f80b4b7dd7d8f978695a3ef70f","datavalue":{"value":{"amount":"+0.8471525311470032","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":"Q581415$D6539BEE-ED5B-4836-8817-BF2BDF1C948F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d7b0c3d351f8f4b58cf2beb719b429b66130cc0","datavalue":{"value":{"entity-type":"item","numeric-id":1327606,"id":"Q1327606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c69b411f4967577a029ae58732fc9806b2c8b71","datavalue":{"value":{"amount":"+0.8018277287483215","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":"Q581415$5F47F378-4FA4-4152-B37C-E0FBB6AA2CE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"802a4f8456ce286e9c948de9e4996a815e9884c0","datavalue":{"value":{"entity-type":"item","numeric-id":4864308,"id":"Q4864308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b6fd4d564b569a109d6920dd14ed98514baf234","datavalue":{"value":{"amount":"+0.8015779256820679","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":"Q581415$A2104DF7-2E9F-484B-AFCC-5B7B55D946C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e05a4b280f4ce0eae65d71fe2e673c0cda48f0c0","datavalue":{"value":{"entity-type":"item","numeric-id":1689921,"id":"Q1689921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d957d03c761f15a7d52c43624339be9c4f6b913e","datavalue":{"value":{"amount":"+0.8014248609542847","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":"Q581415$A324A7DC-4EFB-4914-99E3-400F75B3C980","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2de78ba4c70d3d201210c59bd5bcc38b8ff9312d","datavalue":{"value":{"entity-type":"item","numeric-id":5688998,"id":"Q5688998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e18fec1f346ccb78dde8a79006a6a8eaae71bf3","datavalue":{"value":{"amount":"+0.7666724920272827","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":"Q581415$B4238F6A-BCEA-4DB9-B01A-2B4B28D277DC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Graphs whose every transitive orientation contains almost every relation","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Graphs_whose_every_transitive_orientation_contains_almost_every_relation"}}}}}