{"entities":{"Q949775":{"pageid":951623,"ns":120,"title":"Item:Q949775","lastrevid":65610795,"modified":"2026-04-12T03:46:58Z","type":"item","id":"Q949775","labels":{"en":{"language":"en","value":"Cycles in dense digraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5355081"}},"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":"Q949775$1B82F739-62B6-4D72-9C66-F139E924E5D5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"902f50f1588f9082461b3821b6964c83ea224e0a","datavalue":{"value":{"text":"Cycles in dense digraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q949775$DA6F87D4-7D14-4939-9F20-CE88AF61E1C2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fecd3ac176bd93064dbcdf28e6d41d53d4b5c784","datavalue":{"value":"1174.05049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949775$67091580-2318-4E67-A15C-6FFD4DCF8A97","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"86791d2de8f741697c1a28c841b5e520b1ea6f17","datavalue":{"value":{"entity-type":"item","numeric-id":256974,"id":"Q256974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949775$31744499-723E-415A-9D13-07F5772EE1EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b7666b1aea36d852e5d73efdf8f9faa64e3f54f","datavalue":{"value":{"entity-type":"item","numeric-id":705887,"id":"Q705887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949775$F419FDA7-D7EE-4D7B-9B2E-2CE2DF8C82C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"459720d4850dd172d1b277faecde690558a64abf","datavalue":{"value":{"entity-type":"item","numeric-id":1627189,"id":"Q1627189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949775$242F63BE-7079-4E7D-AB76-4BBB082C54ED","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949775$8DB21D44-6788-467F-ABA2-286CCDAC9BA1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b4a05105c8454225903df775b1ba3fdbda7455a","datavalue":{"value":{"time":"+2008-10-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q949775$CAB8844F-9A5A-49EE-83D5-4489F3B6EB64","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"954a4a34da4d3beb4cda798c5eea0664813f20f9","datavalue":{"value":"https://arxiv.org/abs/math/0702147","type":"string"},"datatype":"url"},"type":"statement","id":"Q949775$8586BF5E-D46D-4DBE-A436-5FC68FAB75D4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"56798d925e9d21e497c09ea732e29805581f8208","datavalue":{"value":"\\(G\\) is a digraph containing no 3-cycles, and \\(X\\) is a subset of its edges such that \\(G \\setminus X\\) is acyclic. Let \\(\\beta(G)\\) be the minimum cardinality of such an \\(X\\). The authors wish to bound \\(\\beta(G)\\) with \\(\\gamma(G)\\), that denote the number of unordered pairs \\(\\{u, v\\}\\) that are not adjacent in \\(G\\). Their first result is that \\(\\beta(G) \\leq \\gamma(G)\\). They also exhibit an infinite family of digraphs for which \\(\\gamma(G)=2n^2\\) for any \\(n\\) natural, and \\(\\beta(G)= \\gamma(G)/2\\). It leads to Conjecture \\(\\beta(G) \\leq \\gamma(G)/2\\). These inequalities are in intimate relation to the Cacetta-H\u00e4ggkvist conjecture [\\textit{L. Cacetta} and \\textit{R. H\u00e4ggkvist}, in: Proc. 9th southeast. Conf. on Combinatorics, graph theory, and computing, Boca Raton 1978, 181-187 (1978; Zbl 0406.05033)] that asserts: If \\(G\\) is a digraph containing no 3-cycles, then some vertex has outdegree less than \\(n/3\\). The conjecture is verified for special graph, namely it holds for {\\parindent=6mm \\begin{itemize}\\item[(i)]if \\(V(G)\\) is the union of two cliques \\item[(ii)]\\(G\\) is a circular interval digraph.   \\end{itemize}} The proof techniques involve a four function theorem, that resembles but not equivalent to that of \\textit{R. Ahlswede and D. E. Daykin} [Z. Wahrscheinlichkeitstheor. Verw. Geb. 43, 183--185 (1978; Zbl 0357.04011)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q949775$FE40AF67-9456-436F-86ED-C1ED2BF504C8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"73456c3353ea197c90c73d5f0daaf3b9d502d311","datavalue":{"value":{"entity-type":"item","numeric-id":235726,"id":"Q235726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949775$7CF36F91-6BA6-4571-936D-6D01A5F1067E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949775$002C6E76-B79C-4842-AB5A-EE797B2F3CC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949775$752D5E2E-4DCD-4814-A76A-F29CFBA2E46F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949775$1C155D1A-1F2C-4303-A1FC-C0FA76164963","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ff64f5fb0933a0649381aee93539d87c5b5802b9","datavalue":{"value":"5355081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949775$CCD02751-4916-409A-8F44-8D56AA67EBC1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dcf267cbc3e04fdcfc3d3761f7ad8ebdabe8c51","datavalue":{"value":"cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q949775$B20FA9DE-8CEF-4A82-A390-78AC776DDA68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a830a1e37165494df85f3ebc75121c767ed416a9","datavalue":{"value":"Cacetta-H\u00e4ggkvist conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q949775$18A0DE06-B73E-48F4-96E8-1706E5607456","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7208cc8434bfbc3e214b4cf2b80a93d70d1ebafd","datavalue":{"value":"four function theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q949775$ECD56B4C-D9FE-4323-BF81-FEAF191676B2","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":"Q949775$ABEFD559-25B6-49EC-BED7-C30AD02D9FD6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"63170aa107bbe2cb0ef8c40c53fbc41d54e8e834","datavalue":{"value":"W1987195239","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949775$2C4F7EA2-9B96-4E1B-B373-BA46429884B2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7748c3f122e9e682729c02c7c3be84a5b05d9f9","datavalue":{"value":{"entity-type":"item","numeric-id":4128579,"id":"Q4128579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949775$D7E45896-08AB-4F5C-9629-CF8A369438F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b82631da6917417897f9de979a35be56476ede5","datavalue":{"value":{"entity-type":"item","numeric-id":4192089,"id":"Q4192089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949775$24FE46D6-234B-4C5F-A701-ACE3C0DA60EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"961d1302716aeacde2ccf5285877b5024a5fa7d7","datavalue":{"value":{"entity-type":"item","numeric-id":1010591,"id":"Q1010591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949775$59E25025-B53F-4B65-917A-657C41B32E28","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3dd205a8d7cade03d45da869c9d809fbeed33afc","datavalue":{"value":"10.1007/S00493-008-2331-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949775$92091357-F1D6-4226-A2DE-CE172600AAF7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4e7266e9b3f23a422daae30d1475396241c2ad7","datavalue":{"value":{"entity-type":"item","numeric-id":1010591,"id":"Q1010591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43585caad2e361127428d80ac3a771a8a16c0818","datavalue":{"value":{"amount":"+0.8500389456748962","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":"Q949775$AD9768A3-34C0-4F83-AE39-2D2740A050DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e737cc3a89761156a5c2495ed06591d12df48bee","datavalue":{"value":{"entity-type":"item","numeric-id":5399538,"id":"Q5399538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8647360662103cf785335f6a89c1ed1b5d5e12fa","datavalue":{"value":{"amount":"+0.8474786877632141","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":"Q949775$E1B88821-2489-4344-98D8-87ADF74A9A49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e31ff6e3fd24ba470f8c5daee172129a053c4c9","datavalue":{"value":{"entity-type":"item","numeric-id":1865152,"id":"Q1865152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74638a329cbfa2351ee392c8c5784d184a5e3656","datavalue":{"value":{"amount":"+0.8352879285812378","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":"Q949775$1F0E393D-BB06-4DC5-8C3C-492768B0FC60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb2586a5b30820328a472560efc12ebfacf6df67","datavalue":{"value":{"entity-type":"item","numeric-id":1942646,"id":"Q1942646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a5568814bd6589c574fd7cd473d341faf852e39","datavalue":{"value":{"amount":"+0.8352707028388977","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":"Q949775$42960A1B-8776-4B17-94D2-5E63399B33E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"801c6649b7ed9e017d1dfb3576e2f6eab220914d","datavalue":{"value":{"entity-type":"item","numeric-id":712265,"id":"Q712265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ef7287fec7d7c631e09cc5ad74faf0e9995e5a3","datavalue":{"value":{"amount":"+0.82745760679245","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":"Q949775$F5817FA5-700E-488E-9859-BA3B0B83C565","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Cycles in dense digraphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Cycles_in_dense_digraphs"}}}}}