|
|||||
[PDF]
- JAMES ROSS, University of New South Wales
Sampling hypergraphs with given degrees [PDF]
-
There are a variety of well-studied methods to approximately uniformly sample simple graphs with prescribed degree sequences, as well as for variations like bipartite graphs. In this talk, we will define and analyse an algorithm for sampling simple, uniform hypergraphs with a given degree sequence. This combines any black box function for sampling bipartite graphs, a standard correspondence from biadjacency matrices of bipartite graphs to the incidence matrices of hypergraphs, and rejection sampling, which guarantees that results are simple hypergraphs. We will show that sparse degree sequences, with length $n$ and maximum degree $d_{\max}$ satisfying $d_{\max}^2 = o(n^{r-2})$ among other conditions, result in a polynomial expected running time, a small approximation error from the uniform distribution, and a small chance of failure when running the algorithm. This was a joint work with Martin Dyer, Catherine Greenhill, Pieter Kleer, and Leen Stougie.
- SAM SPIRO, UC San Diego
Cycle-free Subgraphs of Random Hypergraphs [PDF]
-
Let $H_{n,p}^r$ denote the random $r$-uniform $n$-vertex hypergraph obtained by including each edge independently and with probability $p$. If $\mathcal{F}$ is a family of $r$-uniform hypergraphs, we let $ex(H_{n,p}^r,\mathcal{F})$ denote the size of a largest $\mathcal{F}$-free subgraph of $H_{n,p}^r$. In this talk we study this function when $\mathcal{F}$ is a family of hypergraph cycles, with a particular emphasis on the case when $\mathcal{F}$ is the set of all Berge cycles of length at most $\ell$.
- MICHAL STERN, Academic College of Tel-Aviv Yaffo
Minimum removal or insertion list for Clustered Spanning Tree by Paths [PDF]
-
Let $H = \langle V, \mathcal{S} \rangle $ be a hypergraph, where $V$ is a set of vertices and $\mathcal{S}$ is a set of not necessarily disjoint clusters. The Clustered Spanning Tree by Paths problem aims to decide whether there exists a feasible solution tree, spanning all vertices of $V$, such that each cluster induces a path.
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.
- CHRISTIAN WINTER, Karlsruhe Institute of Technology, Karlsruhe, Germany
Size-Ramsey Number of Tight Paths [PDF]
-
The size-Ramsey number $\hat{R}^{(k)}(\mathcal{H})$ of a $k$-uniform hypergraph $\mathcal{H}$ is the minimum number of edges such that there is a $k$-uniform hypergraph $\mathcal{G}$ on this many edges with the property that each edge $2$-coloring of $\mathcal{G}$ contains a monochromatic copy of $\mathcal{G}$.
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)$.