{"entities":{"Q528999":{"pageid":530766,"ns":120,"title":"Item:Q528999","lastrevid":62516082,"modified":"2026-04-11T06:36:50Z","type":"item","id":"Q528999","labels":{"en":{"language":"en","value":"On the Caccetta-H\u00e4ggkvist conjecture with a forbidden transitive tournament"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6719989"}},"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":"Q528999$EBA5C0C3-376E-436F-8C03-8F511ABCEA6B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4e843c467384e567267fa9dfa9cd77072e23e5e5","datavalue":{"value":{"text":"On the Caccetta-H\u00e4ggkvist conjecture with a forbidden transitive tournament","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q528999$C4A0F434-2959-4A39-9ECD-DCA79504DF2E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d93c80f5701378e82ed2fb57bb640fb9b52b4e77","datavalue":{"value":"1361.05059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528999$07E59929-F0DA-40D9-B424-F814877195E6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"814777841608649a46c3af1c5707b34163ccd36e","datavalue":{"value":{"entity-type":"item","numeric-id":473102,"id":"Q473102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528999$2DDE854A-E01C-4783-8527-9F2BFF1FC0A5","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":"Q528999$4B40C599-1D7C-45EF-A37A-642DF3ABDC3E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"46a30028c10f94c4944c801c86f2de5dd37da0f3","datavalue":{"value":{"time":"+2017-05-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q528999$54377331-7E4C-4B82-A867-BD615450B9D7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0559c06f09a51e723bcae203c3f3272f0454a568","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p19","type":"string"},"datatype":"url"},"type":"statement","id":"Q528999$9E2DBA15-63C7-4BAF-9580-F9009BD65CA9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"42f1c5c2d661b155c680819baa1e79585214161e","datavalue":{"value":"Summary: The Caccetta-H\u00e4ggkvist conjecture asserts that every oriented graph on \\(n\\) vertices without directed cycles of length less than or equal to \\(l\\) has minimum outdegree at most \\((n-1)/l\\). In this paper we state a conjecture for graphs missing a transitive tournament on \\(2^k+1\\) vertices, with a weaker assumption on minimum outdegree. We prove that the Caccetta-H\u00e4ggkvist conjecture follows from the presented conjecture and show matching constructions for all \\(k\\) and \\(l\\). The main advantage of considering this generalized conjecture is that it reduces the set of the extremal graphs and allows using an induction.   We also prove the triangle case of the conjecture for \\(k=1\\) and \\(2\\) by using the Razborov's flag algebras. In particular, it proves the most interesting and studied case of the Caccetta-H\u00e4ggkvist conjecture in the class of graphs without the transitive tournament on 5 vertices. It is also shown that the extremal graph for the case \\(k=2\\) has to be a blow-up of a directed cycle on 4 vertices having in each blob an extremal graph for the case \\(k=1\\) (complete regular bipartite graph), which confirms the conjectured structure of the extremal examples.","type":"string"},"datatype":"string"},"type":"statement","id":"Q528999$F34AB710-0540-4D73-AA17-75EE262D9AD7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528999$D9A580A6-FF51-44B3-A1F2-2F1F3FEF489C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528999$FE32D98A-FD5E-4C4B-BA26-BAB85F7C456D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528999$694626D3-3CC7-4DD3-ACED-F739CBB3F20F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"13f7dfd0266a806ea57a0a6878a0e77f63be6993","datavalue":{"value":"6719989","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528999$72C09892-0A30-410F-B675-C3E4CB0E4438","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6bf023653318cc5b8c727563611596d2cf1a818a","datavalue":{"value":"directed graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q528999$BC8F18B0-7712-489B-B00C-D84C437BF94A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1cef4886cd87e3dd0ff9c6187d84ddbd09840f6","datavalue":{"value":"transitive tournament","type":"string"},"datatype":"string"},"type":"statement","id":"Q528999$736E7358-1BE4-4013-B42B-55FE41640D9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b3a99f9e205dbb8e18f1da9f3c825b8c789b9338","datavalue":{"value":"directed triangle","type":"string"},"datatype":"string"},"type":"statement","id":"Q528999$B1D1F9F2-F9CF-4D1E-9DEC-3DD6329CFF93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e54be5b3a85951dfe34f5edae1727cc89e2ac22","datavalue":{"value":"minimum outdegree","type":"string"},"datatype":"string"},"type":"statement","id":"Q528999$5B5C9D52-D418-46C2-8ECC-D4C5DA90ABC6","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"4a7f62aa8cbf94b3e8bbd8eae8f211a1d088dc1f","datavalue":{"value":{"entity-type":"item","numeric-id":18890,"id":"Q18890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528999$8939026A-303B-4783-A1B9-5D7D4D1F487D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"8bf42d0fd66acf369e3d5d44d7ebef6adc7ae452","datavalue":{"value":{"entity-type":"item","numeric-id":56651,"id":"Q56651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528999$69E8D6F5-0C44-4A6E-A933-99D041248258","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":"Q528999$8855055F-7FCF-467D-A77C-54C97671B8F8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"18c1b7f935026dea5d2d93133a41c67aa05b978b","datavalue":{"value":{"entity-type":"item","numeric-id":3081326,"id":"Q3081326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528999$06EB8E63-C57A-45A7-90EE-F5CC917C5311","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7deba73fdb112b3da07fb87529d67681a95a2043","datavalue":{"value":{"entity-type":"item","numeric-id":896063,"id":"Q896063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528999$9B17EE1D-B390-4272-8765-537548EED93B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3649d985850873f8271596374dd2cc674be92e4","datavalue":{"value":{"entity-type":"item","numeric-id":1356730,"id":"Q1356730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528999$CC4B0FBA-ECC3-4DFB-9390-9FC1BB3EFE54","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":"Q528999$0E3775AC-6A83-4613-B07A-7E06A9658793","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88b1b1c2a7eaf25a5acc36a606ed15ab105a4d77","datavalue":{"value":{"entity-type":"item","numeric-id":797594,"id":"Q797594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528999$BCA553CC-1210-44AE-A2F1-03BB707A7908","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9e501ca680b2695df83f500c96cff1554a95158","datavalue":{"value":{"entity-type":"item","numeric-id":4903261,"id":"Q4903261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528999$BE62A45A-63C6-4744-993A-8B602B865770","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5eb49d0847d218aee975d9eedee95750bb88e3aa","datavalue":{"value":{"entity-type":"item","numeric-id":713972,"id":"Q713972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528999$CF8F8A6A-1033-4FB8-A4C9-F4A1B686949C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3eda837bdc608b13a9b53368f46afa6757823700","datavalue":{"value":{"entity-type":"item","numeric-id":2312602,"id":"Q2312602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528999$96D21AAF-F6C7-4367-886D-D0B2AF96F7F2","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":"Q528999$A997827F-2E15-41B6-AEAF-F63557D00196","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"690c6260f203844fca8512a3e6bbd052ab73ad2f","datavalue":{"value":{"entity-type":"item","numeric-id":1101462,"id":"Q1101462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528999$19BCCCA5-8E40-4C2E-845D-318A42E5AE42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b45f328d574cf59cf025e8b482c38d2c7445a229","datavalue":{"value":{"entity-type":"item","numeric-id":1940382,"id":"Q1940382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528999$B6EC25C3-B391-4D7A-A4DE-71F333A6AACF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8baff4ccb8370f1795c8230796880d5e15f1c4d","datavalue":{"value":{"entity-type":"item","numeric-id":580357,"id":"Q580357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528999$F526424F-016D-4A3E-A60E-67EAF1EDDE69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"541b793255a2075a6283a268b847326c4f5e912b","datavalue":{"value":{"entity-type":"item","numeric-id":4899293,"id":"Q4899293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528999$2E5286E8-C047-4E4E-9F8F-4506D92A254B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8de9d39d5093c058c851283dff120fe881d725b6","datavalue":{"value":{"entity-type":"item","numeric-id":1112060,"id":"Q1112060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528999$5833559C-D673-46EB-9463-C50AC96129A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23acee77d1f4befa62be3cb55faa63af1aacf1ed","datavalue":{"value":{"entity-type":"item","numeric-id":5397739,"id":"Q5397739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528999$E3AB85A1-ADD4-4A72-B799-3C1CFF276BE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d57b3f2adafcc7706fdac957e963ce62b219e8ac","datavalue":{"value":{"entity-type":"item","numeric-id":5444699,"id":"Q5444699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528999$436F6960-0734-4FEF-812E-8828D5583E07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"249a2c832df488f3c22076a4e99eb9270e2778ae","datavalue":{"value":{"entity-type":"item","numeric-id":2853341,"id":"Q2853341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528999$2744D8B0-5A06-4513-8EDC-E68D87E77986","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c993f9a8575d60122642ae4e61b1fe3b3585003","datavalue":{"value":{"entity-type":"item","numeric-id":3527546,"id":"Q3527546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528999$100D5DDF-28B4-4FDD-8B2E-92163700661D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fb5d334836c4a3a38b52a50a08d46c95935990e","datavalue":{"value":{"entity-type":"item","numeric-id":1127878,"id":"Q1127878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528999$5582F9C9-59D7-4135-AD84-A475B45A6ED6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdeb1f6cb54de8b955a7308c648ec27d62b02825","datavalue":{"value":{"entity-type":"item","numeric-id":1969785,"id":"Q1969785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528999$20F33942-24A5-4F4B-8D78-90855D0467D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29391bc396dbc8504cef4ff5792bc8b724a3979d","datavalue":{"value":{"entity-type":"item","numeric-id":1865152,"id":"Q1865152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528999$5EF760BD-6393-416A-9E7A-01050724280E","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"be7123818cb20bb9707d09749869d037f9237c1d","datavalue":{"value":"bafkreiatemksi5om3azidgpzva4byltijodgkevgnrw7oh6bnffor25aci","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528999$DDF7717B-A734-40B6-BD94-61324A154BE5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26f1b1f7eda3d202594341b153329e4e7cb7bf68","datavalue":{"value":{"entity-type":"item","numeric-id":2853341,"id":"Q2853341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36ac15299b22f4d75eaf8b3c1c32fe3ce878fb41","datavalue":{"value":{"amount":"+0.9110981225967408","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":"Q528999$78364223-1BEC-4D5C-A734-C871CCED0DB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9bd43416172c2c1d2d0f2f84de64366c9eed1550","datavalue":{"value":{"entity-type":"item","numeric-id":389212,"id":"Q389212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d75bf4531e42a79d21807686eca570673661fbc","datavalue":{"value":{"amount":"+0.8507164120674133","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":"Q528999$3A544491-5B3E-4214-B169-FD670D278238","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":"eb3f887325d32ff7e18d1e3b35110c0de3804a7f","datavalue":{"value":{"amount":"+0.8268789052963257","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":"Q528999$19FB1A96-9FDD-4157-92F1-C5E43343070C","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":"ccbbdabd2aa64aa16c03d1243f1bf8901b04f9e6","datavalue":{"value":{"amount":"+0.8252463340759277","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":"Q528999$FFAF74BD-04C5-4E49-98E8-450AE161B36B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the Caccetta-H\u00e4ggkvist conjecture with a forbidden transitive tournament","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_Caccetta-H%C3%A4ggkvist_conjecture_with_a_forbidden_transitive_tournament"}}}}}