Толық екібөлімді кішіграфтары жоқ графтар және Заранкевич проблемасы

Кіріспе

үлкен толық екі жақты кіші графтары жоқ графтар. Математикадағы шешілмеген Заранкевич проблемасы, белгілі бір түйіндер саны бар және белгілі бір өлшемдегі толық екі жақты кіші графтары жоқ екі жақты графтың ең көп мүмкін жиектерінің санын анықтауға қатысты. Ол комбинаториканың бір саласы – экстремалды граф теориясы саласына жатады және 1951 жылы проблеманың бірнеше ерекше жағдайларын ұсынған поляк математигі Казимеж Заранкевичтің құрметіне аталған.

Мәселе туралы мәлімдеме

Екі жақты граф екі бөлек төбелер жиынынан – және – және әрқайсысы жиектер жиынтығынан тұрады, олардың әрқайсысы жиектерінің бірінен жиектерінің біріне қосылады. Екі жиек бірдей төбелер жұбын байланыстыра алмайды. Толық екі жақты граф – бұл әрбір төбесінен және төбесінен тұратын жұптардың барлығы бір-бірімен байланысқан екі жақты граф. Егер екі жақты графта және төбелері бар және төбелері бар жиектер жиынтығы болса, онда осы төбелер формасының субграфына ие болады. (Бұл жағдайда, және ретінің маңызды екенін ескеру қажет: төбелер жиынынан және төбелер жиынынан болуы керек, керісінше емес.) Заранкевич функциясы екі жақты графтың ең көп мүмкін жиектерінің санын білдіреді, онда және , бірақ формасының субграфы жоқ. Маңызды ерекше жағдай үшін, Заранкевич мәселесі Заранкевич функциясының формуласын немесе (егер мұндай формула болмаса) тұрақты болған кезде өсу жылдамдығының тығыз асимптотикалық шектерін табуды сұрайды. Бұл мәселе алты периметрлі торларды анықтаумен бірдей. Заранкевич мәселесі, торлар және шекті геометрия тығыз байланысты. Бұл мәселені цифрлық геометрия тұрғысынан да қарастыруға болады. Екі жақты графтың мүмкін жиектерін бүтін сандар торындағы тіктөртбұрыштың нүктелері ретінде қарастыруға болады, ал толық субграф – бұл тіктөртбұрыштағы барлық нүктелер бар жолдар мен бағандар жиынтығы. Осылайша, жолдар мен бағандардың ешбір жиынтығы толық тіктөртбұрышты құрамайтындай етіп, желі ішінде орналастырылатын нүктелердің ең көп санын білдіреді. жағдайы салыстырмалы түрде қарапайым: 13 жиекті екі жақты графты, екі жақтың әр жағында төрт төбесі бар және субграфы жоқ, текше графигіне ұзын диагональдың біреуін қосу арқылы алуға болады. Керісінше, егер 14 жиекті екі жақты графтың әр жағында төрт төбесі болса, онда әр жағындағы екі төбесінің дәрежесі төрт болуы керек. Осы төрт төбесін және олардың 12 жанас жиегін алып тастағанда, бос емес жиектер жиынтығы қалады, олардың кез келгені алынып тасталған төрт төбемен бірге субграфты құрайды.

