Discrete Math Seminar
|
Time: 10:00 am-11:00 pm Wednesdays
Contact: Susanna Fishel
|
||
|
Date |
Speaker |
Topic/Abstract |
|
September 16 |
Andrew Jennings |
Title: Grading and voting in a strategic environment. Abstract: An aggregation function is one that is suitable for taking multiple grades from individuals and giving, as output, one societal grade. Suitable functions are ones that are monotonic and impartial, and which respect unanimity. Another desirable property is strategy-proofness. An aggregation function is strategy-proof if honesty is always the best strategy for any individual or group submitting grades. We characterize all strategy-proof aggregation functions and identify which aggregation functions are the best (with respect to certain norms). Simultaneous grading of multiple candidates (i.e. voting) is explored briefly. |
|
September 23 |
Dhruv Mubayi |
Title: Counting Substructures Abstract: For various (hyper)graphs F, we give sharp lower bounds on the number of copies of F in a (hyper)graph with a prescribed number of vertices and edges. Our results extend those of Rademacher, Erdos and Lovasz-Simonovits for graphs and of Bollobas, Frankl, Furedi, Keevash, Pikhurko, Simonovits and Sudakov for hypergraphs. The proofs use the hypergraph removal lemma and stability results for the corresponding Turan problem proved by the above authors. |
|
September 30 |
Charles J. Colbourn |
Title: Covering Arrays and Perfect Hash Families Abstract: A covering array is an N by k array with each cell containing an entry from an alphabet of size v. It has strength t if, whenever you choose t columns, and choose one of the v alphabet symbols for each column, there is at least one row of the array in which we find the prescribed symbols in the chosen columns. These combinatorial arrays have arisen in testing computer hardware and software, and generally in locating faults that result from component interactions. The explicit construction of covering arrays with "few" rows for given t, k, and v is a challenging problem. In this talk, we describe a strategy that employs the structure of the finite fields in two ways. First a covering array is constructed directly using the algebra of the field. Then a related object, a perfect hash family, is constructed from the field and used to inflate the number of columns of the covering array. We use this construction to explore a number of questions about the structure of arrays arising from the finite fields. |
|
October 7 |
Jacob White |
Title: Discrete Morse Theory and Subspace Arrangements Abstract: Discrete Morse Theory is a tool for translating problems in algebraic topology into problems in enumerative combinatorics and graph theory, in particular the theory of matchings. It was developed by Robin Forman. We will give an introduction into this theory, as well as mention a few applications of this theory. In particular, we will apply the theory to the study of certain subspace arrangements, to obtain a homology basis indexed by certain types of ordered set partitions. Knowledge of algebraic topology is not required. This is joint work with Helene Barcelo and Christopher Severs. |
|
October 14 |
No Seminar |
|
|
October 21 |
Victoria Horan |
Title: Zero-Knowledge Proof Systems Abstract: Zero-knowledge proof systems consist of an interaction between parties to prove the possession of private knowledge without revealing any information about it. One approach is to base zero-knowledge proof systems on the instances and solutions of NP-complete and NP-hard problems. This talk discusses this method with a focus on the problems within the class NP-complete that are related to graph theory. It is based on work done in an ongoing project at the Air Force Research Lab Information Directorate. |
|
October 28 |
Ben Hester |
Title: Graph Pebbling and Linear Optimization Abstract: Many well-known graph invariants can be modeled as linear optimization problems. Specific examples include chromatic number, clique number, and matching number. Relaxing the integer constraints on these optimization problems creates the corresponding fractional graph invariants. In this talk, we show that the optimal pebbling number of a graph obeys a similar generalization. Consequently, we introduce the optimal fractional pebbling number and some of the results that follow by analyzing this value from the lens of linear optimization. |
|
November 4 |
Junling Zhou |
Title: Large Sets of Triple Systems Abstract: In this talk I will focus on the large set problems in Combinatorial Designs. Some development on large sets of pure oriented triple systems and Kirkman triple systems will be introduced. |
|
November 11 |
Gregg Musiker |
|
|
November 18 |
Andrzej Czygrinow |
|
|
November 25 |
Charlie Buehrle |
Title: A New Construction of Kazhdan-Lusztig’s representations of the Hecke Algebra Abstract: We state vanishing results for Kazhdan-Lusztig immanants be- longing to the quantum polynomial ring. Applying these results we find a new construction of Kazhdan-Lusztig’s representation of the Hecke algebra without employing the Kazhdan-Lusztig preorder. |
|
|
|
|
|
|
|
|
| fall08 spring09 | ||
