ABSTRACTS

Go back to seminar page

Richard Anstee (UBC)
Forbidden Configurations: An update

Steven Butler (UCSD)

Dan Pragel (Caltech)
ABSTRACT
A "central digraph" is a directed graph D such that given any two vertices x and y of D (not neccessarily distinct), there is a unique walk of length two from x to y. This occurs precisely when the adjacency matrix A of D has A^2 = J (the matrix of all ones). These also correspond to an algebraic structure called a "central groupoid." In this talk we examine some of the basic properties of these objects as well as different methods of constructing them.

Peter Keevash (Caltech)
ABSTRACT
Let f_m(a,b,c,d) denote the maximum size family of a family F of subsets of an m-element set so that there is no pair A,B ∈ F with

    |A∩ B|≥ a,     |A^c ∩ B|≥ b,     |A∩ B^c|≥ c,     |A^c∩ B^c|≥ d.

By symmetry we can assume a ≥ d and b ≥ c. We show that f_m(a,b,c,d) is Θ(m^a+b-1) if either b > c or a,b≥ 1. We also show f_m(0,b,b,0) is Θ(m^b) and f_m(a,0,0,d) is Θ(m^a). This can be viewed as a result concerning forbidden configurations, and provides further evidence for a conjecture of Anstee and Sali. Our key tool is a strong stability version of the Ahlswede-Khachatrian Complete Intersection Theorem, which is of independent interest.
This is joint work with Richard Anstee.

Yuval Roichman (Bar-Ilan)
Statistics on permutation groups, canonical words and pattern avoidance
ABSTRACT
The number of left to right minima of a permutation is generalized to Coxeter (and closely related) groups, via an interpretation as the number of "long factors" in canonical expressions of elements in the group.
This statistic is used to determine a covering map, which 'lifts' identities on the symmetric group S_n to the alternating group A_{n+1}. The covering map is then extended to 'lift' known identities on S_n to new identities on S_{n+q-1} for every positive integer q, thus yielding q-analogues of the known S_n identities.
Equi-distribution identities on certain families of pattern avoiding permutations follow. The cardinalities of subsets of permutations avoiding these patterns are given by extended Stirling and Bell numbers. The dual systems (determined by matrix inversion) have combinatorial realizations via statistics on colored permutations.
Joint with Amitai Regev.

Paul Zinn-Justin (Paris-Sud)
Towards a proof of the Razumov--Stroganov conjecture?
ABSTRACT
We shall review the remarkable properties of the O(1) Temperley--Lieb loop model and how they led Razumov and Stroganov to formulate a conjecture which relate it to Fully Packed Loops (FPL) and Alternating Sign Matrices (ASM). We shall then discuss recent attempts at proving this conjecture: in particular, we shall try to generalize it by introducing inhomogeneities and explain the connection with the Izergin--Korepin/Okada determinant formulae for the six-vertex model.

Terence Tao(UCLA)
The determinant and singularity probability of a random ± 1 matrix
ABSTRACT
Consider a random n x n matrix A whose entries are all +1 or -1 with equal independent probability of each. We describe some recent simplifications and progress in understanding the distribution of the determinant det(A), and in particular in estimating the probability that A is invertible. This is joint work with Van Vu.

Allen Knutson, UC Berkely
The glue between Young tableaux
ABSTRACT
Young tableaux, beloved of combinatorialists, tolerated by representation theorists and geometers, seem at first glance to be an unruly combinatorial set. I'll define a simplicial complex in which they index the facets, and slightly more general objects (Buch's "set-valued tableaux") label the other interior faces.
The theorem that says we're on a right track: This simplicial complex is homeomorphic to a ball. I'll explain why this is surprising, useful, and shows why Buch didn't discover the exterior faces too.
Finally, I'll explain how algebraic geometry forced these definitions on us (or, "How I made my peace with Young tableaux"). This work is joint with Ezra Miller and Alex Yong.

