Skip to Main Content
Sign In
Visit Apply Give

Archive : Discrete Mathematics

Image Picker for Section 0



Alex Kodess, Farmingdale State CollegeAlex Kodess, Farmingdale State CollegeEWG 336Title: Algebraically Defined Directed Graphs<br><br> Abstract:To view the abstract <a href="">click here</a>11/18/2019 7:30:00 PM11/18/2019 8:30:00 PMFalse
Daniel Katz, California State University at NorthridgeDaniel Katz, California State University at NorthridgeEWG 336Title: Rudin-Shapiro-Like Polynomials with Low Correlation<br><br> Description: The Rudin-Shapiro polynomials are a sequence of polynomials with coefficients in {+1,-1} arising from an elegant recursive construction that gives them interesting analytic and combinatorial properties. They are known to be very flat on the complex unit circle: if f is a Rudin-Shapiro polynomial and we let z range over the unit circle, then the ratio of the maximum value of |f(z)| to the root mean square value is never larger than the square root of 2. When we identify a polynomial with the sequence of its coefficients, we find that a typical Rudin-Shapiro polynomial has very low autocorrelation: the inner products of the sequence of coefficients with nontrivial translates of itself have considerably smaller mean square magnitude than what one would obtain with a typical random sequence with entries from {+1,-1}. The fact that the inner product is only large when the sequences are perfectly aligned makes such sequences very useful for synchronization in communications networks. For multi-user networks, we want to avoid confusing one user's sequence with another's, so we demand pairs of sequences that also have low cross-correlation (inner product with each other) at all shifts. We investigate pairs of Rudin-Shapiro-Like polynomials, a generalization of Shapiro's original recursive construction, and derive a general formula for their mean square cross-correlation. Borwein and Mossinghoff had shown that there are Rudin-Shapiro-like polynomials with low autocorrelation, and now we have found pairs of polynomials such that both have low autocorrelation and the pair has low mutual cross-correlation. There are bounds on how small these quantities can be, and we have found infinite families that achieve the bounds. This is joint work with Sangman Lee, Eli Moore, and Stanislav A. Trunov.11/11/2019 7:30:00 PM11/11/2019 8:30:00 PMFalse
Krystal Guo from Universite de Montreal, CanadaKrystal Guo from Universite de Montreal, CanadaEWG 336 Title: Distinguishing graphs with Weisfeiler-Lehman refinement and cellular algebras </br></br> Abstract: Cellular algebras were first studied by Weisfeiler and Lehman; in the course of analyzing their algorithm for Graph Isomorphism, they define matrix algebras which are graph invariants. Evdokimov and Ponomarenko show that the kth dimensional Weisfeiler-Lehman algorithm fails to distinguish two graph if the result matrix algebras are weakly isomorphic. In this talk, we will explore the Weisfeiler-Lehman algorithm, which still plays a large part in recent Graph Isomorphim algorithms. We will define the matrix algebras associated with WL-dimension and discuss the algebraic explanation of how graphs can fail to be distinguished by the algorithm.10/29/2019 3:30:00 PM10/29/2019 4:30:00 PMFalse
Krystal Guo, Universite de Montreal, CanadaKrystal Guo, Universite de Montreal, CanadaEWG 336Title: Algebraic graph theory and quantum walks<br><br> Description: A system of interacting quantum qubits can be modelled by a graph. The evolution of the quantum system can be completely encoded as a quantum walk in a graph, which can be seen, in some sense, as a quantum analogue of random walk. This gives rise to a rich connection between algebraic graph theory, linear algebra and quantum computing. In this talk, I will present recent results on the average mixing matrix of a graph; a quantum walk has a transition matrix which is a unitary matrix with complex values and thus will not converge, but we may speak of an average distribution over time, which is modelled by the average mixing matrix. This rank of matrix is somewhat surprisingly related to strongly cospectral vertices in a graph; two vertices are strongly cospectral if and only if the corresponding rows of the average mixing matrix are equal. This talk will not assume any prior knowledge of quantum computing or physics. 10/28/2019 5:30:00 PM10/28/2019 6:30:00 PMFalse

Page Settings and MetaData:
(Not Shown on the Page)
Page Settings
MetaData for Search Engine Optimization
<a target='_blank' href='/Lists/CalendarDiscreteMathematics/calendar.aspx' class='ms-promotedActionButton'> <span style='font-size:16px;margin-right:5px;position:relative;top:2px;' class='fa fa-pencil-square-o'></span><span class='ms-promotedActionButton-text'>EDIT CALENDAR</span> </a> WebPartEditorsOnly
  • Department of Mathematical Sciences
  • University of Delaware
  • 501 Ewing Hall
  • Newark, DE 19716, USA
  • Phone: 302-831-2653