{"entities":{"Q1837701":{"pageid":1848443,"ns":120,"title":"Item:Q1837701","lastrevid":69311628,"modified":"2026-04-13T06:09:50Z","type":"item","id":"Q1837701","labels":{"en":{"language":"en","value":"Compactness results in extremal graph theory"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3801576"}},"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":"Q1837701$4DE5B8A5-81F2-4AB4-AD7B-AFFCBCB0BF84","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0a171fa167870a2043aafb7576460eb543cc65c5","datavalue":{"value":{"text":"Compactness results in extremal graph theory","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1837701$CE354278-5026-42D4-9B49-A15E4BB8D8CA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c3c1306773ae2a17f45d517ef99b1203b82d915a","datavalue":{"value":"0508.05043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1837701$453BA2E7-C625-420D-9D7F-6090EDA6B358","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3f810c8aef0ad8ff5dd91c06ecf2c0a18d22d745","datavalue":{"value":"10.1007/BF02579234","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1837701$8363397A-BB3C-4A95-9A42-667C4D473C39","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3a40a7c874481a1a229f505dcfb1443755c75490","datavalue":{"value":{"entity-type":"item","numeric-id":1175548,"id":"Q1175548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1837701$72A1D382-451C-4157-84B2-5C0BC75ACCB7","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":"Q1837701$749BC72C-5F70-46EE-8818-01018D73F0DD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1837701$174C6517-72AF-4CB5-99F4-99BB1CCFE155","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"47f57cd36df9e30d446df3867dc3917e4ea74654","datavalue":{"value":{"time":"+1982-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":"Q1837701$BA82A7C8-EEA5-42C5-ABA7-76E521FAB854","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e6f5936868113833ec7e41be43e55d284c3d2d4e","datavalue":{"value":"(From the authors' abstract:) ``Let \\(L\\) be a given family of \\dots 'prohibited graphs'. Let \\(\\text{ex}(n,L)\\) denote the maximum number of edges a simple graph of order n can have without containing subgraphs from \\(L\\). A typical extremal graph problem is to determine \\(\\text{ex}(n,L)\\), or, at least, to find good bounds on it. Results asserting that, for a given \\(L\\), there exists a 'much smaller' \\(L^*\\subset L\\) for which \\(\\text{ex}(n,L)\\approx \\text{ex}(n,L^*)\\) will be called compactness results. The main purpose of this paper is to prove some compactness results for the case when \\(L\\) consists of cycles. One of our main tools will be finding lower bounds on the number of paths \\(p^{k+1}\\) in a graph on \\(n\\) vertices and \\(E\\) edges \\dots a `supersaturated' version of a well known theorem of Erd\u0151s and Gallai.''    Among the theorems proved, presented in the context of open conjectures, are:    Theorem 1: Let \\(k\\) be a natural number. Then \\(\\text{ex}(n,\\{C^3,\\dots,C^{2k},C^{2k+1}\\})\\leq(n/2)^{1+(1/k)}+2^k\\cdot(n/2)^{1-(1/k)}\\). Theorem 2: \\(\\text{ex}(n,\\{C^4,C^5\\})=(n/2)^{3/2}+0(n)\\). Theorem 3*: Let \\(T\\) be a tree with a fixed 2-colouring: A graph \\(L\\) is obtained from \\(T\\) by joining a new vertex to each vertex of one colour class by disjoint paths, each k edges long. Then, if \\(\\text{ex}(n,L)\\geq cn^{1+(1/k)}\\), then is a \\(t\\) for which  \\[ \\lim_{n\\to\\infty}(ex(n,\\{L,C^3,C^5,\\dots\\})/ex(n,\\{L,C^3,C^5,\\dots,C^{2_{t-1}}\\}))=1 \\]  Theorem 5: If \\(f(n,d)\\) is the minimum number of walks \\(W^{k+1}\\) a graph \\(G^n\\) can have with average degree \\(d\\), then every graph of order \\(n\\) and average degree \\(d\\) contains at least \\((1/2)\\cdot f(n,d)-0(f(n,d))\\) paths \\(p^{k+1}\\), as \\(d\\to\\infty\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1837701$7B4E90B8-299E-4039-B49F-8813BDDB429A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1837701$8E88035C-B62F-40FF-8820-7A3A46ED4FD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1837701$17CBCEDD-6F7D-42BB-9BF7-999487A7A730","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1837701$FFEFD2F7-E56A-4608-8B84-3B285CEA8128","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d383250458923a9c0685422e7f47895be3088c54","datavalue":{"value":"3801576","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1837701$DEC504EC-0749-4513-A3CB-43DCD5B646DE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f5b085ded3183023af8db32fe027d8e782bfe876","datavalue":{"value":"extremal graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1837701$12882C58-58D1-4F7B-9A5C-87F2FDBF36F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f515edcbce20c6d04416ddc6b94e729d386d210","datavalue":{"value":"compactness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1837701$E3EF32A0-3950-46BB-B0B8-0A4AAC668679","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3cf527396198287728237f35682e7b4f98b27c3b","datavalue":{"value":"supersaturated","type":"string"},"datatype":"string"},"type":"statement","id":"Q1837701$FE94C7F7-579E-4405-BFF1-FB2569637FAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8415b13e13866b2a902e773eb49890a053b3a53","datavalue":{"value":"disjoint paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1837701$4C63D11E-D10A-4DC5-B371-6B9B736B30F3","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"fe3d16bd099ccc0380bbb1aa5a20b99353f9c733","datavalue":{"value":"Q56698343","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1837701$64929787-1287-4526-A87C-01FF4B56D376","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7d410aa128a8b8a63913c9594604f4ec3d0ad8b4","datavalue":{"value":{"entity-type":"item","numeric-id":590664,"id":"Q590664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1837701$51387B3E-1EE2-4448-BF1D-F18EEDE33D52","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":"Q1837701$4A7F9A55-A0F1-47CD-A46C-7AACCB002011","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"743567441e15bf22565808e2d39da6d0c9999d37","datavalue":{"value":{"entity-type":"item","numeric-id":5524327,"id":"Q5524327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1837701$CC4EED18-7488-4E38-954A-19544E982F2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d81d022f27d459c65117397e298a3e45690fb65b","datavalue":{"value":{"entity-type":"item","numeric-id":1844243,"id":"Q1844243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1837701$DF9A7512-B502-4407-8BC9-E5931682BE23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"344f697a74f08c27dbfe2d6124ad1eb1876a2d05","datavalue":{"value":{"entity-type":"item","numeric-id":5567713,"id":"Q5567713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1837701$19B6217F-F76E-44FF-85E8-B6D1DF9C984B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27b91fb34b309a1448e42736f924e3a5012ab649","datavalue":{"value":{"entity-type":"item","numeric-id":3253064,"id":"Q3253064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1837701$618F5BC4-6C73-4959-B42F-A91C469A5D3B","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":"Q1837701$FA8499C2-C61E-47A4-BCC6-8D280C602833","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63ada53980e8d3e7e8a0a401742a431780860804","datavalue":{"value":{"entity-type":"item","numeric-id":5825672,"id":"Q5825672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1837701$449AD30D-1F86-459C-AEE3-CF9A81924414","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e111f9913936978e22883dabfd8eab9e011ef2d","datavalue":{"value":{"entity-type":"item","numeric-id":3253804,"id":"Q3253804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1837701$586FE0E0-0CDF-4BD9-8580-EC140F6D7F5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d9a7a646983e7985d14ca337ef4847736cc412d","datavalue":{"value":{"entity-type":"item","numeric-id":5555547,"id":"Q5555547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1837701$F8232833-399A-4353-BB0D-72611BC0E4D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42447f984f8a20633c465465c174a3a999c1bcd4","datavalue":{"value":{"entity-type":"item","numeric-id":2529815,"id":"Q2529815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1837701$31DC2ED1-1882-4B18-B91C-606A1349BE9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47cab1c1eacf59b860b1530a672ea4191bd0cb2f","datavalue":{"value":{"entity-type":"item","numeric-id":3271848,"id":"Q3271848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1837701$0DF43188-9827-4CCF-BB4E-BF9CB3FD96F1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"73145178cd81935e9e62f7d18d9aa4b73b65d90f","datavalue":{"value":"https://doi.org/10.1007/bf02579234","type":"string"},"datatype":"url"},"type":"statement","id":"Q1837701$A5E71B07-DCBB-48C0-8FE5-54870B37223C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"eba74b28e7df3383993ca81a6f964e9d9481c17d","datavalue":{"value":"W2110805362","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1837701$5F370640-9B06-4907-9DEF-C28F57010D22","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"f595a666852ce7156ca63a27100e3ba3b23ea26f","datavalue":{"value":"journals/combinatorica/ErdosS82","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1837701$F3FC33C1-5E00-460A-9577-755402628FE6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3fc9acde789798d49e79bf141b127dccf6104f0","datavalue":{"value":{"entity-type":"item","numeric-id":3220623,"id":"Q3220623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e461ebdcb9fe6ef0e25a2d90aeb36caf721d862","datavalue":{"value":{"amount":"+0.7986491322517395","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":"Q1837701$C6A2DD83-30EE-4E16-B94D-5025ED58A086","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e74cfb03fbd4be54c196cabd6c9a8029cb6c6c9","datavalue":{"value":{"entity-type":"item","numeric-id":2957176,"id":"Q2957176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"592dfda7d226dd32306bc6431edb0a6a370a52d6","datavalue":{"value":{"amount":"+0.7897326350212097","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":"Q1837701$65E9A4F3-74EA-4C00-B761-3259C9ACA213","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e28beccd25cf1df71e8451a8f913a6aa16fa7bf9","datavalue":{"value":{"entity-type":"item","numeric-id":4154888,"id":"Q4154888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"842b272f67c16e4fa3b2ef7b8f81315811035e43","datavalue":{"value":{"amount":"+0.7870911955833435","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":"Q1837701$A9D13999-33F4-481D-9F91-0492AB4E0192","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4cfd7b1ea3a151540c524c7b2023031738e366f","datavalue":{"value":{"entity-type":"item","numeric-id":3312262,"id":"Q3312262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b03fec2db273c720996302add3318ad7bda6bf3","datavalue":{"value":{"amount":"+0.7858983874320984","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":"Q1837701$A3061E9C-FB27-4133-9D29-D2E52276D860","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69b7f571dedcac893de662c5695d8ef0947b3017","datavalue":{"value":{"entity-type":"item","numeric-id":3855211,"id":"Q3855211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58366c974fe700d340b02d48e08c00b2d7452b3b","datavalue":{"value":{"amount":"+0.7848251461982727","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":"Q1837701$C0ABE3C3-BE33-4AEC-9FC0-1CA0D6C66282","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Compactness results in extremal graph theory","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Compactness_results_in_extremal_graph_theory"}}}}}