Richard Wilson (Caltech)
Revisiting the (t, k)-subset inclusion matrices
ABSTRACT
For integers $t,k,v$ with $0\le t,k\le v$, let $W_{tk}$ denote the $ v\choose t$ by $ v\choose k$ matrices whose rows are indexed by the $t$-subsets of an $v$-set, whose columns are indexed by the $k$-subsets of the $v$-set, and which are defined by $W_{tk}(T,K)=1$ if $T\subseteq K$ and $W_{tk}(T,K)=0$ otherwise. These matrices have played an important role in the theory of combinatorial designs and extremal set theory. Topics of interest include the modules and codes generated by the rows, the convex cone generated by the columns, and the Smith normal form of the matrices $W_{tk}$, and also the algebra spanned by the matrices $W_{tk}^\top W_{tk}$, $0\le t\le k$, which is the Bose-Mesner algebra of the Johnson scheme.
We survey results on these matrices, and we give some new proofs and some new applications. We will discuss, for example, the case of equality in the Frankl-Wilson inequalities and what we call $p$-ary $t$-designs.

Benny Sudakov, Princeton University
Max Cut - combinatorial perspective
ABSTRACT
The well-known Max Cut problem asks for the largest bipartite subgraph of a graph G. This problem has been the subject of extensive research, both from the algorithmic perspective in computer science and the extremal perspective in combinatorics. Let n be the number of vertices and e the number edges of G, and let b(G) denote the size of the largest bipartite subgraph of G. The extremal part of the Max Cut problem asks to estimate b(G) as a function of n and e. This question was first raised almost forty years ago and attracted a lot of attention since then.
In this talk we survey some old and recent bounds on the size of the largest bipartite subgraphs for various classes of graphs and obtain some new results. In particular we show that every K_4-free graph G with n vertices can be made bipartite by deleting at most n^2/9 edges. This proves an old conjecture of Erdos.

Dhruv Mubayi (University of Illinois)
New developments on Ramsey-Turan theory for hypergraphs
ABSTRACT
Ramsey-Turan problems are similar to the usual extremal (Turan) problems, except that we require the underlying hypergraph to be similar to a random hypergraph. After briefly surveying the current state of knowledge, I will describe several new results on Ramsey-Turan theory for hypergraphs. One of them allows us to prove a phenomenon similar to supersaturation. As a consequence, one can explicitly construct infinitely many triple systems with Ramsey-Turan density lower than the Turan density, thereby addressing one of the first questions in this area due to Erdos and Sos. (Joint work with Vojtech Rodl and Vera Sos).

Carlos Salazar-Lazaro (Caltech)
Progress on the existence problem of Skew Hadamard Difference Sets
ABSTRACT
We will consider the existence problem of Skew Hadamard Difference sets in Abelian p-groups. We will review the results by Qing Qiang. We will also transform the existance problem to the existence of an integral solution to the matrix equation A_Gx = p^{m-1/2) y where x and y are vectors of zeros and ones and the matrix A_G is a combinatorial matrix depending on the structure of G and the prime p. We will derive some properties of the matrix A_G and show its usefulness in giving existence conditions when $G$ is a special family of p-groups.

Pawel Wocjan (Caltech)
Limitations of nice mutually unbiased bases
ABSTRACT
Two orthonormal bases B and B' of a d-dimensional complex vector space are called mutually unbiased if and only if ||^2=1/d for all v in B and all v' in B'. The question of determining the maximal number of pairwise mutually unbiased bases for each dimension is an open problem. We determine the maximal number of mutually unbiased bases with a certain underlying group structure:
It is know that mutually unbiased bases can be constructed by partitioning suitably a so-called unitary error basis, i.e., a collection of d^2 unitary matrices that are orthogonal with respect to the trace inner product. We consider this construction when the unitary error basis is a nice error basis. A nice error basis is collection of unitary matrices that are obtained from projective representations of central type. We show that the number of resulting nice mutually unbiased bases can be at most one plus the smallest prime power contained in the dimension, and therefore that this construction cannot improve upon previous approaches. We prove this by establishing a correspondance between nice mutually unbiased bases and abelian subgroups of the index group of a nice error basis and then bounding the number of such subgroups. This bound also has implications for the construction of certain combinatorial objects called nets. Furthermore, we show that maximal sets of nice mut! ually unbiased bases, i.e., sets attaining the above bound, correspond to affine translation planes.