A bipartite graph consists of two disjoint sets of vertices and , and a set of edges each of which connects a vertex in to a vertex in No two edges can both connect the same pair of vertices. A complete bipartite graph is a bipartite graph in which every pair of a vertex from and a vertex from is connected to each other. A complete bipartite graph in which has vertices and has vertices is denoted If is a bipartite graph, and there exists a set of vertices of and vertices of that are all connected to each other, then these vertices induce a subgraph of the form (In this formulation, the ordering of and is significant: the set of vertices must be from and the set of vertices must be from , not vice versa.) The Zarankiewicz function denotes the maximum possible number of edges in a bipartite graph for which and , but which does not contain a subgraph of the form As a shorthand for an important special case, is the same as The Zarankiewicz problem asks for a formula for the Zarankiewicz function, or (failing that) for tight asymptotic bounds on the growth rate of assuming that is a fixed constant, in the limit as goes to infinity. For this problem is the same as determining cages with girth six. The Zarankiewicz problem, cages and finite geometry are strongly interrelated. The same problem can also be formulated in terms of digital geometry. The possible edges of a bipartite graph can be visualized as the points of a rectangle in the integer lattice, and a complete subgraph is a set of rows and columns in this rectangle in which all points are present. Thus, denotes the maximum number of points that can be placed within an grid in such a way that no subset of rows and columns forms a complete grid. The case of is relatively simple: a 13 edge bipartite graph with four vertices on each side of the bipartition, and no subgraph, may be obtained by adding one of the long diagonals to the graph of a cube. In the other direction, if a bipartite graph with 14 edges has four vertices on each side, then two vertices on each side must have degree four. Removing these four vertices and their 12 incident edges leaves a nonempty set of edges, any of which together with the four removed vertices forms a subgraph.

Шекті геометриядағы түсу графиктері

, үшін екі жақты график, әр жағында төбесі, жиегі және циклдары жоқ, проективтік жазықтықтың Леви графигі немесе нүкте-сызық инциденттік графигі ретінде алынуы мүмкін, яғни нүктелер мен сызықтардың жүйесі, онда кез келген екі нүкте бір ғана сызықты анықтайды, ал кез келген екі сызық бір ғана нүктеде қиылысады. Біз осы проективтік жазықтыққа қатысты екі жақты графикті құрастырамыз, оның бір төбелік бөлігі нүктелерден, екінші төбелік бөлігі сызықтардан тұрады, сонда нүкте мен сызық проективтік жазықтықта инцидент болған жағдайда ғана байланыстырылады. Бұл төбелері мен жиектері бар еркін графикке алып келеді. Бұл төменгі шек И. Рейман берген жоғарғы шекке сәйкес келетіндіктен, бізде асимптотикалық мәні бар.

, үшін екі жақты графтар, әр жағында төбелері, жиектері және циклдары жоқ, қайтадан шекті геометриядан құрастырылуы мүмкін, төбелер үш өлшемді шекті аффиндік кеңістіктегі нүктелер мен сфераларды (күтімді түрде таңдалған белгілі радиуста) көрсетеді, ал жиектер нүкте-сфера инциденттерін көрсетеді. Жалпы алғанда, қарастырайық және кез келген элементі шекті өріс болсын, ал элементі көбейту ретімен элемент болып табылады, яғни көбейту тобының элемент кіші тобын құрайды. Екі нөлден өзгеше элементтің эквивалентті екендігін айтамыз, егер бізде және кейбір үшін болса. Барлық эквиваленттілік сыныптары жиынтығындағы графикті қарастырайық, егер және тек қана егер болса. Бұл дұрыс анықталғанын және циклдары жоқ екенін, ал графиктің әрбір төбесі дәрежесіне немесе тең болғанын тексеруге болады. Сондықтан бізде жоғарғы шек бар.

Қолданбалар

Кёвари-Шош-Туран теоремасы дискретті геометрияда әртүрлі типтегі геометриялық нысандар арасындағы кездесулер санын шектеу үшін қолданылады. Мысалы, Евклид жазықтығындағы нүктелер мен түзулер жиынында міндетті түрде кездеспеушіліктер болмайды, сондықтан Кёвари-Шош-Туран теоремасына сәйкес нүкте-түзу кездесулерінің саны бар. Бұл шектеу , -нің -ден әлдеқайда үлкен болған жағдайда қатаң, бірақ және -нің шамалары шамалас болғанда емес, онда Сземереди-Троттер теоремасы қатаңрақ шектеу ұсынады. Дегенмен, Сземереди-Троттер теоремасы Кёвари-Шош-Туран теоремасының қатаң болатын кіші жиынтықтарға нүктелер мен түзулерді бөлу арқылы дәлелденуі мүмкін.