{"entities":{"Q6872192":{"pageid":20729740,"ns":120,"title":"Item:Q6872192","lastrevid":75258154,"modified":"2026-04-18T08:51:47Z","type":"item","id":"Q6872192","labels":{"en":{"language":"en","value":"The largest subgraph without a forbidden induced subgraph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8146973"}},"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":"Q6872192$C03E7B67-053C-409E-A249-0FB44681D8BD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7b3bad293146e18c3859642732a933bbdb8a15ac","datavalue":{"value":{"text":"The largest subgraph without a forbidden induced subgraph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6872192$FB69F9B3-7903-491C-A4E5-27E64F969C9B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"75062f0a6b736782657939eaa718db72e83f8ab0","datavalue":{"value":"10.1007/S00493-025-00190-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6872192$A512646F-7F76-427C-B7BF-446607785949","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"576bcceabff8dce115427e52f43e894dfd6284df","datavalue":{"value":{"entity-type":"item","numeric-id":290804,"id":"Q290804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6872192$1AE2D662-3B8C-4521-9CC2-CD8EA786D157","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9e6198021e05f1f6cd4ded3ddf48dc9b0b86db1e","datavalue":{"value":{"entity-type":"item","numeric-id":322225,"id":"Q322225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6872192$4C587232-91E0-4AC9-AD40-0107EEC37F27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a8b7fcb1ec9530b8b138f7a8cd67e2e6a7f21996","datavalue":{"value":{"entity-type":"item","numeric-id":553635,"id":"Q553635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6872192$FAFF4DEE-0503-4F3D-B4FF-B95E7B232467","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":"Q6872192$A2DF4F23-3D21-45A3-8E7C-B7EA6E54A3E9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5f27bc108e2c2a8242e85036b909fd3db9af3d86","datavalue":{"value":{"time":"+2026-01-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6872192$3DC348A3-DEF9-4319-99A3-3453C027C136","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"68f854d1b2c623cedc7166d47a7829bf87dbb172","datavalue":{"value":"A property of graphs is hereditary if it is closed under taking induced subgraphs. Let \\(G\\) be a graph with \\(n\\) vertices such that the edge density between any pair of subsets of vertices of size at least \\(t\\) is at most \\(1-c\\), for some \\(t\\) and \\(c> 0\\). The paper considers the problem of finding the largest number of edges in a subgraph of \\(G\\) which does not contain a fixed bipartite graph \\(H\\) as an induced subgraph. The authors determine the answer up to a constant factor with respect to \\(n\\) and \\(t\\), for certain bipartite \\(H\\) and for either a dense random graph or a Paley graph with a square number of vertices. As an application, the result determines the largest subgraph with a hereditary property which misses a bipartite graph, and determine up to a constant factor the largest number of edges in a string subgraph of \\(G\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q6872192$A2D5F056-EB2F-43B3-85DF-BF9969DD5CBA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"033ae98111ea4a4d9ccdc87e4e91c764fa7980d1","datavalue":{"value":{"entity-type":"item","numeric-id":921953,"id":"Q921953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6872192$DB6D6540-52FD-4C28-94E4-09ACB3D70D46","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6872192$B14D43E8-CB08-41DE-BFD7-8B1E045E7DE9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c78e96eaacfa2f188a8f25f800067d1037002a82","datavalue":{"value":"8146973","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6872192$E0AD4D4C-ABC4-4373-BA15-7C7AEF99F54B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b6fac036d0386461048e4af513ab5529434c4260","datavalue":{"value":"forbidden induced subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6872192$83FD8CEC-7BB1-49D9-9932-6E1046AD4E87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a6018e21eb493b02b55291a49c7934ae5e17292","datavalue":{"value":"Tur\u00e1n-type question","type":"string"},"datatype":"string"},"type":"statement","id":"Q6872192$0F0FD306-4A91-4A7B-B231-3E60DE99D0FB","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":"Q6872192$E521E587-E4C0-420A-AEBB-568BC46214E7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The largest subgraph without a forbidden induced subgraph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_largest_subgraph_without_a_forbidden_induced_subgraph"}}}}}