Zobrazeno 1 - 10
of 57
pro vyhledávání: '"Ehard, Stefan"'
Autor:
Ehard, Stefan, Joos, Felix
We prove that any quasirandom uniform hypergraph $H$ can be approximately decomposed into any collection of bounded degree hypergraphs with almost as many edges. In fact, our results also apply to multipartite hypergraphs and even to the sparse setti
Externí odkaz:
http://arxiv.org/abs/2011.05359
Answering a question posed by Caro, Hansberg, Lauri, and Zarb, we show that for every positive integer $n$ and every function $\sigma\colon E(K_{4n})\to\{-1,1\}$ with $\sigma\left(E(K_{4n})\right)=0$, there is a perfect matching $M$ in $K_{4n}$ with
Externí odkaz:
http://arxiv.org/abs/2010.15418
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, vol. 24, no. 1, Graph Theory (May 13, 2022) dmtcs:6844
We consider a non-monotone activation process $(X_t)_{t\in\{ 0,1,2,\ldots\}}$ on a graph $G$, where $X_0\subseteq V(G)$, $X_t=\{ u\in V(G):|N_G(u)\cap X_{t-1}|\geq \tau(u)\}$ for every positive integer $t$, and $\tau:V(G)\to \mathbb{Z}$ is a threshol
Externí odkaz:
http://arxiv.org/abs/2007.03959
A bihole in a bipartite graph $G$ with partite sets $A$ and $B$ is an independent set $I$ in $G$ with $|I\cap A|=|I\cap B|$. We prove lower bounds on the largest order of biholes in balanced bipartite graphs subject to conditions involving the vertex
Externí odkaz:
http://arxiv.org/abs/2004.03245
Autor:
Ehard, Stefan, Joos, Felix
Kim, K\"uhn, Osthus and Tyomkyn (Trans. Amer. Math. Soc. 371 (2019), 4655--4742) greatly extended the well-known blow-up lemma of Koml\'os, S\'ark\"ozy and Szemer\'edi by proving a `blow-up lemma for approximate decompositions' which states that mult
Externí odkaz:
http://arxiv.org/abs/2001.03506
Publikováno v:
Combinator. Probab. Comp. 29 (2020) 868-885
A celebrated theorem of Pippenger states that any almost regular hypergraph with small codegrees has an almost perfect matching. We show that one can find such an almost perfect matching which is `pseudorandom', meaning that, for instance, the matchi
Externí odkaz:
http://arxiv.org/abs/1907.09946
A subgraph of an edge-coloured graph is called rainbow if all its edges have different colours. We prove a rainbow version of the blow-up lemma of Koml\'os, S\'ark\"ozy and Szemer\'edi that applies to almost optimally bounded colourings. A corollary
Externí odkaz:
http://arxiv.org/abs/1907.09950
Autor:
Ehard, Stefan, Mohr, Elena
For an edge-colored graph, a subgraph is called rainbow if all its edges have distinct colors. We show that if $G$ is an edge-colored graph of order $n$ and size $m$ using $c$ colors on its edges, and $m+c\geq \binom{n+1}{2}+k-1$ for a non-negative i
Externí odkaz:
http://arxiv.org/abs/1810.04980
Autor:
Ehard, Stefan, Rautenbach, Dieter
A widely studied model for influence diffusion in social networks are {\it target sets}. For a graph $G$ and an integer-valued threshold function $\tau$ on its vertex set, a {\it target set} or {\it dynamic monopoly} is a set of vertices of $G$ such
Externí odkaz:
http://arxiv.org/abs/1805.10086
For a graph $G$ and an integer-valued threshold function $\tau$ on its vertex set, a dynamic monopoly is a set of vertices of $G$ such that iteratively adding to it vertices $u$ of $G$ that have at least $\tau(u)$ neighbors in it eventually yields th
Externí odkaz:
http://arxiv.org/abs/1802.03935