A ``tournament'' is a digraph obtained from a complete graph by directing its edges, and ``colouring'' a tournament means partitioning its vertex set into acyclic subsets (``acyclic'' means the subdigraph induced on the subset has no directed cycles). This concept is quite like that for graph-colouring, but different. For instance, there are some tournaments H such that every tournament not containing H as a subdigraph has bounded chromatic number. We call them ``heroes''; for example, all tournaments with at most four vertices are heroes.
we will describe various models of sparse and planar graphs and the associated distributions of eigenvalues (and eigenvalue spacings) which come up. The talk will be light on theorems, and heavy on experimental data.
Let p be an odd prime number and let F be a totally real field. Let F_cyc be the cyclotomic extension of F generated by the roots of unity of order a power of p . From the maximal abelian extension of F_cyc which is unramified (resp. unramified outside auxiliary primes), we get exact sequences of Iwasawa modules. We will discuss how splitting of these exact sequences are linked to Leopoldt conjecture for F and p . (JW with C. Khare)
Associated to any simplicial graph there is a right-angled Coxeter group. Invariants of the Coxeter group such as its growth series or its weighted L^2 Betti numbers can be computed from the graph's clique complex (i.e., its flag complex).
A (q,k,t)-design matrix is an m x n matrix whose pattern of zeros/non-zeros satisfies the following design-like condition: each row has at most q non-zeros, each column has at least k non-zeros and the supports of every two columns intersect in at most t rows. We prove that for $m\geq n$, the rank of any $(q,k,t)$-design matrix over a field of characteristic zero (or sufficiently large finite characteristic) is at least $n - (qtn/2k)^2$ .
Using this result we derive the following applications:
In a sequence of recent papers, Sudan and coauthors have investigated the relation between testability of properties of Boolean functions and the invariance of the properties with respect to transformations of the domain. Linear-invariance is arguably the most common such symmetry for natural properties of Boolean functions on the hypercube. Hence, it is an important goal to find necessary and sufficient conditions for testability of linear-invariant properties.