Weak Saturation of Multipartite Hypergraphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10476100" target="_blank" >RIV/00216208:11320/23:10476100 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=yQO.eCYwUh" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=yQO.eCYwUh</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00493-023-00049-0" target="_blank" >10.1007/s00493-023-00049-0</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Weak Saturation of Multipartite Hypergraphs

Popis výsledku v původním jazyce

Given q-uniform hypergraphs (q-graphs) F, G and H, where G is a spanning subgraph of F, G is called weakly H -saturated in F if the edges in E(F) E(G) admit an ordering e(1), ... , e(k) so that for all i is an element of [k] the hypergraph G boolean OR {e(1), ... , e(i)} contains an isomorphic copy of H which in turn contains the edge ei. The weak saturation number of H in F is the smallest size of an H-weakly saturated subgraph of F. Weak saturation was introduced by Bollobas in 1968, but despite decades of study our understanding of it is still limited. The main difficulty lies in proving lower bounds on weak saturation numbers, which typically withstands combinatorial methods and requires arguments of algebraic or geometrical nature. In our main contribution in this paper we determine exactly the weak saturation number of complete multipartite q-graphs in the directed setting, for any choice of parameters. This generalizes a theorem of Alon from 1985. Our proof combines the exterior algebra approach from the works of Kalai with the use of the colorful exterior algebra motivated by the recent work of Bulavka, Goodarzi and Tancer on the colorful fractional Helly theorem. In our second contribution answering a question of Kronenberg, Martins and Morrison, we establish a link between weak saturation numbers of bipartite graphs in the clique versus in a complete bipartite host graph. In a similar fashion we asymptotically determine the weak saturation number of any complete q-partite q-graph in the clique, generalizing another result of Kronenberg et al.

Název v anglickém jazyce

Weak Saturation of Multipartite Hypergraphs

Popis výsledku anglicky

Given q-uniform hypergraphs (q-graphs) F, G and H, where G is a spanning subgraph of F, G is called weakly H -saturated in F if the edges in E(F) E(G) admit an ordering e(1), ... , e(k) so that for all i is an element of [k] the hypergraph G boolean OR {e(1), ... , e(i)} contains an isomorphic copy of H which in turn contains the edge ei. The weak saturation number of H in F is the smallest size of an H-weakly saturated subgraph of F. Weak saturation was introduced by Bollobas in 1968, but despite decades of study our understanding of it is still limited. The main difficulty lies in proving lower bounds on weak saturation numbers, which typically withstands combinatorial methods and requires arguments of algebraic or geometrical nature. In our main contribution in this paper we determine exactly the weak saturation number of complete multipartite q-graphs in the directed setting, for any choice of parameters. This generalizes a theorem of Alon from 1985. Our proof combines the exterior algebra approach from the works of Kalai with the use of the colorful exterior algebra motivated by the recent work of Bulavka, Goodarzi and Tancer on the colorful fractional Helly theorem. In our second contribution answering a question of Kronenberg, Martins and Morrison, we establish a link between weak saturation numbers of bipartite graphs in the clique versus in a complete bipartite host graph. In a similar fashion we asymptotically determine the weak saturation number of any complete q-partite q-graph in the clique, generalizing another result of Kronenberg et al.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Combinatorica

ISSN

0209-9683

e-ISSN

1439-6912

Svazek periodika

43

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

22

Strana od-do

1081-1102

Kód UT WoS článku

001038559000001

EID výsledku v databázi Scopus

2-s2.0-85165868854