It looks like your browser does not have JavaScript enabled. Please turn on JavaScript and try again.

Jason Williford, University of Wyoming | Jason Williford, University of Wyoming | EWG 336 | Title: Q-polynomial association schemes with at most 5 classes Abstract: An association scheme can be thought of as a combinatorial generalization of a finite transitive permutation group, where the notion of global symmetry is replaced by certain local symmetry conditions. The definition of association scheme is due to Bose and Shimamoto in 1939, in the context of the design of experiments. Since then it has found connections to coding theory, group theory, and finite geometry. In the 1973 thesis of Philippe Delsarte, the author identified two special classes of association schemes: the so-called P-polynomial and Q-polynomial schemes. The schemes that are P-polynomial are precisely those generated by a distance-regular graph, in which Delsarte gave natural analogues to coding theory. Similarly, Delsarte gave a natural analogue to design theory in Q-polynomial schemes. However, Q-polynomial schemes have no analogous combinatorial definition. Consequently, much less is known about them then their P-polynomial counterparts. In this talk, we will discuss what is known about primitive 3-class Q-polynomial schemes, and imprimitive Q-polynomial schemes with at most 5 classes. We will also present new tables of parameter sets summarizing known constructions, non-existence results and open cases. | 3/17/2017 3:00:00 PM | 3/17/2017 4:00:00 PM | False | |

John Urschel, MIT | John Urschel, MIT | Memorial 111 | Title: Trace Theorems and Drawings of Planar Graphs Abstract: The trace operator is a crucial component of the theory of boundary value problems in partial differential equations. We prove variants of the theorems on continuity and existence of right inverse of the trace operator for discrete graphs and without any underlying geometry. We use such results to motivate a new algorithm for finding pictorial representations of planar graphs. | 3/10/2017 3:30:00 PM | 3/10/2017 4:30:00 PM | False | |

Alexandra Kolla, University of Illinois at Urbana-Champaign | Alexandra Kolla, University of Illinois at Urbana-Champaign | EWG 336 | Title: Matrix Signings, Expanders and Perfect 2-Matchings Abstract: The spectra of signed matrices have played a fundamental role in social sciences, graph theory and control theory. They have been key to understanding balance in social networks, to counting perfect matchings in bipartite graphs, and to analyzing robust stability of dynamic systems involving uncertainties. More recently, the results of Marcus et al. have shown that an efficient algorithm to find a signing of a given adjacency matrix that minimizes the largest eigenvalue could immediately lead to efficient construction of Ramanujan expanders. Motivated by these applications, this talk investigates natural spectral properties of signed matrices and address the computational problems of identifying signings with these spectral properties. There are three main results we will talk about: (a) NP-completeness of three signing related problems with (negative) implications to efficiently constructing expander graphs, (b) a complete characterization of graphs that have all their signed adjacency matrices be singular, which implies a polynomial-time algorithm to verify whether a given matrix has a signing that is invertible, and (c) a polynomial-time algorithm to find a minimum increase in support of a given symmetric matrix so that it has an invertible signing. | 2/28/2017 4:00:00 PM | 2/28/2017 5:00:00 PM | False | |

Zeying Wang, Michigan Tech | Zeying Wang, Michigan Tech | EWG 336 | Automorphisms of strongly regular graphs with applications to partial difference sets <br> <a href="/content-sub-site/Documents/wang_abst_s17.pdf">Abstract</a> | 2/21/2017 4:00:00 PM | 2/21/2017 5:00:00 PM | False |

This Page Last Modified On:

No

Archive

RRRR