{"entities":{"Q2112584":{"pageid":2123327,"ns":120,"title":"Item:Q2112584","lastrevid":57729096,"modified":"2026-04-01T03:30:42Z","type":"item","id":"Q2112584","labels":{"en":{"language":"en","value":"The covering threshold of a directed acyclic graph by directed acyclic subgraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7640604"}},"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":"Q2112584$B956B01B-6095-43F3-9BDC-C857873529C0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"adea007d0fbd1789e270fcdc203414660c1a4ccc","datavalue":{"value":{"text":"The covering threshold of a directed acyclic graph by directed acyclic subgraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2112584$216F5FD5-6D73-44D1-9F4E-D929FB8BD28B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3b957634f0486dd924d32a70fbdfdb0eef4bf22d","datavalue":{"value":"1506.05178","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2112584$A5CD0FAF-BC3F-4C9C-996F-BABE2E6FDD6A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8e17c222111e8a6e0bd485dcc447f38b13cbd1ca","datavalue":{"value":"10.37236/11275","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2112584$E1293A66-E56B-4045-A1CF-42A1A1FE0E9D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"58695e9da83c43913be67e6d6be310d1075b58c8","datavalue":{"value":{"entity-type":"item","numeric-id":222643,"id":"Q222643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2112584$7BCADFCE-51D0-4B54-8901-8343D92EE9D7","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":"Q2112584$6A7A0426-14C4-4327-96A4-ACDF82819D2D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1ec9f957d33e6c7548612cea4907d9df7ba11c0c","datavalue":{"value":{"time":"+2023-01-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2112584$34D2A39C-BA63-4090-9BE5-09C868F69CDF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2b6453da0d0755eacb9ad29dca4f8d7099cfc5cf","datavalue":{"value":"https://arxiv.org/abs/2205.10880","type":"string"},"datatype":"url"},"type":"statement","id":"Q2112584$26F4A8A0-A471-47CA-86BE-17381A15437E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d71d1e699016048d1ebbb2891d1dcbb5e48e33c2","datavalue":{"value":"Summary: Let \\(H\\) be a directed acyclic graph (dag) that is not a rooted star. It is known that there are constants \\(c=c(H)\\) and \\(C=C(H)\\) such that the following holds for \\(D_n\\), the complete directed graph on \\(n\\) vertices. There is a set of at most \\(C\\log n\\) directed acyclic subgraphs of \\(D_n\\) that covers every \\(H\\)-copy of \\(D_n\\), while every set of at most \\(c\\log n\\) directed acyclic subgraphs of \\(D_n\\) does not cover all \\(H\\)-copies. Here this dichotomy is considerably strengthened.  Let \\(\\vec{G}(n, p)\\) denote the probability space of all directed graphs with \\(n\\) vertices and with edge probability \\(p\\). The fractional arboricity of \\(H\\) is \\(a(H) = max \\{\\frac{|E(H')|}{|V(H')|-1}\\}\\), where the maximum is over all non-singleton subgraphs of \\(H\\). If \\(a(H) = \\frac{|E(H)|}{|V(H)|-1}\\) then \\(H\\) is totally balanced. Complete graphs, complete multipartite graphs, cycles, trees, and, in fact, almost all graphs, are totally balanced. It is proven that:  \\begin{itemize} \\item Let \\(H\\) be a dag with \\(h\\) vertices and \\(m\\) edges which is not a rooted star. For every \\(a^\\ast > a(H)\\) there exists \\(c^\\ast  = c^\\ast (a^\\ast , H) > 0\\) such a.a.s. \\(G \\sim\\vec{G}(n,n^{-1/a^\\ast })\\) has the property that every set \\(X\\) of at most \\(c^\\ast \\log n\\) directed acyclic subgraphs of \\(G\\) does not cover all \\(H\\)-copies of \\(G\\). Moreover, there exists \\(s(H) = m/2 + O(m^{4/5}h^{1/5})\\) such that the following stronger assertion holds for any such \\(X\\): there is an \\(H\\)-copy in \\(G\\) that has no more than \\(s(H)\\) of its edges covered by each element of \\(X\\).  \\item If \\(H\\) is totally balanced then for every \\(0 < a^\\ast  < a(H)\\), a.a.s. \\(G \\sim\\vec{G}(n,n^{-1/a^\\ast })\\) has a single directed acyclic subgraph that covers all its \\(H\\)-copies. \\end{itemize}  As for the first result, note that if \\(h=o(m)\\) then \\(s(H)=(1+o_m(1))m/2\\) is about half of the edges of \\(H\\). In fact, for infinitely many \\(H\\) it holds that \\(s(H)=m/2\\), optimally. As for the second result, the requirement that \\(H\\) is totally balanced cannot, generally, be relaxed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2112584$C436C8C7-DFD0-4478-8503-BCD20F672917","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2112584$626806A6-C4A0-430D-924A-7B72C5AB595A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2112584$A000C121-1102-4ECB-96B2-0AF7EF9F29DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2112584$0C754662-8E97-4CEE-93D0-AEA1488B2E18","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e92d1e0914ef5fd5bf2fb12f24a2ea4893f78755","datavalue":{"value":"7640604","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2112584$8DEEF52E-777C-4C48-9C90-ACFC4F3B6405","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b79d09121acd0143dd0b56b490f50977890e9364","datavalue":{"value":"totally balanced graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2112584$9C31D6DE-554E-45C9-A7C1-BF710E9F8442","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"362efe259296f54993f41caba02deb0dc050bcea","datavalue":{"value":"fractional arboricity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2112584$14525B76-7E6B-49E2-BBEE-3947F3A66FD7","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":"Q2112584$2D514790-33CB-4B98-B5EA-72C59327A938","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7b9d8388793a918595359e3bb31c75f383f93d0d","datavalue":{"value":"W4313292980","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2112584$DF5C846F-97AA-4B65-8092-C1E4618927F6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bbaef82e8eb92dc4676d651d32794ea23b80ec1","datavalue":{"value":{"entity-type":"item","numeric-id":2798999,"id":"Q2798999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2112584$F8A71D45-12F9-462A-AE7B-3E8D4A593205","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a088e44e576e44e544bc7d4bf6f476921bc93e84","datavalue":{"value":{"entity-type":"item","numeric-id":4290084,"id":"Q4290084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2112584$E1CF3284-87E8-4B83-A624-C4888D929687","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9c871b87d413fbe774e5561b9dfa6d65e443049","datavalue":{"value":{"entity-type":"item","numeric-id":1114216,"id":"Q1114216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2112584$448093DD-C18B-4715-B8C0-B166DD93CD1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1841c44c9e95e6f4b6f04c036935d42beeb09868","datavalue":{"value":{"entity-type":"item","numeric-id":5408596,"id":"Q5408596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2112584$13C973A2-E6D6-4936-AAB6-263FA4C716CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"edd227013a96dd65d0289b90d93ff4bba0dd80ab","datavalue":{"value":{"entity-type":"item","numeric-id":3286850,"id":"Q3286850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2112584$ADCC96FB-18E8-4B98-9185-323E599B0D4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecb036f6d869da2ac039f66bf4869e802d505d14","datavalue":{"value":{"entity-type":"item","numeric-id":4870534,"id":"Q4870534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2112584$06DBF1AA-9D90-4D47-81C8-B05A2E66B200","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42bcb963f62a4cbbca21ce29c88d24d2cccd3004","datavalue":{"value":{"entity-type":"item","numeric-id":3137188,"id":"Q3137188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2112584$3C145497-E78B-473D-904C-1357B1317A94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15ce57d28a1b7429311ed0c4d3b9af30614f7204","datavalue":{"value":{"entity-type":"item","numeric-id":1906857,"id":"Q1906857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2112584$9CCF7EB1-33A9-4E0F-A49E-B1C96CF7EA4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61cbb541a390c1e38b45bfc8b5d33d0ebfdc5d1b","datavalue":{"value":{"entity-type":"item","numeric-id":1126218,"id":"Q1126218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2112584$BC1AB487-64EF-4237-9CFB-D05AE62EADC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bcc85ab9fa16bca6fc418f173746a68af16e1d0b","datavalue":{"value":{"entity-type":"item","numeric-id":3977078,"id":"Q3977078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2112584$9573FE7D-8CA3-4FBF-B6D4-BAD5A3EBA3E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79f40f6cac0c780a9b93fef04ad01fbee5da55dc","datavalue":{"value":{"entity-type":"item","numeric-id":5731396,"id":"Q5731396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2112584$7D2BB72C-1DB7-44AB-AF37-06A361EE96BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3bab370e90b5b957eb93ee78f9c1eba80bd3b3c","datavalue":{"value":{"entity-type":"item","numeric-id":4419290,"id":"Q4419290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2112584$A83AAB4C-2875-4C6E-AF0F-2CDA7A6874C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ccee73b0e548b561c250a58de15d07206cfc4ae","datavalue":{"value":{"entity-type":"item","numeric-id":5652683,"id":"Q5652683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2112584$97508CBD-D735-4917-ACC0-D70581509E23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2331d8897a45af68f232125ffd6b6910e5bc32c4","datavalue":{"value":{"entity-type":"item","numeric-id":2476274,"id":"Q2476274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2112584$4FB79A36-3D24-433D-9392-7EB322487EFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eff4a156064d6310727efebb4d2755d2eeb9ef31","datavalue":{"value":{"entity-type":"item","numeric-id":2205125,"id":"Q2205125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2112584$75AB9905-1C57-4C9D-997A-B0F78FE6E439","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"998ebc3e4502c0c9b23f4fae465ebaf33bd6f254","datavalue":{"value":"bafkreidb7hrj62vp2x7newxf4iuwmbfhmbl6gqfxo44j7twnjwava74xb4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2112584$649A5D01-4FE3-419B-89CF-23CE314ECCC4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12532a89ff00805953fa5dfcc20f537e9f5e0813","datavalue":{"value":{"entity-type":"item","numeric-id":2821620,"id":"Q2821620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"861fb6eb5a1b905a97c94ec3300f206ad8609ea2","datavalue":{"value":{"amount":"+0.7610986232757568","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":"Q2112584$1103ABC0-8DA6-4873-BB2F-609B1768BFAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5cc186a51d27785aa695f5c548edcd01f47f6633","datavalue":{"value":{"entity-type":"item","numeric-id":2857365,"id":"Q2857365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0620c4ee3c119312748d94e0eab9edc0d5d72007","datavalue":{"value":{"amount":"+0.7491349577903748","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":"Q2112584$031C8CD0-B1D0-4343-8B1C-8B308AFDE678","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2ec1a429e940c0f64268658a6fff86cecbdc2ab","datavalue":{"value":{"entity-type":"item","numeric-id":4366872,"id":"Q4366872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0090377c614b967c30079aaa3662593173b76921","datavalue":{"value":{"amount":"+0.7483828663825989","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":"Q2112584$A6CEAB6C-E145-46F1-9FFD-2AA030C7669C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15042f3e01c46ad6a9410881a45b3de9dfd0ca10","datavalue":{"value":{"entity-type":"item","numeric-id":2205125,"id":"Q2205125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0cc1cc5491bdfea42d04f0f95b84941406956de4","datavalue":{"value":{"amount":"+0.7481611371040344","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":"Q2112584$982957C6-2DEB-445F-8041-82D1D48E6557","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03d3bc132613169e005e95dc291cbc390ed6efe3","datavalue":{"value":{"entity-type":"item","numeric-id":2959903,"id":"Q2959903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0be13d7f4a27932e980a2b88303d8d0f9c6b9513","datavalue":{"value":{"amount":"+0.7473375201225281","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":"Q2112584$59F3988B-3F7D-4177-84B0-CF564BFBBEAE","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":"Q2112584$516092BB-B490-4B9A-839A-5F5092DEC783","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2112584","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2112584"}}}}}