Weak Saturation of Multipartite Hypergraphs
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Weak Saturation of Multipartite Hypergraphs
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Combinatorica
ISSN
0209-9683
e-ISSN
1439-6912
Volume of the periodical
43
Issue of the periodical within the volume
6
Country of publishing house
DE - GERMANY
Number of pages
22
Pages from-to
1081-1102
UT code for WoS article
001038559000001
EID of the result in the Scopus database
2-s2.0-85165868854