1. Bounding the Number of Minimal Transversals in Tripartite 3-Uniform Hypergraphs
- Author
-
Bazin, Alexandre, Beaudou, Laurent, Kahn, Giacomo, Khoshkhah, Kaveh, WEB Architecture x Semantic WEB x WEB of Data (WEB3), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Décision et Information pour les Systèmes de Production (DISP), Université Lumière - Lyon 2 (UL2)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA), Institute of Computer Science [University of Tartu, Estonie], University of Tartu, Le2i - CheckSem, School of Computer Science and Informatics [Dublin], University College Dublin [Dublin] (UCD)-University College Dublin [Dublin] (UCD)-Laboratoire Electronique, Informatique et Image [UMR6306] (Le2i), Université de Bourgogne (UB)-École Nationale Supérieure d'Arts et Métiers (ENSAM), Arts et Métiers Sciences et Technologies, HESAM Université (HESAM)-HESAM Université (HESAM)-Arts et Métiers Sciences et Technologies, HESAM Université (HESAM)-HESAM Université (HESAM)-AgroSup Dijon - Institut National Supérieur des Sciences Agronomiques, de l'Alimentation et de l'Environnement-Centre National de la Recherche Scientifique (CNRS)-Université de Bourgogne (UB)-École Nationale Supérieure d'Arts et Métiers (ENSAM), HESAM Université (HESAM)-HESAM Université (HESAM)-AgroSup Dijon - Institut National Supérieur des Sciences Agronomiques, de l'Alimentation et de l'Environnement-Centre National de la Recherche Scientifique (CNRS), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne (UCA)-Centre National de la Recherche Scientifique (CNRS), Institute of Computer Science (University of Tartu) (CS), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), National Research University Higher School of Economics, Faculty of Computer Science (HSE-CS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université Lumière - Lyon 2 (UL2), Université de Bourgogne (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Arts et Métiers (ENSAM), HESAM Université (HESAM)-HESAM Université (HESAM)-AgroSup Dijon - Institut National Supérieur des Sciences Agronomiques, de l'Alimentation et de l'Environnement-Université de Bourgogne (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Arts et Métiers (ENSAM), HESAM Université (HESAM)-HESAM Université (HESAM)-AgroSup Dijon - Institut National Supérieur des Sciences Agronomiques, de l'Alimentation et de l'Environnement, Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), and EUROSTAR PSDP project.'Fonds Européen de Développement Régional (FEDER)' program though project AAP ressourcement S3 – DIS 4 (2015-2018).Estonian Research Council, ETAG (Eesti Teadusagentuur), through PUT Exploratory Grant #620.
- Subjects
FOS: Computer and information sciences ,Mathematics::Combinatorics ,k)-Hypergraphs ,Discrete Mathematics (cs.DM) ,General Computer Science ,Formal Concept Analysis ,Hypergraph Transversals ,3)-Hypergraphs ,Polyadic Concept Analysis ,(k ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,Hypergraphs ,Triadic Concept Analysis ,Theoretical Computer Science ,Measure and conquer ,(3 ,Minimal transversal ,Computer Science::Discrete Mathematics ,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] ,FOS: Mathematics ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Combinatorics (math.CO) ,Computer Science - Discrete Mathematics - Abstract
We focus on the maximum number of minimal transversals in 3-partite 3-uniform hypergraphs on n vertices. Those hypergraphs (and their minimal transversals) are commonly found in database applications. In this paper we prove that this number grows at least like 1.4977^n and at most like 1.5012^n.
- Published
- 2023