We disprove the conjecture that every tree with t leaves embeds isometrically into $\ell_\infty^{\lceil \log_2 t\rceil}$. We construct a 32-leaf tree whose least isometric $\ell_\infty$-dimension is six rather than five, and prove that every tree with at most 31 leaves attains the conjectured bound; Brigham et al. had recorded equality through 21 leaves. Thus 32 is the first failure, and the example answers affirmatively a question of Fitzpatrick and Nowakowski from 2000. The same topology has dimension six under every assignment of positive edge lengths, and therefore also disproves the later sharp leaf-threshold conjecture for weighted metric trees.
Tutte's flow conjectures ask when a graph has a nowhere-zero flow with small integer values. We approach these questions through spanning-tree packing and an analytic minimization argument of Alon, Buci\'c, and Davies. For every integer $q\ge2$, we prove that $q$ edge-disjoint spanning trees suffice to realize every co...
Let $T$ be a tree. Stanley asked whether the chromatic symmetric function $X_T$ determines $T$ up to isomorphism. We approach this open problem by regarding $X_T$ as a polynomial in the power-sum symmetric functions $p_1, p_2, \dots$ and studying the invariant $\Phi_T = (\partial X_T/\partial p_1)|_{p_1 = 0}$. We prove...
We prove that the number of labelled embeddings of any $n$-vertex tree $T$ into an $n$-vertex graph $G$ of maximum degree $d$ satisfies $$ \mathrm{inj}(T,G) \leq (d/e)^n \exp(o_d(1) n). $$ The bound is sharp up to determining $o_d(1)$, even for paths, and the dependence of the error $\exp(o_d(1)n)$ on $d$ is necessary....
Csongor Beke, V. Boskovic, Nina Kamčev et al.· 0 citations
The celebrated conjecture of Lov\'asz from 1969 asks whether every connected vertex-transitive graph has a Hamiltonian path. Buci\'c, Christoph, Pokrovskiy and Steiner recently proved that every such graph on $n$ vertices contains a cycle of length $n^{2/3-o(1)}$. In this paper, we improve this bound to $n^{1-o(1)}$. O...
The B\'ar\'any-Larman conjecture states that for any $d+1$ sets of $r$ points each in $\mathbb{R}^d$, considered as color classes, we can partition their union into $r$ rainbow $(d+1)$-tuples whose convex hulls intersect. We prove that the topological version of this conjecture holds when $r$ is a prime number. We also...
Let $a,b,c$ be the side lengths of a triangle, and let $R$ and $r$ denote its circumradius and inradius, respectively. Liu proposed the conjecture \[ \sum_{\text{cyc}} \left(\frac{a(b+c-a)}{bc}\right)^k \ge 2+\left(\frac{2r}{R}\right)^k,\qquad k>1, \] with the reverse inequality for $k<1$. We prove this conjecture by r...
Tserendorj Batbold· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
