Sign In
  • UD Search

Archive : Discrete Mathematics



Jason Williford, University of WyomingJason Williford, University of WyomingEWG 336Title: 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 PM3/17/2017 4:00:00 PMFalse
John Urschel, MITJohn Urschel, MITMemorial 111Title: 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 PM3/10/2017 4:30:00 PMFalse
Alexandra Kolla, University of Illinois at Urbana-ChampaignAlexandra Kolla, University of Illinois at Urbana-ChampaignEWG 336Title: 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 PM2/28/2017 5:00:00 PMFalse
Zeying Wang, Michigan TechZeying Wang, Michigan TechEWG 336Automorphisms 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 PM2/21/2017 5:00: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