<div dir="ltr"><div><div><span style="font-family:arial,sans-serif">Logic and Philosophy of </span><span style="font-family:arial,sans-serif">Science Seminar</span><br></div><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div><font face="arial, sans-serif">Department of Logic, Institute of Philosophy</font></div><div><font face="arial, sans-serif">Eötvös Loránd University</font></div><div><span style="font-family:arial,sans-serif">Budapest, </span><font face="arial, sans-serif">Múzeum krt. 4/i Room 224</font></div><div>_____________________________________________</div><div>P R O G R A M</div><div><br>T<font face="arial, sans-serif">he seminar is held in hybrid format, in person (Múzeum krt. 4/i Room 224) and online. <a href="https://us02web.zoom.us/j/84594385686?pwd=a7KPWoNLrPg11xNTi5Ug91YR5mHmmS.1" target="_blank">Zoom link</a> </font></div><div><font face="arial, sans-serif"><br></font></div><font face="arial, sans-serif">27 March (Friday) 4:15 PM  Room 224 + ONLINE       </font></div><div dir="ltr"><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><span style="text-align:-webkit-center">Domonkos Inges</span></font></div><div><font face="arial, sans-serif"><span style="text-align:-webkit-center">Eötvös Loránd University, Department of Logic</span></font></div><div dir="ltr"><font face="arial, sans-serif"><span style="color:rgb(0,0,0);text-align:center">Title: </span></font><span style="color:rgb(0,0,0)">About the distinguishing of </span><i>S(<span style="font-family:Arial,sans-serif">K_n</span><span style="color:rgb(0,0,0);font-family:-webkit-standard"></span>)</i><span style="color:rgb(0,0,0)"> and the usage of distinguishing coloring in<span class="gmail-Apple-converted-space"> </span></span><span style="color:rgb(0,0,0)">cryptographic</span><span style="color:rgb(0,0,0)"><span class="gmail-Apple-converted-space"> </span>protocols</span></div><div dir="ltr"><span style="font-family:arial,sans-serif">______________________________</span><span style="font-family:arial,sans-serif">_______________</span><br></div></div></div></div></div><div>ABSTRACT:<br></div><div><br></div><div>In this thesis, we consider a way of breaking a graph's symmetry: distinguishing colorings. A distinguishing coloring<span class="gmail-Apple-converted-space"> </span><i>c</i><span class="gmail-Apple-converted-space"> </span>of<span class="gmail-Apple-converted-space"> </span><i>G</i> colors the vertices of<span class="gmail-Apple-converted-space"> </span><i>G</i><span class="gmail-Apple-converted-space"> </span>so that the only automorphism of the colored graph<span class="gmail-Apple-converted-space"> </span><i>(G,c)</i><span class="gmail-Apple-converted-space"> </span>is the identity map. The distinguishing number of<span class="gmail-Apple-converted-space"> </span><i>G</i>,<span class="gmail-Apple-converted-space"> </span><i>D(G)</i>, is the minimum number of colors needed to create a distinguishing coloring of<span class="gmail-Apple-converted-space"> </span><i>G</i>. The cost number of<span class="gmail-Apple-converted-space"> </span><i>G</i>, <i><span style="color:rgb(32,33,34);font-family:sans-serif">ρ</span>(G),</i><span class="gmail-Apple-converted-space"> </span>is the size of the minimum color class of an optimal distinguishing coloring of<span class="gmail-Apple-converted-space"> </span><i>G</i>.<br></div><div><br>We provide the following result for the complete graph and its subdivision graph: <i><span style="color:rgb(32,33,34);font-family:sans-serif">ρ</span>(S(<span style="font-family:Arial,sans-serif">K_n</span><span style="color:rgb(0,0,0);font-family:-webkit-standard"></span>))=</i><span style="font-style:italic;color:rgb(32,33,34);font-family:sans-serif">ρ'</span><i>(</i><span style="font-style:italic;font-family:Arial,sans-serif">K_n</span><i><span style="color:rgb(0,0,0);font-family:-webkit-standard"></span>),</i><span class="gmail-Apple-converted-space"> </span>where<span class="gmail-Apple-converted-space"> </span><i><span style="color:rgb(32,33,34);font-family:sans-serif">ρ'(G)</span> </i>is the cost number of a distinguishing edge coloring of<span class="gmail-Apple-converted-space"> </span><i>G</i>.</div><div><br>Furthermore, we present the known complexity of the language<span class="gmail-Apple-converted-space"> </span><i>DIST = {(G,k) : D(G) ≤ k}</i>. 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.</div><div><div>_____________________________________________<br></div><div><br></div><div><div><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div><div><div><font face="arial, sans-serif">The seminar is open to everyone, including students, visitors, and faculty members from all departments and institutes! Format: 60 minute lecture, coffee break, discussion.</font></div></div></div><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div><div><div>_____________________________________________</div></div></div></div></div></div></div></div></div></div></div></div></div></div><br></div><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div><div><div><font face="arial, sans-serif">Organizers: Márton Gömöri and Zalán Molnár</font></div><div>_____________________________________________</div></div></div></div></div></div></div></div></div></div></div></div></div></div>LPS - Logic and Philosophy of Science (Student and Faculty Seminar)<br>Department of Logic, Institute of Philosophy<br>Eötvös University Budapest<br><a href="http://phil.elte.hu/lps" rel="noreferrer" target="_blank">http://phil.elte.hu/lps</a></div></div></div></div></div>