Pawel Wocjan (Caltech)
Eulerian orthogonal arrays
ABSTRACT
I would like to talk about Eulerian orthogonal arrays. My motivation for defining and constructing Eulerian OAs is that they could be used for some problems in quantum control theory.
Eulerian orthogonal arrays are orthogonal arrays over a group G which satisfy an additional property: if we choose any any t rows (where t denotes the strength of the OA) then they define an Eulerian cycle in the Cayley graph of G x ... x G (direct product of G with t components) with respect to some generating set that may depend on the choosen rows. Usual orthogonal arrays may be interpreted as follows: if we choose any t rows then they define Hamiltonian cycles in the complete directed graph with G x ... x G as vertex set. I will show how to construct Eulerian OAs from linear error correcting codes when G is the additive group of a finite field.

Peter Keevash (Caltech)
Multicoloured extremal problems
ABSTRACT
Many problems in extremal set theory can be formulated as finding the largest set system (or uniform set system) on a fixed ground set that does not contain some forbidden configuration of sets. We shall consider multicoloured versions of such problems, defined as follows. Given a list of set systems, which we think of as colours, we call another set system multicoloured if for each of its sets we can choose one of the colours it belongs to in such a way that each set gets a different colour. Given an integer k and some forbidden configurations, the multicoloured extremal problem is to choose k colours with total size as large as possible subject to containing no multicoloured forbidden configuration. This question arises naturally from the study of cycles in 3-uniform hypergraphs, but is also of interest in its own right, as it often proves necessary to develop new tools for the solution that cast light on some structural features of the original problem.
We shall consider a variety of classical problems from extremal combinatorics, for which determine the optimal constructions. For the multicoloured version of Sperner's theorem this was done by Daykin, Frankl, Greene and Hilton in 1981. We extend their result to some other Sperner problems, and also prove multicoloured versions of the generalized Erd\H{o}s-Ko-Rado theorem and the Sauer-Shelah theorem. Moving to extremal graph theory, we obtain multicoloured versions of Tur\'an's theorem and other forbidden subgraph results that fit the same pattern.
Finally, we give multicoloured versions of the Frankl--Ray-Chaudhuri-Wilson restricted intersection theorems, for which a key ingredient is a tight lower bound for the rank of the inclusion matrix of a set system. Our bound generalises the well-known result that if |{A}| < 2^{s+1} then the s^\ast-inclusion matrix has full rank |{A}|. In a combinatorial setting this fact was proved by Frankl and Pach in the study of null t-designs; it can also be viewed as determining the minimum distance of the Reed-Muller codes.
This talk is based on three works, which are co-authored with B. Sudakov and in various combinations with B. Bollobás, M. Saks and J. Verstraëte.

October 21
Pawel Wocjan (Caltech)
New Construction of Mutually Unbiased Bases in Square Dimensions
ABSTRACT
Two orthonormal bases B and B' of the Hilbert space C^d are called mutually unbiased if and only if ||^2=1/d for all v in B and all v' in B'. In this talk I will address the question of how many mutually orthogonal bases can be constructed for a given dimension. This question can be considered as a "quantum extension" of the design-theoretic problem of determining the maximal number of mutually orthogonal Latin squares for a given size.
We show that k=w+2 mutually unbiased bases can be constructed in any square dimension d=s^2 provided that there are w mutually orthogonal Latin squares of order s. The construction combines the design-theoretic objects (k,s)-nets (which can be constructed from w mutually orthogonal Latin squares of order s and vice versa) and generalized Hadamard matrices of size s. Using known lower bounds on the asymptotic growth of the number of mutually orthogonal Latin squares (based on number theoretic sieving techniques), we obtain that the number of mutually unbiased bases in dimensions d=s^2 is greater than s^1/14.8 for all s but finitely many exceptions. Furthermore, our construction gives more mutually orthogonal bases in many non-prime-power dimensions than the construction that reduces the problem to prime power dimensions.

October 7
Peter Keevash (Caltech)
The role of approximate structure in extremal combinatorics
ABSTRACT

Go back to Combinatorics Seminar Page