3
$\begingroup$

Is there a cardinal $\kappa$ and a connected simple, undirected graph $G^* = (\kappa, E^*)$ such that whenever $G = (\kappa, E)$ is a connected graph, there is a graph homomorphism $f:G^*\to G$?

EDIT. Sorry - I forgot the word "connected" in 2 positions of the question. Moreover, I changed the title according to Peter Heinig's comment (thanks, Peter!).

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ To provide some more usual terminology: this asks for whether the concrete category whose objects are the irreflexive symmetric relations on specified sets, and whose morphisms are the graph-homomorphisms (in the most usual sense within graph theory) has a weakly initial object. $\endgroup$
    – Peter Heinig
    Commented Sep 9, 2017 at 10:07
  • 1
    $\begingroup$ If $\kappa$ is uncountable regular, then each connected graph of cardinality $\kappa$ contains a vertex of degree $\kappa$ and so embeds the $\kappa$-star: one vertex joined with $\kappa$ other vertices. This is not an answer, as it concerns homomorphisms which embed (i.e., distinct points go to distinct points, edges to edges, nonedges to edges or nonedges). $\endgroup$
    – Péter Komjáth
    Commented Sep 9, 2017 at 13:50

2 Answers 2

Reset to default
2
$\begingroup$

Obsolete answer to a previous edit: In the present statement the only possible $G^*$ is the empty graph, for any non-empty $G^*$ has no homomorphisms to empty $G$.

After the edit (with additional requirement of connecitivity): for every $\kappa$, the initial objects $G^*$ are exactly the connected bipartite graphs with vertex set $\kappa$. Indeed, parts of every bipartite $G^*$ can be mapped to endpoints of any edge of $G$. On the other hand, if $G^*$ is not bipartite, it does not have homomorphisms to bipartite $G$. The trivial special case is $\kappa \leq 1$, with the only object clearly being initial.

Improve this answer
$\endgroup$
0
1
$\begingroup$

Obsolete answer to initial version of OP. (and, to set the record straight: there was an error in my answer, and Mikhail Tikhomirov's was the only correct answer. The original version of the OP allowed empty graphs as the targets in the mapping property that the OP was asking for, and the only graph which admits a graph-homomorphism to the empty graph is the empty graph. Symbolically, the slice category $\mathsf{IrreflexiveSymmetricBinaryRelationsWithGraphHomomorphisms}/(\{\},\{\})$ equals the full subcategory consisting of the sole object $(\{\},\{\})$. It was wrong in my hasty answer to claim that the one-vertex graphs are weakly-initial: they are not, since they do not map into the empty graph. I will leave the answer as it is, for several reasons, yet will add a a warning.

Echoing Mikhail Tikhomirov's answer a bit: the answer to the question in the OP is evidently yes: EDIT: (what comes next is wrong) the (still: proper) class of one-vertex graphs (i.e., isomorphic copies of $K^1$) is the class of weakly initial objects of the category implicit in the OP, ENDOFWRONGSTATEMENT and [the following was true as long as the OP still allowed non-connected graphs; the empty graph is not connected] the empty graph is its unique initial object.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .