| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

2. Graph Theory Motivated Questions

    1. Thin Tree Conjecture

          If you have a graph $G$, and it is $k$-edge connected for some large $k$. That is, for every partition of the vertices into 2 parts $A \subseteq V(G)$ and $A^c$ there exists at least $k$ edges going from $A$ to $A^c$. A spanning tree is $\alpha$-thin with respect to $G$ if for every cut $A \cup A^c$, the number of edges in $T$ going from $A$ to $A^c$ is at most $\alpha E(A,A^c)$, where $E(A,A^c)$ is the number of edges from $A$ to $A^c$ in $G$.

      Add remark

      Conjecture 2.1.

      There is a $k_0$ (independent of $|V|$) so that every $k_0$-edge connected graph has a $\frac{1}{2}$-thin spanning tree.

        • Negative correlation for random forests


          Add remark

          Problem 2.2.

          For what $\epsilon$ is it true that $\Pr(e \in F \text{ and }f \in F) \le (1+\epsilon)\Pr(e \in F)\Pr(f \in F)$ for $F$ a uniformly random spanning forest?


            • Add remark

              Problem 2.3.

              Let $G = (V,E)$ be a graph of maximum degree $\Delta$. Let $\chi(t)$ be the chromatic polynomial (i.e. $\chi(q)$ is the number of ways of properly coloring the graph $G$ with $q$ colors). Then, is $\chi(t) \neq 0$ for any $t \in \C$ so that $|t| > 2\Delta$. Also if the real part of $\text{Re }t > \Delta + 1$, then do we have $\chi(t) \neq 0$?

                  Cite this as: AimPL: The geometry of polynomials in combinatorics and sampling, available at http://aimpl.org/geompolysampling.