{"entities":{"Q311564":{"pageid":313331,"ns":120,"title":"Item:Q311564","lastrevid":61002594,"modified":"2026-04-10T20:32:17Z","type":"item","id":"Q311564","labels":{"en":{"language":"en","value":"Counting trees in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6626803"}},"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":"Q311564$9CCFF141-DA19-4B55-8109-49032C57C94A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3de6c0a4406de8f0502292e2c9d74b98e81facf7","datavalue":{"value":{"text":"Counting trees in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q311564$7E536CFC-BFDB-4972-9A58-CB5307BA0E9C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1a18f1db11c4a69a27e989e338f2db8e1dd19581","datavalue":{"value":"1344.05074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q311564$B9155DED-102D-4DF1-8937-73D437585D22","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8444f9fccd215f879b6fe3e03b6423c5e05bd6c1","datavalue":{"value":{"entity-type":"item","numeric-id":311563,"id":"Q311563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311564$0F77774A-3623-4915-86C7-C87628C5F04F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3b2dc7fb86714f67c87c73e07c13ee1e0d7b9d71","datavalue":{"value":{"entity-type":"item","numeric-id":168649,"id":"Q168649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311564$A6E4B032-C857-4069-AA91-7ED5E8D8490A","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":"Q311564$D5098F67-39E9-44A0-8858-E0F816397301","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b5855202242268e2d32d9cba2484fa0b5d8a8d40","datavalue":{"value":{"time":"+2016-09-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q311564$C9C9CA8F-5167-4032-AA4E-E075A3D95912","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0df0f08ac84a9541d90a2a8d72bff8b03b2a3785","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p39","type":"string"},"datatype":"url"},"type":"statement","id":"Q311564$D70155EF-45B0-42F5-B0AE-2B560BCC7F4F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ce60197bf159bcf18204e0a7ecad6e2991db4ab4","datavalue":{"value":"Summary: \\textit{P. Erd\u0151s} and \\textit{M. Simonovits} [Combinatorica 2, 275--288 (1982; Zbl 0508.05043)] proved that the number of paths of length \\(t\\) in an \\(n\\)-vertex graph of average degree \\(d\\) is at least \\((1-\\delta)nd(d-1) \\cdots (d-t+1)\\), where \\(\\delta = (\\log d)^{-1/2 + o(1)}\\) as \\(d \\to \\infty\\). In this paper, we strengthen and generalize this result as follows. Let \\(T\\) be a tree with \\(t\\) edges. We prove that for any \\(n\\)-vertex graph \\(G\\) of average degree \\(d\\) and minimum degree greater than \\(t\\), the number of labelled copies of \\(T\\) in \\(G\\) is at least  \\[  (1-\\varepsilon)nd(d-1)\\cdots(d-t+1)  \\]  where \\(\\varepsilon = O(d^{-2})\\) as \\(d \\to \\infty\\). This bound is tight except for the term \\(1 - \\varepsilon\\), as shown by a disjoint union of cliques. Our proof is obtained by first showing a lower bound that is a convex function of the degree sequence of \\(G\\), and this answers a question of \\textit{D. Dellamonica} et. al. [J. Comb. 3, No. 1, 49--62 (2012; Zbl 1272.05084)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q311564$5879AC1F-2BEB-4007-A693-C541C88DCC4C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q311564$FE382174-04FD-4E5D-B29E-4FA144F678BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q311564$FAAF6DC0-1276-47C4-85B2-2CAFA8647C20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q311564$8FE5C70F-B100-4D04-B0D9-159066362756","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q311564$DB1D2B9B-9408-4014-8F7B-B596F966EE9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q311564$E586366C-8CA3-40F8-B576-E8785AAB0423","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q311564$AE9C4028-E5D2-41CB-891C-D5BF8E23BF31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q311564$8ED976FC-A536-4B6B-BBF4-6532B29FA028","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"214d784280be9882b8154bad8725565fbed0eb54","datavalue":{"value":"6626803","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q311564$53D54175-7122-4BA1-8978-56329B8F9E4B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ea8987bf69b2b7832f695141e3c43a4f160f651","datavalue":{"value":"embedding trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q311564$C88926D3-DFF5-47EE-B022-8701CB97AC47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e865dcf04feef79efcf163ac054d2ac37b7305b","datavalue":{"value":"paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q311564$12F7519B-19A9-4AA0-8144-ED9FFE14C362","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"37855f916737f223d8888545342b3978c164caeb","datavalue":{"value":"random embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q311564$73F3FCAB-140A-4BEE-8F8C-0F8A254A3F69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e0f187f2c9771f30b700db2c6dd0b89d5482a33","datavalue":{"value":"Jensen's inequality","type":"string"},"datatype":"string"},"type":"statement","id":"Q311564$C18E8598-13C5-4E27-BE61-1810784BF5E0","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":"Q311564$D4E35BD3-A261-4073-AD6E-9D7FA7500D2F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e0da50e9870f8cb226026bbc1ec21e379f11349","datavalue":{"value":{"entity-type":"item","numeric-id":1348665,"id":"Q1348665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311564$BE476319-9C42-49BA-8220-6A5F6F4685C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f56760be6c8faf06365155dda708fd0d045f4962","datavalue":{"value":{"entity-type":"item","numeric-id":5517742,"id":"Q5517742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311564$27F414E4-6C80-4F77-802C-DA43D1B24C3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca855deddc63408e4e32740660493921f7b6bd47","datavalue":{"value":{"entity-type":"item","numeric-id":353399,"id":"Q353399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311564$E699C413-41FE-491B-8469-927ABD18EB77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02aa720f0fa82e3addfed9feff58641822d76a93","datavalue":{"value":{"entity-type":"item","numeric-id":1837701,"id":"Q1837701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311564$C47BAD10-9495-49D4-924A-1D09FFA44F4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a74ae225fc555eb81f4e5c170f572b8459f594fd","datavalue":{"value":{"entity-type":"item","numeric-id":3363325,"id":"Q3363325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311564$072075E5-0871-48F9-BE66-3CE2EA40A76A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afa04bcf31d77e7b71b66916590c273cb6c4bcdc","datavalue":{"value":{"entity-type":"item","numeric-id":403573,"id":"Q403573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311564$2AE9ADB8-C6B3-4889-A6A0-E6F1B2CAE9CE","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"c4b6526371c6b1747280b9028e51cddc8e394532","datavalue":{"value":"bafkreie64z62fae3e2fvmuggjlrrosqvfj7hsrfz6qphlouwfpnz3tabpy","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q311564$1F6FDCC9-46A3-4B64-963F-1AD02BF6367B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43300ff4c1e027e144d79faa1e6f7f2ad8e4a754","datavalue":{"value":{"entity-type":"item","numeric-id":353399,"id":"Q353399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4a87065555aee95eb9c1c6c0a24c11e03a58820","datavalue":{"value":{"amount":"+0.8789067268371582","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":"Q311564$4CEC1D35-1EE6-417F-B9B3-0CFB05CF0FED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6edfd1d9002024b641e765584f0a02276b3988f","datavalue":{"value":{"entity-type":"item","numeric-id":3114975,"id":"Q3114975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"737f4dbf67b77a18f8614e8c90ae4dba18bd9072","datavalue":{"value":{"amount":"+0.8028548955917358","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":"Q311564$49EE1DE3-AF51-485B-BEC4-EBD2C0C2F865","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"556e67ee5e44d0181b4283bb87bfe3369ab82dd7","datavalue":{"value":{"entity-type":"item","numeric-id":4631099,"id":"Q4631099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26b60cc7f0980cc0b10627c89d07fe77d95f0da2","datavalue":{"value":{"amount":"+0.7839263677597046","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":"Q311564$809F48AA-7E69-4081-8597-71A2502ADCFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ad38ca371f82b319e6fc84eb6eeba90809871ea","datavalue":{"value":{"entity-type":"item","numeric-id":2712588,"id":"Q2712588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4099262ff9da45cdad2f014d19650030764239a6","datavalue":{"value":{"amount":"+0.7704868316650391","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":"Q311564$5E77E204-23FF-4F3D-87F3-29F14EC54127","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94946d6f9e003885521df3edf20628bed6d93b66","datavalue":{"value":{"entity-type":"item","numeric-id":1357755,"id":"Q1357755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02e50d6d80dff818511af1473f2c12ab40ff8b4e","datavalue":{"value":{"amount":"+0.7704864740371704","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":"Q311564$780072DD-CA3B-4680-B20E-CB7289E760F7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Counting trees in graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Counting_trees_in_graphs"}}}}}