ELFT HÍRADÓ

[Gömöri Márton <gomorim AT gmail.com>]

Logic and Philosophy of Science Seminar
Department of Logic, Institute of Philosophy
Eötvös Loránd University
Budapest, Múzeum krt. 4/i Room 224
_____________________________________________
P R O G R A M

The seminar is held in hybrid format, in person (Múzeum krt. 4/i Room 224)
and online. Zoom link
<https://us02web.zoom.us/j/84594385686?pwd=a7KPWoNLrPg11xNTi5Ug91YR5mHmmS.1>


27 March (Friday) 4:15 PM  Room 224 + ONLINE

Domonkos Inges
Eötvös Loránd University, Department of Logic
Title: About the distinguishing of *S(Kn)* and the usage of distinguishing
coloring in cryptographic protocols
_____________________________________________
ABSTRACT:

In this thesis, we consider a way of breaking a graph's symmetry:
distinguishing colorings. A distinguishing coloring *c* of *G* colors the
vertices of *G* so that the only automorphism of the colored graph *(G,c)* is
the identity map. The distinguishing number of *G*, *D(G)*, is the minimum
number of colors needed to create a distinguishing coloring of *G*. The
cost number of *G*, *ρ(G),* is the size of the minimum color class of an
optimal distinguishing coloring of *G*.

We provide the following result for the complete graph and its subdivision
graph: *ρ(S(Kn))=*ρ'*(*Kn*),* where *ρ'(G) *is the cost number of a
distinguishing edge coloring of *G*.

Furthermore, we present the known complexity of the language *DIST = {(G,k)
: D(G) ≤ k}*. We explore a research area by giving a sketch of a
zero-knowledge protocol for someone to commit to a distinguishing coloring
on a graph.
_____________________________________________

The seminar is open to everyone, including students, visitors, and
faculty members from all departments and institutes! Format: 60 minute
lecture, coffee break, discussion.
_____________________________________________

Organizers: Márton Gömöri and Zalán Molnár
_____________________________________________
LPS - Logic and Philosophy of Science (Student and Faculty Seminar)
Department of Logic, Institute of Philosophy
Eötvös University Budapest
http://phil.elte.hu/lps