Zobrazeno 1 - 10
of 174
pro vyhledávání: '"Letzter, Shoham"'
We consider the problem of constructing a graph of minimum degree $k\ge 1$ in the following controlled random graph process, introduced recently by Frieze, Krivelevich and Michaeli. Suppose the edges of the complete graph on $n$ vertices are permuted
Externí odkaz:
http://arxiv.org/abs/2401.15812
Autor:
Letzter, Shoham
In this survey we aim to give a comprehensive overview of results using sublinear expanders. The term sublinear expanders refers to a variety of definitions of expanders, which typically are defined to be graphs $G$ such that every not-too-small and
Externí odkaz:
http://arxiv.org/abs/2401.10865
Autor:
Letzter, Shoham, Sgueglia, Amedeo
Let $f^{(r)}(n;s,k)$ be the maximum number of edges in an $n$-vertex $r$-uniform hypergraph not containing a subhypergraph with $k$ edges on at most $s$ vertices. Recently, Delcourt and Postle, building on work of Glock, Joos, Kim, K\"{u}hn, Lichev a
Externí odkaz:
http://arxiv.org/abs/2312.03856
For a given $\delta \in (0,1)$, the randomly perturbed graph model is defined as the union of any $n$-vertex graph $G_0$ with minimum degree $\delta n$ and the binomial random graph $\mathbf{G}(n,p)$ on the same vertex set. Moreover, we say that a gr
Externí odkaz:
http://arxiv.org/abs/2310.18284
A typical theme for many well-known decomposition problems is to show that some obvious necessary conditions for decomposing a graph $G$ into copies $H_1, \ldots, H_m$ are also sufficient. One such problem was posed in 1987, by Alavi, Boals, Chartran
Externí odkaz:
http://arxiv.org/abs/2308.11613
Autor:
Letzter, Shoham
A well-known result due to Chvat\'al and Erd\H{o}s (1972) asserts that, if a graph $G$ satisfies $\kappa(G) \ge \alpha(G)$, where $\kappa(G)$ is the vertex-connectivity of $G$, then $G$ has a Hamilton cycle. We prove a similar result implying that a
Externí odkaz:
http://arxiv.org/abs/2306.12579
Autor:
Letzter, Shoham, Morrison, Natasha
For a finite abelian group $A$, define $f(A)$ to be the minimum integer such that for every complete digraph $\Gamma$ on $f$ vertices and every map $w:E(\Gamma) \rightarrow A$, there exists a directed cycle $C$ in $\Gamma$ such that $\sum_{e \in E(C)
Externí odkaz:
http://arxiv.org/abs/2306.09033
Publikováno v:
Combinator. Probab. Comp. 33 (2024) 624-642
We investigate the existence of a rainbow Hamilton cycle in a uniformly edge-coloured randomly perturbed digraph. We show that for every $\delta \in (0,1)$ there exists $C = C(\delta) > 0$ such that the following holds. Let $D_0$ be an $n$-vertex dig
Externí odkaz:
http://arxiv.org/abs/2304.09155
Given a graph $H$, we say that an edge-coloured graph $G$ is $H$-rainbow saturated if it does not contain a rainbow copy of $H$, but the addition of any non-edge in any colour creates a rainbow copy of $H$. The rainbow saturation number $\text{rsat}(
Externí odkaz:
http://arxiv.org/abs/2211.08589
Autor:
Letzter, Shoham
A separating path system for a graph $G$ is a collection $\mathcal{P}$ of paths in $G$ such that for every two edges $e$ and $f$ in $G$, there is a path in $\mathcal{P}$ that contains $e$ but not $f$. We show that every $n$-vertex graph has a separat
Externí odkaz:
http://arxiv.org/abs/2211.07732