{"entities":{"Q1226502":{"pageid":1237251,"ns":120,"title":"Item:Q1226502","lastrevid":69939603,"modified":"2026-04-13T11:21:40Z","type":"item","id":"Q1226502","labels":{"en":{"language":"en","value":"On sparse graphs with dense long paths"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3513821"}},"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":"Q1226502$107BC62B-B4A4-4AE6-B865-02B5817ABABE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"186247e38626732a823fdd3453e03a3789bd150a","datavalue":{"value":{"text":"On sparse graphs with dense long paths","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1226502$F679041B-C695-460C-8F0C-D064234205ED","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3d91a899ab8fab5c042b1bfd120718a61752f393","datavalue":{"value":"0328.05123","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1226502$8F8DCD6A-937D-4FCD-902F-A9160B05904C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6f28bf58862f4188659bd4cc3b30e075199f2e5b","datavalue":{"value":"10.1016/0898-1221(75)90037-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1226502$ECF1CC52-D8F2-4845-95EB-E764D59272CB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e043dc28119e45fe4c5adc4ff22403979bc60e85","datavalue":{"value":{"entity-type":"item","numeric-id":1065803,"id":"Q1065803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1226502$68FAB393-937D-4D81-B060-345F61358103","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fb00475fd567190194461a0f087df1793eeae7c4","datavalue":{"value":{"entity-type":"item","numeric-id":6480801,"id":"Q6480801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1226502$107CD662-CAE0-4A6D-9DFE-C94C2A71BFAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"11ae3d44052578af232f86664e60399b2eea5845","datavalue":{"value":{"entity-type":"item","numeric-id":6480429,"id":"Q6480429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1226502$FFD8C40F-92E5-4118-83FB-9965D23A20A0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b5e8f5a4bedcdf1368f667e537d4925490c864ae","datavalue":{"value":{"time":"+1975-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":"Q1226502$42070BAF-E689-4A20-A899-9511A7526347","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"26f8f4911c38f97cc6244ff6ef62e75539878f84","datavalue":{"value":"An acyclic directed graph \\(G\\) is said to have property \\(P(m,n)\\) if for any set \\(X\\) of \\(m\\) vertices of \\(G\\), there is a directed path of length \\(n\\) in \\(G\\) which does not intersect \\(X\\). Let \\(f(m,n)\\) denote the minimum number of edges a graph with property \\(P(m,n)\\) can have. (Hereafter, \\(c_1,c_2, \\ldots\\) denote suitable positive constants.) Theorem. \\(c_1n \\log n/ \\log \\log n<f(n,n)<c_2n \\log n\\). The graph constructed in order to establish the upper bound on \\(f(n,n)\\) has \\(c_3n\\) vertices. In this case, the upper bound is essentially best possible since it is shown that for \\(c_4\\) sufficiently large, if a graph on \\(c_4n\\) vertices has property \\(P(n,n)\\) then it must have at least \\(c_5n \\log n\\) edges.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1226502$9D8BF3BB-D268-43A3-B703-AC4149ACF1A6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1226502$FECE8081-3445-4F36-8282-158A63E61182","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1226502$DB6ABDEA-6210-4686-A373-E7718848117B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"83610fa4ca570a832a765b4c358757dc4e59d270","datavalue":{"value":"3513821","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1226502$A04D8109-F6E1-45A1-B988-81C28787F880","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":"Q1226502$0944E833-8424-4303-AA5A-FFF5618A5233","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2bab8508f3be2ccb34c3f87dbfb71e4ae1808773","datavalue":{"value":"https://doi.org/10.1016/0898-1221(75)90037-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1226502$03FB43F6-E6EA-40EB-B150-8F88B434822B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"67db304ab28943594dec0d4bb429f3cadd4b86c9","datavalue":{"value":"W2066775922","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1226502$B491494A-B0C2-4BA9-9D2A-47CDD33F16AE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c4bf606a449c9953c484dbb8476ee3760f5a6c3","datavalue":{"value":{"entity-type":"item","numeric-id":3267900,"id":"Q3267900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1226502$CA93700A-64EE-4EA4-9DD7-369F51D9BEC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"381a960f503ac85a49306b64108f576aee192c7d","datavalue":{"value":{"entity-type":"item","numeric-id":3291948,"id":"Q3291948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1226502$F3C1CA41-95E3-4372-9AEC-EF3004C9174B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"293935db3834ff8b5d542ae1771b7c6cb66baa38","datavalue":{"value":{"entity-type":"item","numeric-id":85551,"id":"Q85551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1226502$7C4ADC28-4410-45F8-B7C8-3372B2A78A7E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5754425c28b4116cc08bd20bcac726ecc1834aee","datavalue":{"value":{"entity-type":"item","numeric-id":2844080,"id":"Q2844080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0dd1194d22bbcb8706c9cf7b03bc0e3b1d78d51","datavalue":{"value":{"amount":"+0.7625477313995361","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":"Q1226502$F9572B74-5995-4596-A5CA-25414F7E536A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14cf269be072eb458750797116134269bb620e4b","datavalue":{"value":{"entity-type":"item","numeric-id":3828039,"id":"Q3828039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d168b078e33ac2eb555b119a55f9f80f2a2f859","datavalue":{"value":{"amount":"+0.7517253756523132","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":"Q1226502$021F8BF7-32AC-419C-BD4F-F0307AA4F7E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dfb9e4d0a265b2bbf2c3f97bfdbe3b2b4a371b4d","datavalue":{"value":{"entity-type":"item","numeric-id":4294587,"id":"Q4294587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7a684f2e55407d728576f12b40424245fbae5ce","datavalue":{"value":{"amount":"+0.7514140009880066","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":"Q1226502$9DAF9054-DC58-4F69-8E78-17320C937C2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af5a05e84058063fb4e73cab1ff07a249a378e23","datavalue":{"value":{"entity-type":"item","numeric-id":3480068,"id":"Q3480068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"efc867224de779460f6fb896a146c889f9db9aa4","datavalue":{"value":{"amount":"+0.7506158947944641","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":"Q1226502$D4598E71-02E6-43B1-AE5A-091C8AE67A63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e7c500e73853e085b99ff93c1f0ecc152410177","datavalue":{"value":{"entity-type":"item","numeric-id":3347916,"id":"Q3347916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cadff7939e7b6b50cd11a5632aec8b2cac1ef127","datavalue":{"value":{"amount":"+0.7488858103752136","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":"Q1226502$47622999-FB14-4BDE-922E-20802D4CBE7C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On sparse graphs with dense long paths","badges":[]}}}}}