{"entities":{"Q2380438":{"pageid":2391181,"ns":120,"title":"Item:Q2380438","lastrevid":73762896,"modified":"2026-04-14T17:11:04Z","type":"item","id":"Q2380438","labels":{"en":{"language":"en","value":"Large bounded degree trees in expanding graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5686988"}},"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":"Q2380438$D57B3F6E-60AA-48AB-9447-354791DB94FA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8a0793c5e6f665b3520e3dee39da4c2bcf45623a","datavalue":{"value":{"text":"Large bounded degree trees in expanding graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2380438$9898EDFA-36E6-4D03-B498-F7D2E34F7997","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f9776566d90cc52b1817a4e28b33a3ad165ad2f0","datavalue":{"value":"1184.05022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380438$4AB83384-8CEA-45C9-8DDF-BBD696C50B5C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f9158385d8dfa25fd1cbf34c726849285f5355cf","datavalue":{"value":{"entity-type":"item","numeric-id":189372,"id":"Q189372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380438$9BF0BF26-2BED-441C-A9FE-9E7252227039","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"58e9391d7892765e76758f4e8216eb3fab67e085","datavalue":{"value":{"entity-type":"item","numeric-id":2380437,"id":"Q2380437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380438$107A5880-4D03-454C-AAE5-6F41216A9973","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a8013bc00783240c57786649bc43e422121684be","datavalue":{"value":{"entity-type":"item","numeric-id":285062,"id":"Q285062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380438$6ECC9023-572E-4A47-A58D-91E79867890B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1377da21651e905f48a4ad4865918cecbf085e48","datavalue":{"value":{"entity-type":"item","numeric-id":313784,"id":"Q313784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380438$97913A5F-DD32-486A-B8E8-5250CC69D674","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":"Q2380438$E1C00FF5-EF3B-4E9F-9229-8679C979F6B8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"143e8774a45e663375c24b3b343519cf2933b18c","datavalue":{"value":{"time":"+2010-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2380438$E7206DFB-A5BA-47E2-9DE4-CE0C826E8622","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9a84ec022b621e1d1a7f0b3f63d6c959e25e7adb","datavalue":{"value":"https://eudml.org/doc/233109","type":"string"},"datatype":"url"},"type":"statement","id":"Q2380438$E5530592-C360-4D2C-B929-AEDE12D27E23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"a020667ab80424bb8e00a1f9da1fd917e4dda3c5","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r6.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q2380438$F879E353-47F7-48F0-9307-56E6E615F1F0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0ee2332440965147683b91bf7dcf717ec6f4b642","datavalue":{"value":"Summary: A remarkable result of \\textit{J. Friedman} and \\textit{N. Pippenger} [``Expanding graphs contain all small trees'', Combinatorica 7, 71--76 (1987; Zbl 0624.05028)] gives a sufficient condition on the expansion properties of a graph to contain all small trees with bounded maximum degree. \\textit{P.E. Haxell} [``Tree embeddings'', J. Graph Theory 36, No.\\,3, 121--130 (2001; Zbl 0967.05029)] showed that under slightly stronger assumptions on the expansion rate, their technique allows one to find arbitrarily large trees with bounded maximum degree. Using a slightly weaker version of Haxell's result we prove that a certain family of expanding graphs, which includes very sparse random graphs and regular graphs with large enough spectral gap, contains all almost spanning bounded degree trees. This improves two recent tree-embedding results of \\textit{N. Alon}, \\textit{M. Krivelevich}, and \\textit{B. Sudakov} [Combinatorica 27, No.\\,6, 629--644 (2007; Zbl 1164.05032)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380438$34862F9E-D787-4745-910C-52FF39AB91CC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380438$EBFA44F3-2B09-45BE-9E09-B077B95FD3C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380438$11C96E06-29C5-498C-A2B2-B1F4EC52698F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380438$BE66C3FE-0F48-4EE7-97D2-956AA9E7B3B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"505dab9721154d1029d881b944cbf9d233b6d0c1","datavalue":{"value":"05D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380438$4E8A5583-6503-4B87-9AE3-5723FA3AFD17","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e02f429d6819d1fd969558f36b854dfabb29663f","datavalue":{"value":"5686988","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380438$8FA76296-7A3D-4964-9CC8-DC4F2D2D3CFB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"47c557571a5c8705d9ea0036223c0c5d8f5c1f7f","datavalue":{"value":"expansion properties","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380438$0A10F39C-FAB8-409D-A8F9-1026DB1FF112","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"17654d080aced196d886b872db07339536e06ac3","datavalue":{"value":"small trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380438$63ED8EA4-1CF4-49A1-B213-D9849BBD89F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78d7c81f47c453cbfcdcfa0d00441d5371e3fa1e","datavalue":{"value":"bounded maximum degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380438$87BEFF10-9042-4076-9543-C093B536B56A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0bdb65590d16b6c0d3f7eaaf3f9666bded37dfd5","datavalue":{"value":"sparse random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380438$56437727-1C7E-456E-9414-F0B6156DFBD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"37c36aa081a4c295bbccc99aac3f3a04b9de0cf9","datavalue":{"value":"spectral gap","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380438$B1DD32EC-BCAC-4C7C-B012-D3B964DD0AC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdb76054d5e62b4d91d8ebd24a4bf814a839263f","datavalue":{"value":"spanning bounded degree trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380438$B127D57D-62F0-422A-B86B-371085E92382","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":"Q2380438$7B024A6D-90E3-4E28-9C2F-033C0D399319","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"9b874ebf8a31c630f7545100b685f0679a344b1f","datavalue":{"value":"bafkreie4eqbsxuaphjxkmm6bawswvddd6m5h7rqkd2sanwbhthpclyfbde","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380438$B4FABA7B-FEB5-45DA-A71A-845329599885","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80498d0f9c87e668c6c562cdf04f4fce35faba21","datavalue":{"value":{"entity-type":"item","numeric-id":950331,"id":"Q950331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c1a88f363d684022e0fc7bde7c001f8dead2e70","datavalue":{"value":{"amount":"+0.898365318775177","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":"Q2380438$563C5FDE-A520-4591-81E8-C6352C273303","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88f035a30c56de03c2967888fc0bbff93ec53580","datavalue":{"value":{"entity-type":"item","numeric-id":1010862,"id":"Q1010862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64922c51dda48d87324458da3a337fdfc07ab33f","datavalue":{"value":{"amount":"+0.856778085231781","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":"Q2380438$E2F2EB57-C134-44BA-B8D2-D01EDE75E769","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23b600c1c5fa144f4f81dae4bf44d1a2bac48f64","datavalue":{"value":{"entity-type":"item","numeric-id":1092058,"id":"Q1092058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c30a3d51c4896b4b7e22b56e069c41b5de99e91b","datavalue":{"value":{"amount":"+0.8422702550888062","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":"Q2380438$F29D2A27-DF24-49F5-B8E1-457DFDC49766","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c81548eca08efca93ceb42a4ba32503093275d8d","datavalue":{"value":{"entity-type":"item","numeric-id":5743497,"id":"Q5743497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"beae0e54342230ea2d1d05b558811df0a71d9831","datavalue":{"value":{"amount":"+0.8256687521934509","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":"Q2380438$50533938-F959-4CC0-91FC-65DB649F5DF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"653d114435bf29f73889d5b8e644d1bac4824e2f","datavalue":{"value":{"entity-type":"item","numeric-id":3013142,"id":"Q3013142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29d83538aacdc2f9acdee796ae194f7a1a6ba2df","datavalue":{"value":{"amount":"+0.8127924203872681","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":"Q2380438$EF122DEB-ACBD-412B-BE0D-B7FBD0CEE9EA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Large bounded degree trees in expanding graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Large_bounded_degree_trees_in_expanding_graphs"}}}}}