Zobrazeno 1 - 10
of 275
pro vyhledávání: '"Stein, Maya"'
We prove that for every ${\gamma > 0}$ there exists $n_0 \in \mathbb{N}$ such that for every ${n \geq n_0}$ any family of up to $\lfloor{n^{\frac12+\gamma}}\rfloor$ trees having at most $(1-\gamma)n$ vertices in each bipartition class can be packed i
Externí odkaz:
http://arxiv.org/abs/2410.13290
K\H onig's theorem says that the vertex cover number of every bipartite graph is at most its matching number (in fact they are equal since, trivially, the matching number is at most the vertex cover number). An equivalent formulation of K\H onig's th
Externí odkaz:
http://arxiv.org/abs/2409.18250
Autor:
Reed, Bruce, Stein, Maya
The Erd\H{o}s-S\'os Conjecture states that every graph with average degree exceeding $k-1$ contains every tree with $k$ edges as a subgraph. We prove that there are $\delta>0$ and $k_0\in\mathbb N$ such that the conjecture holds for every tree $T$ wi
Externí odkaz:
http://arxiv.org/abs/2405.15733
Autor:
Stein, Maya, Trujillo-Negrete, Ana
We show that if $D$ is an $n$-vertex digraph with more than $(k-1)n$ arcs that does not contain any of three forbidden digraphs, then $D$ contains every antidirected tree on $k$ arcs. The forbidden digraphs are those orientations of $K_{2, \lceil k/1
Externí odkaz:
http://arxiv.org/abs/2404.10750
We study two variations of the Gyarfas--Lehel conjecture on the minimum number of monochromatic components needed to cover an edge-coloured complete bipartite graph. Specifically, we show the following. - For p>> (\log n/n)^{1/2}, w.h.p.~every 2-colo
Externí odkaz:
http://arxiv.org/abs/2403.12587
Autor:
Kontogeorgiou, George, Stein, Maya
We show that for each natural number $n$ the clique $K_n$ has a weakly separating path system of size $n+2$, improving the previous best known upper bound of $(1+o(1))n$. Since $n-1$ is a lower bound, this is almost tight.
Comment: 7 pages
Comment: 7 pages
Externí odkaz:
http://arxiv.org/abs/2403.08210
Autor:
Dubó, Freddy Flores, Stein, Maya
The double star $S(m_1,m_2)$ is obtained from joining the centres of a star with $m_1$ leaves and a star with $m_2$ leaves. We give a short proof of a new upper bound on the two-colour Ramsey number of $S(m_1,m_2)$, for positive $m_1,m_2$ fulfilling
Externí odkaz:
http://arxiv.org/abs/2401.01274
Autor:
Stein, Maya
Which conditions ensure that a digraph contains all oriented paths of some given length, or even a all oriented trees of some given size, as a subgraph? One possible condition could be that the host digraph is a tournament of a certain order. In arbi
Externí odkaz:
http://arxiv.org/abs/2310.18719
Autor:
Klimošová, Tereza, Stein, Maya
We show that for any natural number $k \ge 1$, any oriented graph $D$ of minimum semidegree at least $(3k- 2)/4$ contains an antidirected path of length $k$. In fact, a slightly weaker condition on the semidegree sequence of $D$ suffices, and as a co
Externí odkaz:
http://arxiv.org/abs/2212.09876
Autor:
Stein, Maya, Zárate-Guerén, Camila
We show that for every $\eta>0$ every sufficiently large $n$-vertex oriented graph D of minimum semidegree exceeding $(1 + \eta) k/2$ contains every balanced antidirected tree with $k$ edges and bounded maximum degree, if $k \ge \eta n$. In particula
Externí odkaz:
http://arxiv.org/abs/2212.00769