Algebraic and Geometric Representations of Combinatorial Structures

点击翻译按钮获取中文摘要

9970270Representations of graphs employing algebraic or geometric ideas is one of he central topics of combinatorial research. Their importance is highlighted by their applications in Theoretical Computer Science. The PIs continue their work on this subject and investigate three different aspects of representations. One of the goals of the PIs is to discover dense graphs not containg some fixed graph G as a subgraph. This problem is wide open once G is bipartite. The PIs search for algebraic or geometric representation of the appropriate graphs (e.g., Ramanujan graphs, norm graphs, polarity graphs). In another aspect of graph representations the type of representation is given and one tries to find the most efficient one for a class of graphs. The PI and the coPI investigate ``worst-case'' and ``average-case'' efficiencies of important representations. The methods here also include probability theory. Finally, the PIs apply appropriately chosen representations as tools in the determination of some other parameter or property of a combinatorial structure of interest. Graphs are made up of "vertices" and "edges" connecting some pairs of vertices. Behind the transparent definition hidden is a vast amount of complexity. One of the reasons the study of graphs is of paramount interest is their wide applicability in Computer Science. The "thinking" of today's computers is modeled by graphs. Algorithms often use specific exmples of graphs having a certain appropriately chosen structure. The speed of an algorithm could depend on the attributes of the graphs employed. The problems arising are part of a broader research area within Combinatorics, which aims at obtaining information about global properties of graphs under some local restrictions. The PIs tackle specific problems of this type. They apply ideas from algebra and geometry to obtain representations of graphs with excellent global properties. Another aspect of graph representations is the following. Expensive computer (disk) space can be saved by communicating the structure of a graph to the computer efficiently. In these problems the type of the representation, that is the the way of communication is fixed, and one tries to determine how well different graphs can be represented. The PI and the coPI investigate "economic" ways to represent graphs using representations from algebra and geomtry.