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
T
he seminar is held in hybrid format, in person (Múzeum krt. 4/i Room 224) and online. Zoom link
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