Raziskovalni matematični seminar - Arhiv

In this talk, a graph Γ = (V, E) is a finite simple graph, which means that V is a finite set and E is a family of its subsets that have two elements. Given two graphs Γ1 = (V1, E1) and Γ2 = (V2, E2), a map Φ : V1 → V2 is
a homomorphism if {Φ(u), Φ(v)} ∈ E2 whenever {u, v} ∈ E1. A bijective homomorphism is an isomorphism in the case {Φ(u), Φ(v)} ∈ E2 if and only if {u, v} ∈ E1. As usual, if Γ1 = Γ2, then a homomorphism/isomorphism is
an endomorphism/automorphism. A core of a graph Γ is any its subgraph Γ0 such that a) there exists some homomorphism from Γ to Γ0 and b) all endomorphisms of Γ0 are automorphisms.
In graph theory, Γ1 and Γ2 are usually treated as ‘equivalent’ if they are isomorphic, i.e. if there exists some isomorphism between them. Less frequent we meet the notion of homomorphically equivalent graphs Γ1, Γ2,
which means that there exists a graph homomorphism Φ : V1 → V2 and a graph homomorphism Ψ : V2 → V1. Here, the notion of a core appears very naturally because two graphs are homomorphically equivalent if and
only if they have isomorphic cores. Often, it is very difficult to decide if there exists a homomorphism between two graphs. In fact, this problem is related to many graph parameters that are hard to compute, such as the
chromatic/clique/independence number. As a result, the study of cores is challenging. In this talk, I will survey some properties of cores, with an emphasis on graphs that either admit a certain degree of ‘symmetry’ or have
‘nice’ combinatorial properties.

Everyone is welcome and encouraged to attend.