Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCollapsibility of simplicial complexes of hypergraphs
196
0
0.0
(
0
)
Authors
Alan Lew
Ask ChatGPT about the research
No Arabic abstract
Let $mathcal{H}$ be a hypergraph of rank $r$. We show that the simplicial complex whose simplices are the hypergraphs $mathcal{F}subsetmathcal{H}$ with covering number at most $p$ is $left(binom{r+p}{r}-1right)$-collapsible, and the simplicial complex whose simplices are the pairwise intersecting hypergraphs $mathcal{F}subsetmathcal{H}$ is $frac{1}{2}binom{2r}{r}$-collapsible.
rate research
Read More
The family of contractible graphs, introduced by A. Ivashchenko, consists of the collection $mathfrak{I}$ of graphs constructed recursively from $K_1$ by contractible transformations. In this paper we show that every graph in a subfamily of $mathfrak{I}$ (the strongly contractible ones) is a collapsible graph (in the simplicial sense), by providing a sequence of elementary collapses induced by removing contractible vertices or edges. In addition, we introduce an algorithm to identify the contractible vertices in any graph and show that there is a natural homomorphism, induced by the inclusion map of graphs, between the homology groups of the clique complex of graphs with the contractible vertices removed. Finally, we show an application of this result to the computation of the persistent homology for the Vietoris-Rips filtration.
We consider a Hopf algebra of simplicial complexes and provide a cancellation-free formula for its antipode. We then obtain a family of combinatorial Hopf algebras by defining a family of characters on this Hopf algebra. The characters of these combinatorial Hopf algebras give rise to symmetric functions that encode information about colorings of simplicial complexes and their $f$-vectors. We also use characters to give a generalization of Stanleys $(-1)$-color theorem. A $q$-analog version of this family of characters is also studied.
Let $X$ be a simplicial complex on vertex set $V$. We say that $X$ is $d$-representable if it is isomorphic to the nerve of a family of convex sets in $mathbb{R}^d$. We define the $d$-boxicity of $X$ as the minimal $k$ such that $X$ can be written as the intersection of $k$ $d$-representable simplicial complexes. This generalizes the notion of boxicity of a graph, defined by Roberts. A missing face of $X$ is a set $tausubset V$ such that $tau otin X$ but $sigmain X$ for any $sigmasubsetneq tau$. We prove that the $d$-boxicity of a simplicial complex on $n$ vertices without missing faces of dimension larger than $d$ is at most $leftlfloorfrac{1}{d+1}binom{n}{d}rightrfloor$. The bound is sharp: the $d$-boxicity of a simplicial complex whose set of missing faces form a Steiner $(d,d+1,n)$-system is exactly $frac{1}{d+1}binom{n}{d}$.
We provide a random simplicial complex by applying standard constructions to a Poisson point process in Euclidean space. It is gigantic in the sense that - up to homotopy equivalence - it almost surely contains infinitely many copies of every compact topological manifold, both in isolation and in percolation.
Our first main result is a uniform bound, in every dimension $k in mathbb N$, on the topological Turan numbers of $k$-dimensional simplicial complexes: for each $k in mathbb N$, there is a $lambda_k ge k^{-2k^2}$ such that for any $k$-complex $mathcal{S}$, every $k$-complex on $n ge n_0(mathcal{S})$ vertices with at least $n^{k+1 - lambda_k}$ facets contains a homeomorphic copy of $mathcal{S}$. This was previously known only in dimensions one and two, both by highly dimension-specific arguments: the existence of $lambda_1$ is a result of Mader from 1967, and the existence of $lambda_2$ was suggested by Linial in 2006 and recently proved by Keevash-Long-Narayanan-Scott. We deduce this geometric fact from a purely combinatorial result about trace-bounded hypergraphs, where an $r$-partite $r$-graph $H$ with partite classes $V_1, V_2, dots, V_r$ is said to be $d$-trace-bounded if for each $2 le i le r$, all the vertices of $V_i$ have degree at most $d$ in the trace of $H$ on $V_1 cup V_2 cup dots cup V_i$. Our second main result is the following estimate for the Turan numbers of degenerate trace-bounded hypergraphs: for all $r ge 2$ and $dinmathbb N$, there is an $alpha_{r,d} ge (5rd)^{1-r}$ such that for any $d$-trace-bounded $r$-partite $r$-graph $H$, every $r$-graph on $n ge n_0(H)$ vertices with at least $n^{r - alpha_{r,d}}$ edges contains a copy of $H$. This strengthens a result of Conlon-Fox-Sudakov from 2009 who showed that such a bound holds for $r$-partite $r$-graphs $H$ satisfying the stronger hypothesis that the vertex-degrees in all but one of its partite classes are bounded (in $H$, as opposed to in its traces).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
