|
We introduce minimum cardinality removal or insertion list, which removes or inserts vertices from or into clusters, to gain feasibility. In addition, we decompose the intersection graph of $H$ into smaller instances, for those cases where the intersection graph contains a cut node or a separating edge. We demonstrate how to compose a minimum cardinality feasible removal or insertion list for the given hypergraph from the smaller instances. This approach may reduce the size and intricacy of the instances.
Joint work with Nili Beck.
For $k\ge2$ and $n\in\mathbb{N}$, a $k$-uniform tight path on $n$ vertices $\mathcal{P}^{(k)}_{n,k-1}$ is defined as a $k$-uniform hypergraph on $n$ vertices for which there is an ordering of its vertices such that the edge set is precisely the set consisting of all $k$-element intervals of consecutive vertices in this ordering.
It is a subject of current research to find an upper bound on the size-Ramsey number of $k$-uniform tight paths that is linear in terms of $n$.
In this talk we show a lower bound on this number, that is $\hat{R}^{(k)}(\mathcal{P}^{(k)}_{n,k-1})= \Omega\big(\log (k)n\big)$.