
Combinatorics and Computing Weekly Seminar

سمینار هفتگی ترکیبیات و محاسبه




TITLE

Orthogonal signatures of graphs



SPEAKER




TIME

Wednesday, October 2, 2024,


14:00  15:00




VENUE 
Lecture Hall 1, Niavaran Bldg.



SUMMARY 


A signed graph is a pair $G_{\sigma}=(G, \sigma)$, where $G$ is a simple graph and $\sigma$, called the signature, is a function which assigns 1 or $1$ to each edge of $G$. We call $\sigma$ as an it orthogonal signature of $G$ if $A(G_{\sigma})^2=D$, where $A(G_{\sigma})$ is the signed adjacency matrix of $G_{\sigma}$ and $D$ is the diagonal matrix with vertex degrees on the diagonal.
We have shown that if $G$ has an orthogonal signature, then $G$ should be regular.
Graphs with orthogonal signature were crucial in the proof of sensitivity conjecture by Huang in 2019. Hunag used an orthogonal signature of hypercube in his proof. Alon and Zheng extended it from hypercubes to Cayley graphs of $\mathbb{Z}^{n}_2$. Other researchers had considered signed graphs with just two distinct eigenvalues. Note that the signed adjacency matrix of an orthogonal signature
of a $k$regular graph has only two distinct eigenvalues which are $\pm \sqrt{k}$. We also note the signed adjacency matrix of any signature of a $k$regular graph has spectral radius in the interval $[ \sqrt{k},k]$. So an orthogonal signature has the minimum spectral radius among all signatures of a regular graph. Orthogonal signatures have been classified for $3$regular and 4regular graphs. A partial answer for 5regular graphs is given by Stanic.
We will discuss general constructions for graphs with orthogonal
signature and also the classification of orthogonal signatures of $k$regular
graphs for a fixed $k$, specially for $k = 5, 6$.
This is a joint work with Bojan Mohar and Maxwell Levit.
Zoom room information:
https://us06web.zoom.us/j/85237260136?pwd=MFSZoKdmRXAjfaSaBzbf19lTaaKglf.1
Meeting ID: 852 3726 0136
Passcode: 362880




تهران، ضلع جنوبی
ميدان شهيد باهنر (نياوران)، پژوهشگاه
دانشهای بنيادی، پژوهشکده رياضيات
School of
Mathematics, Institute for Research in
Fundamental Sciences (IPM), Niavaran
Bldg., Niavaran Square, Tehran
ipmmath@ipm.ir
♦ +98 21
22290928 ♦
math.ipm.ir 


