Go back to seminar page

Richard Anstee (UBC)

Forbidden Configurations: An update

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

By symmetry we can assume

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 |

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 |

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.

Peter Keevash (Caltech)

The role of approximate structure in extremal combinatorics

ABSTRACT

Go back to Combinatorics Seminar Page