Publication

Linearity of saturation for Berge hypergraphs

Abhishek Methuku
2019
Journal Articles

Abstract

For a graph F, we say a hypergraph H is a Berge-F if it can be obtained from F by replacing each edge of F with a hyperedge containing it. We say a hypergraph is Berge-F-saturated if it does not contain a Berge-F, but adding any hyperedge creates a copy of a Berge-F. The k-uniform saturation number of Berge-F, sat(k)(n, Berge-F) is the fewest number of hyperedges in a Berge-F-saturated k-uniform hypergraph on n vertices. We show that sat(k)(n, Berge-F) = O(n) for all graphs F and uniformities 3

Official source

https://infoscience.epfl.ch/entities/publication/f0f6b941-f4ef-420e-be4e-a301b4ebe8ba

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Linearity of saturation for Berge hypergraphs

Chat with Graph Search

Molecular hypergraph neural networks

Hypergraph-Based Fast Distributed AC Power Flow Optimization

Explicit representations for Banach subspaces of Lizorkin distributions