{"entities":{"Q2048544":{"pageid":2059286,"ns":120,"title":"Item:Q2048544","lastrevid":57705795,"modified":"2026-04-01T00:17:28Z","type":"item","id":"Q2048544","labels":{"en":{"language":"en","value":"Duality pairs and homomorphisms to oriented and unoriented cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7379540"}},"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":"Q2048544$B6788580-D713-4777-81D9-79477086BF01","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"07a976f4b988984edca3489b7096a58c3adcf740","datavalue":{"value":{"text":"Duality pairs and homomorphisms to oriented and unoriented cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2048544$4B971783-9D5D-44F5-A7B7-2FB29EC801DB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3f4a998cdce4c8e1c4875cf23a4b3ea61060c671","datavalue":{"value":"1470.05117","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2048544$720FF627-C279-4FB6-AD96-E4A35B6D1B27","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c9c3ec26c2ad1d478b5c6c317b9aa00ac33cbdd8","datavalue":{"value":"10.37236/9747","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2048544$601EF441-319B-44C9-994D-88425944646F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2b73733ab61a44aa2e2543373c851998f366437b","datavalue":{"value":{"entity-type":"item","numeric-id":2048543,"id":"Q2048543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048544$25425090-69BE-423A-8F7F-23A87B56D288","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e0256728d2b9e907ba2a8c5f27be200fddd8a24c","datavalue":{"value":{"entity-type":"item","numeric-id":338574,"id":"Q338574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048544$74FB82C3-9DB1-4465-ABE1-FF1AAABA4DBD","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":"Q2048544$37EDA1A8-8C75-4FEE-BA38-63A25009FE92","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"30e793a417e36fabefb163f4091de1cf887efc65","datavalue":{"value":{"time":"+2021-08-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2048544$79448BD8-26C5-44A7-8680-AE92AA1D7364","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"286d21ac83cf32fd838d9baf3c223bd95057c8d7","datavalue":{"value":"https://arxiv.org/abs/2003.05605","type":"string"},"datatype":"url"},"type":"statement","id":"Q2048544$00940906-2C62-4F8F-96FA-3A7D2BA44AC9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8647e22facc98d75746e37f68aba967c47bea2b8","datavalue":{"value":"Summary: In the homomorphism order of digraphs, a duality pair is an ordered pair of digraphs \\((G,H)\\) such that for any digraph, \\(D\\), \\(G\\to D\\) if and only if \\(D\\not \\to H\\). The directed path on \\(k+1\\) vertices together with the transitive tournament on \\(k\\) vertices is a classic example of a duality pair.  In this work, for every undirected cycle \\(C\\) we find an orientation \\(C_D\\) and an oriented path \\(P_C\\), such that \\((P_C,C_D)\\) is a duality pair. As a consequence we obtain that there is a finite set, \\(F_C\\), such that an undirected graph is homomorphic to \\(C\\), if and only if it admits an \\(F_C\\)-free orientation. As a byproduct of the proposed duality pairs, we show that if \\(T\\) is an oriented tree of height at most \\(3\\), one can choose a dual of \\(T\\) of linear size with respect to the size of \\(T\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2048544$00CC9795-0C60-4931-B629-7FE53773C33F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2048544$8272A43B-46BF-4D5E-9640-E4F38A95A2A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2048544$4A0D15A1-267D-4F6C-BEE7-41E37FDB3C63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2048544$D9AC1376-A15B-4EAB-A7D8-B22399C2799C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a8a2b167d283968f447566d13463d12e7b394452","datavalue":{"value":"7379540","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2048544$7CFDA322-853F-4E77-BFE8-5C6C34EA2A13","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f93c599f42f100050b7d59882802a50fe2afc96","datavalue":{"value":"oriented path","type":"string"},"datatype":"string"},"type":"statement","id":"Q2048544$0982C3C2-8364-4CAC-8E09-889D66CBB8CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d945cfe7d51487fc4fdf40e0e7918af3eb157d04","datavalue":{"value":"undirected cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q2048544$C1220F70-6BC6-4EB2-8054-B34AC1CDEB30","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":"Q2048544$4C0A2CA7-2C62-4703-A448-38500AA71383","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cdb0bd01bc6d4395cdd1529da80c72970460ddf2","datavalue":{"value":"W3010794942","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2048544$E498F291-5B38-4E92-83E0-66818C6318B4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a253dfedc634c3617fd93c34bc6b364162d4ecb1","datavalue":{"value":{"entity-type":"item","numeric-id":3791169,"id":"Q3791169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048544$7F96D6BD-4A6A-4934-847D-6CF2013B2027","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c74b7954c4e96ea2e676044196dc57d8b06146d","datavalue":{"value":{"entity-type":"item","numeric-id":2395457,"id":"Q2395457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048544$54A45D65-96BD-4A83-B9D4-C96842F908C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bdd250a45275500c245c98aa669a4cad3fe76cd","datavalue":{"value":{"entity-type":"item","numeric-id":5545303,"id":"Q5545303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048544$F2F00BC2-D932-4483-8D6C-0C31CD353C02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c21b97a1c274a5f75c018b79e9170da70257e50a","datavalue":{"value":{"entity-type":"item","numeric-id":5617553,"id":"Q5617553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048544$8CA5928A-7343-4ECD-BF29-D9CF533AAF06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5028065ceb61d7fbbcc8d74c873e6a965e0cc43f","datavalue":{"value":{"entity-type":"item","numeric-id":1110530,"id":"Q1110530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048544$2CB369EF-4FED-4164-8013-4049ECFDAEB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a633e84f28e974524d6f21199618016457237af","datavalue":{"value":{"entity-type":"item","numeric-id":4828516,"id":"Q4828516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048544$403A7F95-8BA9-48E7-AF2F-207ED5D4327F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"676176244725ad505d74fb063bc848b0d22d5ecc","datavalue":{"value":{"entity-type":"item","numeric-id":751667,"id":"Q751667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048544$C8D66E1E-1E55-4AE7-876C-C7389D7DB3AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"201de901ea95934bb102d54c382e7d0e410a0681","datavalue":{"value":{"entity-type":"item","numeric-id":1316647,"id":"Q1316647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048544$09FC1F80-1EB4-433D-943B-4301A62E8A50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b85e726a9dea4d901959cd5845fa226b41795ec","datavalue":{"value":{"entity-type":"item","numeric-id":4837649,"id":"Q4837649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048544$57FEEA19-EFBD-4376-A93D-AC2B3CD36A96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2267e402f097d8fe53c383856603a9e564f62ec0","datavalue":{"value":{"entity-type":"item","numeric-id":2462336,"id":"Q2462336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048544$9AB6E1C0-7DE5-48A5-9ECB-2B83B1E5463F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a15f0d5d06eb8f30a0d71ed29f48211a4f9dca39","datavalue":{"value":{"entity-type":"item","numeric-id":1850486,"id":"Q1850486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048544$C1060A9B-0676-4DD5-8764-F4E0E6A7B288","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31ffb594742705f0bb995ca7f67a18307c6b90a4","datavalue":{"value":{"entity-type":"item","numeric-id":5470800,"id":"Q5470800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048544$B570A784-218E-4242-B8EA-284CCEF398D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70b64c36f147f07e9132a04121c3023f0fae5bd8","datavalue":{"value":{"entity-type":"item","numeric-id":5539654,"id":"Q5539654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048544$946B8F51-70D7-49B0-974D-B856340E7C55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77ab35126ffbaac542fe1dfc3cbbdaafbc1fb762","datavalue":{"value":{"entity-type":"item","numeric-id":3958485,"id":"Q3958485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048544$AF6ABB44-60A6-44BC-93BA-54B25DD104A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c9d5f997ad4e98faf4457159b52d629b48df3f6","datavalue":{"value":{"entity-type":"item","numeric-id":5331780,"id":"Q5331780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048544$C2EBF4DA-A1F4-4724-B375-6DC7604FFB0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16fa441ee502da32a1be25c5ce44d3fc6fb06b6f","datavalue":{"value":{"entity-type":"item","numeric-id":4857535,"id":"Q4857535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048544$C5746DF1-41E6-4C14-A5F5-A1DFC5D9A714","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"abc5ac6d4ff0054c7989161cbb2cec8e91082161","datavalue":{"value":"bafkreick46k4rdarorkjp56m4kh4ebplpivx2is7xki7ccteojank6o22m","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2048544$39ADAC27-A691-455C-A215-A6C5C177C058","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ffbf3b6ed1aca6b4d792a6a9778964f213c5667e","datavalue":{"value":{"entity-type":"item","numeric-id":1336655,"id":"Q1336655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee3dbcd88b428cb1f277a98ac173430c445106f1","datavalue":{"value":{"amount":"+0.7981317043304443","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":"Q2048544$B8C26E49-0F27-4816-A0EB-3C0DE3643361","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bcac02117f845b50a1dcc047fcc780634d1169f0","datavalue":{"value":{"entity-type":"item","numeric-id":4823311,"id":"Q4823311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee3dbcd88b428cb1f277a98ac173430c445106f1","datavalue":{"value":{"amount":"+0.7981317043304443","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":"Q2048544$977E1E0F-6749-45DB-9E9E-F9C0FD6DB7FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02de5f49e485232d89caa609d459c7c1b733899a","datavalue":{"value":{"entity-type":"item","numeric-id":4457317,"id":"Q4457317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da9b709a82e393a0b6b63fd9509fbc1ffff3b2f0","datavalue":{"value":{"amount":"+0.780283510684967","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":"Q2048544$620ADDE8-8CAB-4D8E-A744-1842927E9AFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17e66bf0668e601df639fd765b6c354bc2ddac63","datavalue":{"value":{"entity-type":"item","numeric-id":4837649,"id":"Q4837649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22f426a953b4dd8ff9a46c01bc2977bf6fdfca4b","datavalue":{"value":{"amount":"+0.7737599015235901","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":"Q2048544$4C7ECBE3-A8AB-4307-AB16-37337F13D91C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f8646f3603d9bd96e085da5baa9a6be1c663cf3","datavalue":{"value":{"entity-type":"item","numeric-id":1316647,"id":"Q1316647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a6cdd2acdcb92afe655b38ed681a33192093b46","datavalue":{"value":{"amount":"+0.7725103497505188","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":"Q2048544$38C4FB7D-DCA5-4D13-936E-2BAF37DD62F0","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":"Q2048544$F24EFF58-9F46-4A9A-B462-F614A79DCA0C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2048544","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2048544"}}}}}