{"entities":{"Q2121753":{"pageid":2132496,"ns":120,"title":"Item:Q2121753","lastrevid":73451658,"modified":"2026-04-14T16:02:49Z","type":"item","id":"Q2121753","labels":{"en":{"language":"en","value":"Independent sets in subgraphs of a shift graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7503029"}},"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":"Q2121753$6C39197B-F832-450E-AFBC-87D74665A61E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5844728d2ea5a197b2f0f716dc59e5302e2bd577","datavalue":{"value":{"text":"Independent sets in subgraphs of a shift graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2121753$7FC5D568-F043-4958-8A6C-362B57E90AA9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5a050bad7bbfa7751bca6f93099b878040ae8325","datavalue":{"value":"1486.05221","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121753$2B09E22C-3FCF-4355-B58F-BD512EF83D71","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"84ffa68e81aa4e17ddd1be69918b8e806fc2865b","datavalue":{"value":"10.37236/10453","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121753$94240CF8-787B-43BE-9072-5224C02C0AC4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d9a462613c5afbf590df9607324e22604daa3362","datavalue":{"value":{"entity-type":"item","numeric-id":501680,"id":"Q501680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121753$E68EB49B-3960-4532-8DB8-648E9C337A7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"477a0c780e886916763eab889b8f59bd0e4e18d6","datavalue":{"value":{"entity-type":"item","numeric-id":2121752,"id":"Q2121752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121753$F43E6484-CCEA-4FCA-998E-252CC03EB92A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c36b77bffff6f43e669d0380d3493f37a56849f","datavalue":{"value":{"entity-type":"item","numeric-id":168591,"id":"Q168591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121753$20572DDF-A68C-4A40-99DA-44DFDF38F9EE","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":"Q2121753$815CEE3F-A07A-44CC-8F6D-C19F7D4E3C82","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d249924fb2575f70cd1998ce670af4e4c548d4a2","datavalue":{"value":{"time":"+2022-04-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2121753$FB5C4392-B6A5-4F3D-9401-55C440753B48","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cbabcdc76ea8be88670672da23337d71b5f81ed5","datavalue":{"value":"https://arxiv.org/abs/2105.10971","type":"string"},"datatype":"url"},"type":"statement","id":"Q2121753$E26786CA-1EB2-447D-A181-7F0B5160653A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1623d1827865b29a298dcbbb2542149d49364c93","datavalue":{"value":"Summary: \\textit{P. Erd\u0151s} et al. [Ann. Discrete Math. 12, 117--123 (1982; Zbl 0501.05033)] proved that any subset \\(G\\) of vertices of a shift graph \\(\\text{Sh}_n^k\\) has the property that the independence number of the subgraph induced by \\(G\\) satisfies \\(\\alpha(\\text{Sh}_n^k[G])\\geqslant \\left(\\frac{1}{2}-\\varepsilon\\right)|G|\\), where \\(\\varepsilon\\to 0\\) as \\(k\\to \\infty \\). In this note we prove that for \\(k=2\\) and \\(n \\to \\infty\\) there are graphs \\(G\\subseteq \\binom{[n]}{2}\\) with \\(\\alpha(\\text{Sh}_n^2[G])\\leqslant \\left(\\frac{1}{4}+o(1)\\right)|G|\\), and \\(\\frac{1}{4}\\) is best possible. We also consider a related problem for infinite shift graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2121753$14BAAD9C-11B3-460D-8C2B-DF72A58FE836","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121753$06C5CF72-E290-49F7-9CC4-6DFB8690AAC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9729428b7f3faff6f70db9a7fa765e75946ff6b6","datavalue":{"value":"05C63","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121753$5B4C5620-593D-4F3A-A383-7A56C1AA2740","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b0d614bf59dee10966229dd8958d5bac25082e4b","datavalue":{"value":"7503029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121753$33330827-E6F1-4934-8A4E-6255EE255BC2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"31b8fced48ea55975a28d41090023efb0100b60a","datavalue":{"value":"subgraphs of large graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2121753$EB1FFBC8-1002-4D23-B2C1-376B0ADFC007","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2121753$8B9B9D84-98BB-4D99-AB92-942ED48D9406","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"95749dc4c2d2f08cb67d69896ee1bf3845cae76c","datavalue":{"value":"finite bipartite graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2121753$8A92CBC7-FADC-4283-8A34-EEAA0DBAF7E6","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":"Q2121753$55FB165A-A0B6-4A8D-872B-4986F3BC62C4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7093b0bd2c6dd8147954fe055c48b8c0a3b2cfab","datavalue":{"value":"W4213418234","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121753$DD6FB672-CD50-4CB7-8AF6-0B91B1D977F3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2438a022aa674b1c2ea482009e984b52b3947f7","datavalue":{"value":{"entity-type":"item","numeric-id":345136,"id":"Q345136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121753$D0B78D69-0611-4442-A97D-19088E59852D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c919e824f557133d0a9e23815c40d3ca8dfdcaf","datavalue":{"value":{"entity-type":"item","numeric-id":5721213,"id":"Q5721213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121753$6F1B802F-1BB5-42FF-A19E-E12ECC78109D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09a1d60b8390f110d2a46a491b1ba11ee48deb21","datavalue":{"value":{"entity-type":"item","numeric-id":5548831,"id":"Q5548831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121753$9E326E7F-CA07-49D3-9BC2-426820CA3BC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26cf9da64decc279eb27fe1f7d3495a7a0ae4e44","datavalue":{"value":{"entity-type":"item","numeric-id":5596772,"id":"Q5596772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121753$32284F6F-CE29-4028-A7EF-0BF03BDC59FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6a222de0bfae53ecde1a749b0e21e4687de2218","datavalue":{"value":{"entity-type":"item","numeric-id":3966165,"id":"Q3966165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121753$C12090E0-162A-461E-AC02-E0592BA29A91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8406bc96e7af3eadbb7276b92b44254fa600dbba","datavalue":{"value":{"entity-type":"item","numeric-id":2550401,"id":"Q2550401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121753$0F872BB6-DFF2-408D-BE59-0696B7EBA3D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28588578bb09af0b4bf0a3281ab6c8d321eb619b","datavalue":{"value":{"entity-type":"item","numeric-id":4519896,"id":"Q4519896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121753$245DF4C8-810C-4407-835B-888CF296E72A","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"c95dd667f6d05a9c217b8add5b4781259ab54ba6","datavalue":{"value":"bafkreiajooctaeai25yhwqauop7hswduv4xus2eiqz3ytlzeccgpt5ebde","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2121753$9D707111-E007-4F24-ABD1-844E381D9A0E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"346b349e1f65391eaf0e57de4d1337958ce1f458","datavalue":{"value":{"entity-type":"item","numeric-id":1100485,"id":"Q1100485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"079988e32ec5e80e9f664676192525d19669c8a1","datavalue":{"value":{"amount":"+0.8224030137062073","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":"Q2121753$8ED76646-EB9D-4E58-9FAA-80C53B838DBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1bbca9b6461d4cbc3755686ea35ebde63b5fdc1a","datavalue":{"value":{"entity-type":"item","numeric-id":5420363,"id":"Q5420363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f67862789696ca973d016c8ef4f29edd772ad94","datavalue":{"value":{"amount":"+0.8002232313156128","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":"Q2121753$34155C8A-2A1F-46FB-9FFD-8965067C617F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ded385f662012b020ee31c2541ed174b2ddf4273","datavalue":{"value":{"entity-type":"item","numeric-id":5434251,"id":"Q5434251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f0e7957b244157fbc266d24c321c9c42ac1e82f","datavalue":{"value":{"amount":"+0.7707390189170837","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":"Q2121753$8071118C-34BF-4799-B532-BBC56DF8A695","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23de44a8386da6dbcb9741e2d3995b6769462fbc","datavalue":{"value":{"entity-type":"item","numeric-id":5028354,"id":"Q5028354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6c54d7b4ac3ff89f1ae14823634b56e5972ac23","datavalue":{"value":{"amount":"+0.7670525908470154","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":"Q2121753$98555E9B-6B75-4293-AC41-5F758CF75827","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b735ad60e4b36194e1f8e75e048038d2c9a1346","datavalue":{"value":{"entity-type":"item","numeric-id":325669,"id":"Q325669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8252f0da57a264d4fe9f0bce63cfeff367ab10b","datavalue":{"value":{"amount":"+0.7461872696876526","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":"Q2121753$9B1795EE-A591-405D-BC7D-68F520093AB0","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2121753$0F151DD5-6E30-4760-966C-1DE5D6E94AB5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Independent sets in subgraphs of a shift graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Independent_sets_in_subgraphs_of_a_shift_graph"}}}}}