Search

The Fibonacci cube $\Gamma_n$ is is the graph whose vertices are independent subsets of the path graph of length $n$, where two such vertices are considered adjacent if they differ by the addition or removal of a single element. Klav\v{z}ar [1] suggested considering the infinite Fibonacci cube $\Gamma_\infty$ whose vertices are independent subsets of the one-way infinite path graph with the same adjacency condition. We show that every connected component of $\Gamma_\infty$ is asymmetric (has no nontrivial automorphism) and no two connected components of $\Gamma_\infty$ are isomorphic. This follows from our results on a further generalization $\Gamma_G$ where $G$ is a simple, locally finite hypergraph with no isolated vertices., Comment: 5 pages

The distinguishing index $D'(G)$ of a graph $G$ is the least number of colors necessary to obtain an edge coloring of $G$ that is preserved only by the trivial automorphism. We show that if $G$ is a connected $\alpha$-regular graph for some infinite cardinal $\alpha$ then $D'(G) \le 2$, proving a conjecture of Lehner, Pil\'{s}niak, and Stawiski. We also show that if $G$ is a graph with infinite minimum degree and at most $2^\alpha$ vertices of degree $\alpha$ for every infinite cardinal $\alpha$, then $D'(G) \le 3$. In particular, $D'(G) \le 3$ if $G$ has infinite minimum degree and order at most $2^{\aleph_0}$.

Vop\v{e}nka's Principle says that the category of graphs has no large discrete full subcategory, or equivalently that the category of ordinals cannot be fully embedded into it. Weak Vop\v{e}nka's Principle is the dual statement, which says that the opposite category of ordinals cannot be fully embedded into the category of graphs. It was introduced in 1988 by Ad\'{a}mek, Rosick\'{y}, and Trnkov\'{a}, who showed that it follows from Vop\v{e}nka's Principle and asked whether the two statements are equivalent. We show that they are not. However, we show that Weak Vop\v{e}nka's Principle is equivalent to the generalization of itself known as Semi-Weak Vop\v{e}nka's Principle., Comment: 8 pages

We give a new proof of a theorem of Shelah which states that for every family of labeled trees, if the cardinality $\kappa$ of the family is much larger (in the sense of large cardinals) than the cardinality $\lambda$ of the set of labels, more precisely if the partition relation $\kappa \to (\omega)^{\mathord{<}\omega}_\lambda$ holds, then there is a homomorphism from one labeled tree in the family to another. Our proof uses a characterization of such homomorphisms in terms of games.

We show that Weak Vop\v{e}nka's Principle, which is the statement that the opposite category of ordinals cannot be fully embedded into the category of graphs, is equivalent to the large cardinal principle Ord is Woodin, which says that for every class C there is a C-strong cardinal. Weak Vop\v{e}nka's Principle was already known to imply the existence of a proper class of measurable cardinals. We improve this lower bound to the optimal one by defining structures whose nontrivial homomorphisms can be used as extenders, thereby producing elementary embeddings witnessing C-strongness of some cardinal.

W.H. Woodin showed that if $\kappa_1 < \cdots < \kappa_n$ are strong cardinals then two-step ${\bf\Sigma}^1_{n+3}$ generic absoluteness holds after collapsing $2^{2^{\kappa_n}}$ to be countable. We show that this number can be reduced to $2^{\kappa_n}$, and to $\kappa_n^+$ in the case $n = 1$, but cannot be further reduced to $\kappa_n$.

We show that the statement "every universally Baire set of reals has the perfect set property" is equiconsistent modulo ZFC with the existence of a cardinal that we call a virtually Shelah cardinal. These cardinals resemble Shelah cardinals but are much weaker: if $0^\sharp$ exists then every Silver indiscernible is virtually Shelah in $L$. We also show that the statement $\text{uB} = {\bf\Delta}^1_2$, where $\text{uB}$ is the pointclass of all universally Baire sets of reals, is equiconsistent modulo ZFC with the existence of a $\Sigma_2$-reflecting virtually Shelah cardinal.

We consider a weak version of Schindler's remarkable cardinals that may fail to be $\Sigma_2$-reflecting. We show that the $\Sigma_2$-reflecting weakly remarkable cardinals are exactly the remarkable cardinals, and we show that the existence of a non-$\Sigma_2$-reflecting weakly remarkable cardinal has higher consistency strength: it is equiconsistent with the existence of an $\omega$-Erd\H{o}s cardinal. We give an application involving gVP, the generic Vop\v{e}nka principle defined by Bagaria, Gitman, and Schindler. Namely, we show that gVP + "Ord is not $\Delta_2$-Mahlo" and $\text{gVP}({\bf\Pi}_1)$ + "there is no proper class of remarkable cardinals" are both equiconsistent with the existence of a proper class of $\omega$-Erd\H{o}s cardinals, extending results of Bagaria, Gitman, Hamkins, and Schindler.

We define a generic Vop\v{e}nka cardinal to be an inaccessible cardinal $\kappa$ such that for every first-order language $\mathcal{L}$ of cardinality less than $\kappa$ and every set $\mathscr{B}$ of $\mathcal{L}$-structures, if $|\mathscr{B}| = \kappa$ and every structure in $\mathscr{B}$ has cardinality less than $\kappa$, then an elementary embedding between two structures in $\mathscr{B}$ exists in some generic extension of $V$. We investigate connections between generic Vop\v{e}nka cardinals in models of ZFC and the number and complexity of $\aleph_1$-Suslin sets of reals in models of ZF. In particular, we show that ZFC + (there is a generic Vop\v{e}nka cardinal) is equiconsistent with ZF + $(2^{\aleph_1} \not\leq |S_{\aleph_1}|)$ where $S_{\aleph_1}$ is the pointclass of all $\aleph_1$-Suslin sets of reals, and also with ZF + $(S_{\aleph_1} = {\bf\Sigma}^1_2)$ + $(\Theta = \aleph_2)$ where $\Theta$ is the least ordinal that is not a surjective image of the reals.