[Koglist] Logic and Philosophy of Science, Domonkos Inges

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