{"entities":{"Q1377695":{"pageid":1388435,"ns":120,"title":"Item:Q1377695","lastrevid":68761068,"modified":"2026-04-13T01:53:01Z","type":"item","id":"Q1377695","labels":{"en":{"language":"en","value":"Independent transversals in \\(r\\)-partite graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1109972"}},"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":"Q1377695$C72B2E02-5088-436E-845B-1EEB2C17E77F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e379184860057ec15275c6833e91337a1ae3699e","datavalue":{"value":{"text":"Independent transversals in \\(r\\)-partite graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1377695$403F6535-616C-4DB4-95EA-80CE07918C01","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4861b484937443f3be2f8128de44f024a5726010","datavalue":{"value":"0891.05041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1377695$A4B366FB-B1B3-44C5-95BD-1CBF4DB6B492","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3a4bb0d06a8ba5ac10a1912c093b06cc7cca01c5","datavalue":{"value":"10.1016/S0012-365X(96)00300-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1377695$0CF85990-6987-4440-BB39-1DC02BC44E67","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"58695e9da83c43913be67e6d6be310d1075b58c8","datavalue":{"value":{"entity-type":"item","numeric-id":222643,"id":"Q222643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1377695$EFEE59C2-4527-4CDE-8293-9E02A9ACC7D6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1377695$2B310E80-B1C8-4A53-BC42-522345621DF9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"11f7738b90032b640ef86af9767c7f4f407bb95e","datavalue":{"value":{"time":"+1998-07-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1377695$EF29EC78-83EB-4722-B93F-12724BF3DE28","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a476db75f650cf7cee616e401301fdf7cce04779","datavalue":{"value":"\\({\\mathcal G}(r,n)\\) denotes the set of all \\(r\\)-partite graphs having precisely \\(n\\) vertices in each of the \\(r\\) classes. An independent transversal is an independent set consisting of exactly one vertex from each of the \\(r\\) classes. If \\(\\Delta(r,n)\\) denotes the maximum integer \\(m\\) such that every \\(G\\in{\\mathcal G}(r,n)\\) with maximum degree less than \\(m\\) contains an independent transversal, then \\(C_r\\) is defined to be \\(\\lim\\limits_{n\\to\\infty}\\frac{\\Delta(r,n)}n\\). Theorem 1.1. (1) \\(\\Delta(4,n)\\geq\\frac{2n}3\\). (2) For all \\(r\\geq3\\), \\(\\Delta(2r,n)\\geq\\frac{\\Delta(r,n)}2\\). (3) For all \\(r\\geq3\\), \\(C_r\\geq\\max\\{\\frac{1}{2^{\\log\\left\\lceil r/3 \\right\\rceil}},\\frac 1{3\\cdot 2^{\\left\\lceil\\log r\\right\\rceil}-3}\\}\\). Theorem 1.2. For every \\(r\\geq2\\), \\(\\Delta(r,n)\\leq n\\cdot\\frac{2^{\\lfloor\\log r\\rfloor-1}}{2^{\\lfloor \\log r \\rfloor}-1}\\) holds for infinitely many values of \\(n\\). Consequently \\(C_r\\leq\\frac{2^{\\lfloor\\log r\\rfloor-1}}{2^{\\lfloor \\log r \\rfloor}-1}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1377695$ABBBB114-7218-4DE9-A866-C674252A5A41","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1377695$285C09EB-D928-45C6-B6C9-971799CB2A18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1377695$170B82E3-9901-4936-8035-C76286B806B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1ad1bf428b79a0176d62afa9a160b2a17f8d9ea9","datavalue":{"value":"05D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1377695$87D26F83-5E34-496A-988B-726788EA7C34","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f6f2e6f044d8c374684e5e29d2d1e700347c79e1","datavalue":{"value":"1109972","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1377695$45E5135C-6555-4B01-B367-ADDE0772C376","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ed3b666edffc90b9843b110c1957d9d66b9dc91","datavalue":{"value":"\\(r\\)-partite graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1377695$0057B3CA-B1CA-4E3E-A67A-A992DC0EF746","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01c7659f330f20b48e5a054d487f71f4678d2542","datavalue":{"value":"independent transversal","type":"string"},"datatype":"string"},"type":"statement","id":"Q1377695$51EB83BC-DADF-4CBA-9C08-93D9AB5671DB","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":"Q1377695$3CEAD31C-4091-44F1-8266-3491122501E4","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":"Q1377695$C7861148-FC7A-483B-98D0-3C10FAB609BD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"889a3c4a8729b73ec6703ac1260a2435fba83043","datavalue":{"value":{"entity-type":"item","numeric-id":3989737,"id":"Q3989737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1377695$CD11A91B-270C-46D1-BFF5-05A11987BA28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eea8108228a3fb03cd6914491ae57fb9168aef1f","datavalue":{"value":{"entity-type":"item","numeric-id":3986105,"id":"Q3986105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1377695$0040E583-C4CC-4730-9036-91596179F421","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5899e3e12a743d53573a910fcbfa636f0f6c8e3","datavalue":{"value":{"entity-type":"item","numeric-id":3852212,"id":"Q3852212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1377695$E8C23947-4449-4B70-AA39-06FEA439E16B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"060f551a54b40a4666d5dddb90c1a9a7f469e908","datavalue":{"value":{"entity-type":"item","numeric-id":4100117,"id":"Q4100117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1377695$2AF9459F-63E2-4F7E-87D1-CBC37135BD0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"835719973f233409024ef3cbbd019c8eb10bd440","datavalue":{"value":{"entity-type":"item","numeric-id":1217812,"id":"Q1217812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1377695$584376BC-352A-4271-8D70-ABDF821C7956","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c830fdb6cc2165a692a7944cb5c717669eedfbc","datavalue":{"value":{"entity-type":"item","numeric-id":766882,"id":"Q766882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1377695$CD9C6D03-4D9F-4CB7-BD21-2A5C9BDE33C4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7237e239bd80efe1cd3da2f53e9824ab7dfebf5a","datavalue":{"value":{"entity-type":"item","numeric-id":4314148,"id":"Q4314148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be4545e04a3b28b9707519689ab3a37f48332afc","datavalue":{"value":{"amount":"+0.94217837","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1377695$A9E06BF8-66A9-421D-ACBD-0E4BC203D7DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f7c2a9896f3348576231113a2ede70da5dfb83a","datavalue":{"value":{"entity-type":"item","numeric-id":3123116,"id":"Q3123116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4bc6aec1ec3e3e25a0d7fee89b879bc419618803","datavalue":{"value":{"amount":"+0.93296564","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1377695$D4331DDA-0756-4201-A84E-9E2A0FE12B09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"171a7017137c36806335c5f46b64cf8f27c2547d","datavalue":{"value":{"entity-type":"item","numeric-id":2665964,"id":"Q2665964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6abc81e524bed105fce960742299c7820f410f6c","datavalue":{"value":{"amount":"+0.927787","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1377695$13516140-6C27-4F5A-B9B4-719214709411","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"180462f7fa7f30aae2e1616d305062fc78ee383f","datavalue":{"value":{"entity-type":"item","numeric-id":2906362,"id":"Q2906362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b3f73fef6fd804c839af0f8a67eeba744268dad","datavalue":{"value":{"amount":"+0.9179272","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1377695$38A2E190-1143-4487-87EB-FB4EE5F51412","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"750196cf0deb81f5d4e212776f836847be9577e7","datavalue":{"value":{"entity-type":"item","numeric-id":1974346,"id":"Q1974346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"193855dc639d9f60fb98961cea771fc3b179d0ec","datavalue":{"value":{"amount":"+0.9163336","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1377695$0BB7D8BA-20B4-46BB-87B4-B165D54A01EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a485b5c451223687d7613a42b14e72e3e26b58f1","datavalue":{"value":{"entity-type":"item","numeric-id":505424,"id":"Q505424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4dba82b2330a7b49bf352bc8ca32feb9d2af304b","datavalue":{"value":{"amount":"+0.9078291","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1377695$10487145-6CEE-4E62-ABB8-DCA920E09B9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29c4f23201ed297ac8032a21baa5a5deff62193b","datavalue":{"value":{"entity-type":"item","numeric-id":5133085,"id":"Q5133085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bfcf1771671d0484538a0f1dd3461cdfcd4424de","datavalue":{"value":{"amount":"+0.9046235","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1377695$FFEE2167-3069-407A-845D-B340D1967AEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb10c850b60f693d56ad614342914e1083db1b9e","datavalue":{"value":{"entity-type":"item","numeric-id":5888915,"id":"Q5888915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64d1f62506b48a2acdfc36299de52b06fb84ef0e","datavalue":{"value":{"amount":"+0.90218794","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1377695$ADC8D995-DEDE-4DDB-BE8F-AEF04A1B8FD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"482926090b2156d64f2d52cd762809c70844443e","datavalue":{"value":{"entity-type":"item","numeric-id":2384801,"id":"Q2384801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30550af315fc8c24dee017bfa29904ddcf032821","datavalue":{"value":{"amount":"+0.90052855","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1377695$2F78AFFD-E612-4FD0-A4DD-DB8BDBB6D64D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6874b49bae3c2b1190f7bbef61cd37ebef78f56b","datavalue":{"value":{"entity-type":"item","numeric-id":4712708,"id":"Q4712708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d69706853d20cbd641287b6afb163a8010eb3f9","datavalue":{"value":{"amount":"+0.8987552","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1377695$5D5B48B0-0CCF-4743-9DA2-845DC218F5D6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Independent transversals in \\(r\\)-partite graphs","badges":[]}}}}}