Combinatorics
In this talk, I will introduce a new algebraic structure called "contractad" resembling the contraction of a subgraph in a simple connected graph.
Examples of contractads include Hamiltonian paths, spanning trees, and configuration spaces.
These examples admit presentations with quadratic relations and standard methods of homological algebra may help us to get functional equations for generating series.
As an application, I will show a simple generating series counting Hamilton paths, Hamilton cycles and chromatic polynomials for complete multipartite graphs.
The talk is based on joint works with D.Lyskov.
We consider the continuous-time random walk on $G\wr S_n$, the complete
monomial group of degree $n$ over a finite group $G$.
An analogue of the Aldous' spectral gap conjecture is presented and proved.
For more details, see enclosed file.
An important combinatorial characteristic of finite-dimensional algebras is their length. The length of a finite system of generators for a finite-dimensional
algebra over a field is the least positive integer $k$, such that the products of generators of length not exceeding $k$ span this algebra as a vector space.
The maximum length over all systems of generators of an algebra is called the length of this algebra.
Length function is an important invariant widely utilized to investigate finite dimensional algebras since 1959.
It is actively used in various applications, for example, in mechanics of isotropic continua or in quantum sciences.
However, even the length of the matrix algebra is unknown. It was conjectured by Azaria Paz in 1984 that the length of the full matrix algebra is a linear function
on the size of matrices, and this conjecture is still open. It turns out that the investigation of the length function requires a number of tools from algebra and combinatorics. In particular, the length of nonassociative algebras is closely related with the integer sequences known in combinatorics as addition chains. These are the sequences where each term is a sum of two previous terms. The most well-known example of an addition chain is the Fibonacci sequence. In the talk we obtain optimal upper bounds for the length of several classes of non-associative algebras using addition chains and prove some other results on the length of algebras.
The talk is based on the series of joint works with Dmitry Kudryavtsev, Olga Markova and Svetlana Zhilina.
In 1961, Solomon proved that the sum of all the entries in the character
table of a finite group does not exceed the cardinality of the group.
We state a different and incomparable property here -- this sum is at
most twice the sum of degrees of the irreducible characters. Although
this is not true in general, it seems to hold for "most" groups. We
establish the validity of this property for symmetric, hyperoctahedral
and demihyperoctahedral groups. Using these techniques, we are able to
show that the asymptotics of the character table sums is the same as the
number of involutions in these groups. We will also derive generating
functions for the character tables sum for these groups as infinite
products of continued fractions.
This is joint work with D. Paul and H. K. Dey (Arxiv:2406.06036).
Which 4-manifolds admit a flag-no-square triangulation? Just one family of examples, described by Przytycki and Swiatkowski, was known.
We introduce two “gluing” operations which allow us to construct new examples of flag-no-square 4-manifolds.
Furthermore, our construction technique may be of independent interest: we take copies of a single such 4-manifold
(which we know very little about) and carefully apply our operations to obtain 4-manifolds with many different flag-no-square triangulations.
The unsigned Stirling numbers c(n,k) of the first kind give the Hilbert function for two algebras
associated to the hyperplane arrangement in type A, the Orlik-Solomon algebra and the graded Varchenko-Gelfand
algebra. Both algebras carry symmetric group actions with a rich structure, and
have been well studied by topologists, algebraists and combinatorialists: the first coincides with the Whitney homology
of the partition lattice, and the second with a well-known decomposition (Thrall's decomposition,
giving the higher Lie characters) of the universal enveloping algebra of the free Lie algebra.
In each case the graded representations have dimension c(n,k).
Both these algebras are examples of Koszul algebras, for which the Priddy resolution defines a group-equivariant dual Koszul algebra.
Now the Hilbert function is given by the Stirling numbers S(n,k) of the second kind, and hence the Koszul duality relation defines representations
of the symmetric group whose dimensions are the numbers S(n,k).
Investigating this observation leads to the realisation that this situation generalises to all supersolvable matroids.
The Koszul duality recurrence is shown to have interesting general consequences.
For the resulting group representations, it implies the existence of branching rules which, in the case of the braid
arrangement, specialise by dimension to the classical enumerative recurrences satisfied by the Stirling numbers of both kinds.
It also implies representation stability in the sense of Church and Farb.
The associated Koszul dual representations appear to have other properties that are more mysterious;
for example, in the case of the braid arrangement, the Stirling representations of the Koszul dual
are sometimes tantalisingly close to being permutation modules.
We also show a connection with the homology of the subword order poset, from previous work of the speaker, where Stirling numbers
arise again in the representations.
The local h-polynomial is a fundamental enumerative invariant
of a triangulation Δ of a simplex. This talk aims to review its
remarkable combinatorial properties, discuss nice examples and address
the following question: Which triangulations of the simplex have a
real-rooted h-polynomial? Our main result states that this is the case
when Δ is the barycentric subdivision of any triangulation of the
simplex. The proof is based on a new combinatorial formula for the
local h-polynomial, which is valid when Δ is any uniform triangulation
of any triangulation of the simplex, and on the study of a family of
polynomials which refine and interpolate between Eulerian and
derangement polynomials. A combinatorial interpretation of the local
h-polynomial of the second barycentric subdivision of the simplex will
be deduced.
The classical theory of type A crystals provides a graphical framework for proving Schur positivity results.
In this talk we will discuss a new category of "square root crystals" (introduced implicitly in the work of Yu) that can be used to establish instances of Grothendieck positivity.
For example, Buch's combinatorial interpretation of the coefficients expanding products of symmetric Grothendieck functions has a simple description in terms of the natural tensor product for this category.
We will also discuss some shifted analogues and applications to a conjectural formula of Cho-Ikeda for K-theoretic Schur P-functions.
In a seminal paper, Grunewald, Segal and Smith (1988) introduced zeta functions of groups and rings, enumerating various types of sub-objects, such as subgroups or two-sided ideals of finite index. Computations of these functions involve other enumeration problems in algebra and combinatorics.
Our main focus will be on zeta functions enumerating ideals of finite (additive) index, in nilpotent rings of class 2. It is well known that in this case there is a decomposition into an Euler product of local factors indexed by primes. The local factors are rational functions over the rationals, but their explicit computation is usually a very hard problem.
We show that the complexity of computing the ideal zeta function of an amalgamated direct power of such rings does not increase by the amalgamation. More generally, we prove this for the zeta functions of quiver representations introduced by Lee and Voll (2021). The proof of rationality of the local factors relies on techniques from model theory, and their explicit computation uses tools from algebraic combinatorics. Such methods are likely to be applicable to other combinatorial enumeration problems in which one wants to prove polynomiality, rationality or uniformity.
This is a joint work with Michael Schein.
No prior experience with zeta functions of groups and rings will be assumed.
For a set $\Pi$ of permutations (patterns) in $S_k$, consider the set of all permutations in $S_n$ that avoid all patterns in $\Pi$. An important problem in current algebraic combinatorics is to find pattern sets $\Pi$ such that the corresponding quasi-symmetric function is symmetric for all $n$. Recently, Bloom and Sagan proved that for any $k \ge 4$, the size of such $\Pi$ must be at least $3$ (with one exception), and asked for a general bound.
In this talk, we prove that the minimal size of such $\Pi$ is exactly $k - 1$. The proof uses a new variant of a theorem of Ray-Chaudhuri and Wilson in extremal combinatorics. This variant is proved using the polynomial approach of Alon, Babai and Suzuki to the original theorem.
No prior knowledge will be assumed.
This work is a part of an MSc Thesis, supervised by Ron Adin and Yuval Roichman.
Convex polytopes are among the most fundamental geometric objects, and have numerous applications ranging from art, through engineering, to applied mathematics and computer science.
In this talk we will consider several questions about polytopes, focusing on combinatorial and geometric aspects. In particular, we will mention questions about the realization spaces of polytopes, Voronoi's conjecture on parllelohedra, face numbers of cubical polytopes and the VC-dimension of polytopes.
Given a set $P$ of $m \geq 3$ points in general position in the plane, we want to find the smallest possible number of convex polygons with vertices in $P$ such that the edges of all these polygons contain all the ${m \choose 2}$ straight line segments determined by the points of $P$.
We show that if $m$ is odd, the answer is $\frac{m^2-1}{8}$ regardless of the choice of $P$. The answer in the case where $m$ is even depends on the choice of $P$ and not only on $m$. Nearly tight lower and upper bounds follow in the case where $m$ is even.
Based on joint work with Rom Pinchasi.
The quasisymmetric generating function of an inverse descent class is known to be symmetric, and there is a corresponding descent representation of the symmetric group. This result was generalized to products of inverse descent classes and Schur-positive sets of permutations by Elizalde and Roichman (2017), and to signed permutations by Adin, Athanasiadis, Elizalde and Roichman (2017).
In this talk we present colored extensions of these two results. Proof ingredients include a new notion of colored ribbon, a colored version of Stanley's shuffling theorem, and a character formula for colored descent representations.
All relevant notions will be explained in the talk.
Let T be a subset of R^d, such as a ball, a cube or a cylinder, and consider all possibilities for packing translates of T, perhaps with its rotations, in some bounded domain in R^d. How does a typical packing of this sort look like? One mathematical formalization of this question is to fix the density of the packing and sample uniformly among all possible packings with this density. Discrete versions of the question may be formulated as choosing a random independent set in a suitable lattice graph.
The question arises naturally in the sciences, where T may be thought of as a molecule and its packing is related to the spatial arrangement of molecules of a material under given conditions. In some cases, the material forms a liquid crystal - states of matter which are, in a sense, between liquids and crystals.
I will review ideas from this field, mentioning some of the predictions and the mathematical progress. Time permitting, I will elaborate on a recent result, joint with Daniel Hadas, on the structure of high-density packings of 2x2 squares with centers on the square lattice.
The talk is meant to be accessible to a general mathematical audience.
The amplituhedron A(n,k,m) is a geometric object, discovered by Arkani-Hamed and Trnka (2013) in the study of scattering amplitudes in quantum field theories. They conjectured that A(n,k,4) admits a decomposition based on a certain combinatorial structure. The components are images of BCFW positroid cells of the Grassmannian Gr(k,n), which arise from the Britto–Cachazo–Feng–Witten recurrence (2005).
In a recent paper with Tsviqa Lakrec and Ran Tessler, we prove this conjecture. In the talk, I will review the amplituhedron, its BCFW triangulation, and the main ideas of the proof.
Joint work with Tsviqa Lakrec and Ran Tessler.
We prove a 1973 conjecture of Erdős on the existence of Steiner triple systems with arbitrarily high girth. (The girth of an STS is the smallest g>3 for which there exist g vertices spanning at least g-2 triangles.) Our construction builds on the methods of iterative absorption (Glock, Kühn, Lo, and Osthus) and the high-girth triangle removal process (Glock, Kühn, Lo, and Osthus and independently Bohman and Warnke). In particular, we extend iterative absorption to handle triangle-decompositions of sparse graphs. We also introduce a moments-based technique, similar to Kim--Vu polynomial concentration for dependent random variables, which allows a unified approach to control statistics of complex random processes.
The talk will include an overview of iterative absorption.
This is joint work with Matthew Kwan, Ashwin Sah, and Mehtaab Sawhney.
Based on arXiv:2201.04554.
In this talk we will discuss the Leray and collapsibility numbers of a simplicial complex K, and their role in Helly-type theorems in combinatorial geometry. The Leray number is, roughly speaking, the hereditary homological dimension of K, while the collapsibility number captures the complexity of dismantling K by sequentially removing free faces from K.
Following the formal definition of these parameters and their connection to the combinatorics of convex sets, we will introduce the construction of the “tolerance complex” of a complex K. We will explain its relation to a tolerant version of Helly’s theorem due to Montejano and Oliveros and present new results on the Leray numbers of these complexes.
The talk is based on joint work with Minki Kim.
Fix a finite field K and a word w in a free group F. A w-random element in GL_n(K) is obtained by substituting the letters of w with uniform random elements of GL_n(K). For example, if w = abab^{-2}, a w-random element is ghgh^{-2} with g,h independent and uniformly random in GL_n(K). The moments of w-random elements reveal a surprising structure which relates to the free group algebra K[F].
In this talk I will describe what we know about this structure, and draw some analogies to w-random permutations.
This is joint work with Doron Puder and Matan Seidel.
Given a finite set $P \subseteq \mathbb{R}^d$, points $a_1, a_2, \dots, a_{\ell} \in P$ form an $\ell$-hole in $P$ if they are the vertices of a convex polytope which contains no points of $P$ in its interior.
We construct arbitrarily large point sets in general position in $\mathbb{R}^d$ having no holes of size $2^{7d}$ or more. This improves the previously known upper bound of order $d^{d+o(d)}$ due to Valtr. Our construction uses a certain type of designs, originating from numerical analysis, known as ordered orthogonal arrays. The bound may be further improved, to roughly $4^d$, via an approximate version of such designs.
Joint work with Boris Bukh and Ting-Wei Chao.
Let T be a set of n triangles in 3-space, and let \Gamma be a family of algebraic arcs of constant complexity in 3-space. We show how to preprocess T into a data structure that supports various \emph{intersection queries} for query arcs \gamma \in \Gamma, such as detecting whether \gamma intersects any triangle of T, reporting all such triangles, counting the number of intersection points between \gamma and the triangles of T, or returning the first triangle intersected by a directed arc \gamma, if any (i.e., answering arc-shooting queries). Our technique is based on polynomial partitioning and other tools from real algebraic geometry, among which is the cylindrical algebraic decomposition.
Our first result is an O^*(n^{4/3})-size data structure that answers a query in O^*(n^{2/3}) time. Next, we devise an O^*(n)-size data structure that answers a query in O^*(n^{4/5}) time. Incorporating this structure at the leaf nodes of the main structure reduces its overall size to O^*(n^{11/9}), without affecting its query time which remains O^*(n^{2/3}). We also present a data structure that provides a trade-off between the query time and the size of the data structure. For example, if \Gamma is a family of algebraic arcs defined by t > 1 real parameters, increasing the storage to O^*(n^{3/2}) decreases the query time to O^*(n^{\rho}), where \rho=\max {1/2, (2t-3)/3(t-1)} < 2/3. We also show that this query time can be further improved for circular query arcs.
Our approach can be extended to many other intersection-searching problems in three and higher dimensions. We exemplify this versatility by giving an efficient data structure for answering segment-intersection queries amid a set of spherical caps in 3-space, and we lay a roadmap for extending our approach to other intersection-searching problems.
Joint work with Pankaj Agarwal, Boris Aronov, Matya Katz, and Micha Sharir.
In the site percolation model, a random induced subgraph G[R] of a given graph G is formed by putting every vertex v of G into a random subset R with probability p and independently. One then researches typical properties of G[R], like the sizes of its connected components.
Here we study site percolation on pseudo-random graphs, specifically on (n,d,\lambda)-graphs, which are d-regular graphs on n vertices with all eigenvalues but the first (trivial) one bounded in absolute values by \lambda. It is well known that, assuming that the eigenvalue ratio \lambda/d is small, the edge distribution of an (n,d,\lambda)-graph resembles closely that of a truly random graph G(n,p) with the same expected density p=d/n.
We focus on the so-called supercritical regime p=(1+\epsilon)/d, for a positive constant \epsilon>0. In this range, we establish the asymptotic order of the giant component (a component of size proportional to |R|) in G[R] and show that it is typically unique. We also discuss further properties of the giant.
A joint work with Michael Krivelevich.
The affine Weyl group G of type C has many natural actions on finite
combinatorial objects (for example on the so called "arc permutations").
Their common feature is an action of the finite Weyl group of type C and
a "rotation", a one dimensional linear action of the translation
subgroup. The action of the finite Weyl group is multiplicity-free, so a
natural question arose, whether the original action is also
multiplicity-free? It turns out that it is not, but it is "almost," that
there exists a G equivariant pairing of the underlying objects that the
action on the pairs is multiplicity-free.
The whole structure of the question and the proof suggests a natural
generalisation to arbitrary types. Let G be any affine Weyl group,
acting by its finite Weyl group and a one dimensional "rotation." When
is this action multiplicity-free? And if not, is there a G-equivariant
pairing such that the action on pairs is multiplicity-free?
Part of the work was joint with Ron Adin and Yuval Roichman.
In this talk, we focus on the properties of a random walk on the alternating group $A_n$ generated by $3$-cycles of the form $(i,n-1,n)$ and $(i,n,n-1)$. We call this the transpose top-$2$ with random shuffle. We find the spectrum of the transition matrix of this shuffle. We show that the mixing time is of order $\left(n-\frac{3}{2}\right)\log n$ and prove that there is a total variation cutoff for this shuffle.
Stable permutations are a class of permutations that arises
in the study of the automorphism group of the Cuntz algebra.
In this talk I will define stable permutations, explain the
connection to the automorphisms of the Cuntz algebra, and
describe the main results known about them. I will then
present a characterization of stable permutations in terms
of certain associated graphs. As a consequence of this
characterization I will prove a conjecture in [Advances in Math.,
381(2021) 107590], and I will characterize explicitly stable
4 and 5-cycles.
This is joint work with Roberto Conti and Gleb Nenashev.
The cyclic descent statistic that can be defined on certain permutation sets and other combinatorial objects, as a cyclic equivariant extension of the classical descent statistic. Cyclic descents were introduced by Klyachko and Cellini in the late 20th century, and further studied by many. An axiomatic approach was presented by Rhoades, further developed by Adin, Reiner and Roichman and others.
In a recent work, Adin, Hegedus and Roichman characterize the conjugacy classes in the symmetric group, which carry a cyclic descent extension. A related permutation set is the set of roots of unity of fixed order in the symmetric group. In this talk we show that roots of unity of order $p^k$ in the symmetric group $S_n$ carry a cyclic descent extension if and only if $p$ and $n$ are not coprime. The proof involves a detailed study of unimodal permutations, their structure and enumeration.
Necessary background will be provided in the talk.
We will construct a family of S_n modules with the property
that upon restriction to S_{n-1} they recover the classical parking
function representation of Haiman. The representation is conjecturally
isomorphic to a construction from Berget--Rhoades. We will also
mention some (conjectured) connections with Donaldson--Thomas
invariants of the m-loop quiver.
We define combinatorially a partial order on the set partitions.
This order appears to be equivalent to the Bruhat–Chevalley–Renner order on the upper triangular matrices.
We exhibit a connection between two statistics on set partitions --
the intertwining number (introduced by Richard Ehrenborg and Margaret Readdy in 1998)
and the depth-index (our parameter which is the rank function of our poset of set partitions).
This talk is based on joint works with Mahir Bilen Can and Martin Rubey.
The coefficients of the chain polynomial of a finite poset
enumerate chains in the poset by their number of elements. The chain
polynomials of geometric lattices are conjectured in this talk to have
only real roots and the analogous question is discussed for other
important classes of Cohen--Macaulay posets. Among other partial
results, the conjecture is proven for the subspace and the partition
lattices. An application to the face enumeration of the second
barycentric subdivision of the boundary complex of the simplex will
be given. This is joint work with Katerina Kalampogia-Evangelinou.
Combinatorial objects and methods naturally appear in the study of aperiodic order and mathematical quasicrystals. In the talk I will describe how aspects of matchings, graphs, counting and discrepancy can imply results on certain measures of order and disorder in long-range geometry, with applications to classical constructions such as the Penrose tiling as well as to recent developments in aperiodic order. Partially based on joint work with Yaar Solomon.
The multicolor hypergraph Ramsey number Rk(s,r) is the minimal n, such that in any k-coloring of all r-element subsets of [n], there is a subset of size s, all whose r-subsets are monochromatic.
We present a new "stepping-up lemma" for Rk(s,r): If Rk(s,r)>n, then Rk+3(s+1,r+1)>2n. Using the lemma, we improve some known lower bounds on multicolor hypergraph Ramsey numbers.
Furthermore, given a hypergraph H=(V,E), we consider the Ramsey-like problem of coloring all r-subsets of V such that no hyperedge of size >r is monochromatic.
We provide upper and lower bounds on the number of colors necessary in terms of the chromatic number χ(H). In particular, we show that this number is O(log(r−1)(r⋅χ(H))+r), where log(m) denotes m-fold logarithm.
Joint work with Bruno Jartoux, Shakhar Smorodinsky, and Yelena Yuditsky.
Shrub-depth is a graph invariant often considered as an extension of tree-depth to dense graphs. In this talk I will explain our recent proofs of two results about graphs of bounded shrub-depth.
1. Every graph property definable in monadic-second order logic, e.g., 3-colorability, can be evaluated by Boolean circuits of constant depth and polynomial size, whose depth only depends on the shrub-depth of input graphs.
2. Graphs of bounded shrub-depth can be characterized by a finite set of forbidden induced subgraphs [Ganian et al. 2015].
Central to the first result is the definability in first-order logic of tree-models for graphs of bounded shrub-depth. For the second result, we observe that shrub-depth can be easily generalized to infinite graphs, and thus some classical tools, i.e., Craig's Interpolation and the Łoś-Tarski Theorem in model theory, are applicable to graphs of bounded shrub-depth.
This is joint work with Jörg Flum.
X = a_1 x_1 + ... + a_n x_n,
We discuss various aspects in which Rademacher sums behave "somewhat" like normally distributed variables.
A relevant puzzle by Bogusław Tomaszewski, 1986:
Is it true that all Rademacher sums X satisfy Pr[ |X| <= sqrt Var(X) ] >= 1/2 ?
Joint work with Nathan Keller.
In this talk we will discuss an improved upper bound, an algorithm achieving this bound, and a lower bound showing the algorithm is asymptotically tight for fat regions.
Based on joint work with Reuven Cohen and Shai Gul.
Joint work with Nati Linial.
An interval graph is the intersection graph of a family of intervals in the real line. Motivated by problems in ecology, Roberts defined the boxicity of a graph G to be the minimal k such that G can be written as the intersection of k interval graphs.
A natural higher dimensional generalization of interval graphs is the class of d-representable complexes. These are simplicial complexes that carry the information on the intersection patterns of a family of convex sets in R^d. We define the d-boxicity of a simplicial complex X to be the minimal k such that X can be written as the intersection of k d-representable complexes.
A classical result of Roberts, later rediscovered by Witsenhausen, asserts that the boxicity of a graph with n vertices is at most n/2. Our main result is the following high dimensional extension of Roberts' theorem: Let X be a simplicial complex on n vertices with minimal non-faces of dimension at most d. Then, the d-boxicity of X is at most (n choose d)/(d+1).
Examples based on Steiner systems show that our result is sharp. The proofs combine geometric and topological ideas.
The well-known Worpitzky identity provides a connection between two bases of ![\mathbb{Q}[x]](https://ci3.googleusercontent.com/proxy/nTjOjEPuaUIy5XDBTWqxasdncagVZAAoLsvLvFw9bg1JA8IHibi-ELj9WVOGkRxuQV9pnW6gEVzdpDznpbqjXVu1QotlngPIcJ5-fbKZpGaNaM7-SrTknzlfVabyQLV0x2QTqdJ9vQ=s0-d-e1-ft#https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathbb%7BQ%7D%5Bx%5D)
%5En)
Brenti has generalized this identity to the Coxeter groups of types 
Motivated by Foata-Schützenberger and Rawlings' proof for the Worpitzky identity in the symmetric group, we provide combinatorial proofs of this identity and for its 
Joint work with David Garber and Mordechai Novick.
Let 
![\Gamma_g=\langle a_1,b_1,\ldots,a_g,b_g \mid [a_1,b_1]\cdots[a_g,b_g]\rangle](https://ci5.googleusercontent.com/proxy/IgKspqTgm38WSw9ShzFYs1GInnVJipZTzPjpchyk42pvyH2t6AdBsiXxiQTHmIQ2lHDCkeE9J2tlXk_xZbhxoFQSHIztt6DI7uz_9xjyxu7yOhPYtPcdh69A0I0XS4JDAyE4rx4rkHtjLf8HpYdKnax7WwVKKDaxdsdDcu8n0l53l0rRwwcQ0GiiOUcoYm2TsK1V7BY2K4FaDI7cAGuvAZITgO4QF2QUahpk6-nIdU_TLTbZsZ8HoncWJH7stUwmXZsdG5M=s0-d-e1-ft#https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5CGamma_g=%5Clangle%09a_1,b_1,%5Cldots,a_g,b_g%09%5Cmid%09%5Ba_1,b_1%5D%5Ccdots%5Ba_g,b_g%5D%5Crangle)
We develop new techniques to study the random permutation )
This is joint work with Michael Magee.
The resonance arrangement is the arrangement of hyperplanes which has all nonzero 0/1-vectors in R^n as normal vectors. It is also called the all-subsets arrangement. Its chambers appear in algebraic geometry, in mathematical physics, and as maximal unbalanced families in economics.
In this talk, I will present a universality result of the resonance arrangement. Subsequently, I will report on partial progress on counting its chambers. Along the way, I will review some basics of the combinatorics of general hyperplane arrangements.
We define a statistic on the hyperoctahedral group B_n; this is a special case of one introduced by Stembridge and Waugh. We show that a certain two-variable generating function involving this statistic factors into the product of a generating function over the symmetric group S_n and some simple binomials. Then we mention related results by Macdonald and Carnevale-Shechter-Voll, and discuss what the correct way to state and prove our identity should be.
Our motivation for this work comes from counting finite-index subgroups of the centrally amalgamated product of n copies of the discrete Heisenberg group whose profinite completion is isomorphic to that of the ambient group; we describe how the above-mentioned identity enables us to complete a computation begun 25 years ago by du Sautoy and Lubotzky.
This is joint work with Mark Berman.
A d-partite hypergraph is called *fractionally balanced* if there exists a non-negative function on its edge set that has constant degrees in each vertex side. Using a topological version of Hall's theorem, we prove new lower bounds on the matching number of such hypergraphs. Our bounds yield results on envy-free division of multiple cakes, covering colorful families of d-intervals, and rental harmony with multiple houses.
Joint work with Ron Aharoni, Eli Berger, Joseph Briggs and Shira Zerbib.
We present an explicit formula for the generating function for the number of permutations of length $n$ that avoid $1324$, in terms of generating functions for permutations that have a kernel shape of length $m$, $m \ge 2$. This allows us to write down a systematic procedure for finding a lower bound for approximating the Stanley-Wilf limit of the pattern $1324$.
Joint work with Christian Nassau.
A systematic study of avoidance of mesh patterns of length 2 was conducted by Hilmarsson et al. in 2015. In a recent paper, Kitaev and Zhang examined the distribution of the aforementioned patterns.
We show that two pairs of triple mesh patterns are equidistributed, by constructing two involutions on permutations. As an application we confirm four conjectures raised by Kitaev and Zhang recently.
Based on joint work with Jiang Zeng.
Given a d-dimensional polytope P, its realization space consists of all d-polytopes that have the same combinatorial type as P. For instance, consider the realization space of the d-simplex: since the d-simplex is projectively unique (i.e., any d-simplex can be transformed into any other d-simplex by a projective transformation) the realization space of the d-simplex is connected (and in fact, contractible). As a consequence, any two simplicial d-polytopes, after applying an appropriate projective transformation to one of them, can be glued along a facet to produce a convex polytope. This realizes the connected sum operation for simplicial polytopes geometrically.
We consider the realization space of the d-cube. The d-cube is not projectively unique for 
Based on joint work with Karim Adiprasito and Eran Nevo.
In this talk we study a natural generalization of the classical epsilon-net problem (Haussler-Welzl 1987), which we call 'the epsilon-t-net problem': Given a hypergraph on n vertices and parameters t and epsilon, find a minimum-sized family S of t-element subsets of vertices such that each hyperedge of size at least epsilon n contains a set in 
We prove that any sufficiently large hypergraph with VC-dimension d admits an epsilon-
Joint work with Noga Alon, Bruno Jartoux, Shakhar Smorodinsky and Yelena Yuditsky.
Given a word w in the free group on k generators, the word measure induced by w on the symmetric group S_n is the distribution obtained when substituting k independent uniform permutations into the word w. Puder and Parzanchevski (2015) estimated the expected number of fixed points of a permutation sampled according to this distribution.
We generalize this result to other statistics of the permutation, such as the expected number of cycles of a constant length, or the expected number of pairs of fixed points. As an application of these results, we prove results regarding the expansion of random Schreier graphs of the symmetric group.
Based on joint work with Doron Puder.
Since the celebrated work of Guth and Katz on the Erdos distinct distances problem, polynomial partitioning became a central tool in solving incidence problems, as well as other main problems in discrete geometry. In spite of this progress, the application of polynomial partitioning in solving computational problems received considerably less attention. In particular, except for special settings (such as points in d-space), it is currently unknown how to efficiently construct partitioning polynomials for arbitrary semi-algebraic sets.
In this talk I will present an efficient construction of such partitioning polynomials based on quantifier elimination and epsilon-approximations.
This talk is based on joint work with Pankaj Agarwal, Boris Aronov, and Joshua Zahl.
An element of a Coxeter group W is fully commutative if any two of its reduced decompositions are related by a series of transpositions of adjacent commuting generators. These elements were extensively studied by Stembridge, in the finite case. They index naturally a basis of the generalized Temperley–Lieb algebra of W.
In this talk, we give explicit descriptions of fully commutative elements when W is an affine Coxeter group. Using our characterizations we then enumerate these elements according to their Coxeter length, and we show that the corresponding generating function is ultimately periodic in each type.
Based on joint work with F. Jouhet and P. Nadeau.
Let G be an n-vertex oriented graph. Let t(G) (respectively i(G)) be the probability that a random set of 3 vertices of G spans a transitive triangle (respectively an independent set). We prove that t(G) + i(G) is asymptotically at least 1/9. We also prove a stability result and an exact result. Namely, we describe an extremal construction, prove that it is essentially unique, and prove that if H is sufficiently far from that construction, then t(H) + i(H) is significantly larger than 1/9. The proof of the asymptotic result uses the method of flag algebras. I will try to use this result to explain (in some detail) how this method works.
Based on joint work with Shoni Gilboa, Roman Glebov, Nati Linial and Avraham Morgenstern.
The random greedy algorithm for finding a maximal independent set in a graph
has been studied extensively in various settings in combinatorics, probability,
computer science — and even in chemistry. The algorithm builds a maximal
independent set by inspecting the vertices of the graph one at a time according
to a random order, adding the current vertex to the independent set if it is
not connected to any previously added vertex by an edge.
In this talk I will present a natural and general framework for calculating the
asymptotics of the proportion of the yielded independent set for sequences of
(possibly random) graphs, involving a useful notion of local convergence. We
use this framework both to give short and simple proofs for results on
previously studied families of graphs, such as paths and binomial random
graphs, and to give new results for other models such as random trees.
If time allows, I will discuss a more delicate result, according to which in
expectation, the cardinality of a random greedy independent set in the path is
no larger than that in any other tree of the same order.
The talk is based on joint work with Michael Krivelevich, Tamás Mészáros and
Clara Shikhelman.
Let G be a finite group. Every word w in the free group on, say, 2 generators x and y, induces a probability measure on G as follows: sample two uniformly random elements g and h from G and evaluate w(g,h) to get an element of G. For example, if w = xyxy^{-2}, one obtains the random element ghgh^{-2} in G. The study of word measures on groups has revealed a lot of beautiful structure with surprising connections to other fields of mathematics, and has shed light on the finite group G as well as on the free group.
In this talk I will survey some of what we know and some of the challenges ahead, and focus on one illustrating example.
This is based on joint works with Liam Hanany, Michael Magee, Chen Meiri, Ori Parzanchevski and Danielle West.
Let X be a simplicial complex. Given a simplex σ ∈ X of dimension at most d − 1 that is contained in a unique maximal face of X, the operation of removing σ and all the simplices that contain it from X is called an elementary d-collapse. We say that X is d-collapsible if it can be reduced to the void complex by performing a sequence of elementary d-collapses. The collapsibility of X is the minimal d such that X is d-collapsible. The notion of d-collapsibility was introduced by Wegner, who applied it in the study of intersection patterns of convex sets in R^d .
We study the collapsibility of simplicial complexes associated to different properties of graphs and hypergraphs, and present several topological and combinatorial applications. We discuss some of the tools that we use for bounding the collapsibility of a complex. In particular, we present a useful and easy to apply bound, generalizing a method due to Matoušek and Tancer.
The talk is partly based on joint work with Minki Kim.
We are given a 2-coloring of the edges of the complete graph. If the number of red edges in triangles is almost always even, then the coloring is approximately defined on vertices. Thus triangles "test" a function on edges to be defined from the vertices.
Replacing triangles by squares, and going up in the dimension, we show that differentials can test properties, as long as the cohomology group is sufficiently well understood.
Joint work with David Garber.
In 1974 Rick Wilson proved one of the most important theorems on combinatorial structures in the 20th century by showing that the easy necessary conditions on the parameters of a block design are eventually sufficient. The proof involves morphisms between block designs whose fibers allow for recursive constructions. The self-maps of a design form a monoid that are a fundamental part of the theory of designs. The algebraic properties of this monoid have not been explored up to now and the purpose of this talk is to do just that. We give a beautiful connection between semigroups, groups designs and incidence geometry.
No background in either design theory or semigroup theory is required for the talk. This is joint work with John Rhodes and Pedro Silva.
The goal of my second talk on the subject (the first one was given at this seminar two years ago), which is also based on joint work with Vladimir Retakh, is twofold:
First, I will recall motivations, definition and basic properties of noncommutative Catalan numbers C_n, which belong to the free Laurent polynomial algebra in x_0,...,x_n. They admit interesting (commutative and noncommutative) specializations, one of them related to the Garsia-Haiman (q,t)-version Catalan numbers, another -- to solving noncommutative quadratic equations. We also established total positivity of the corresponding (noncommutative) Hankel matrices H_n and introduced two kinds of noncommutative binomial coefficients which are instrumental in computing the inverse of H_n, its positive factorizations, and other combinatorial identities involving C_n.
Second, I will outline a relationship of the C_n with (noncommutative) orthogonal polynomials, which can be viewed as "characteristic polynomials" of an extended version of the matrices H_n or of the corresponding noncommutative Jacobi matrices J_n.
We say that a family F of k-element sets is a j-junta if there is a set J of size j such that, for any set, its presence in F depends on its intersection with J only. Approximating arbitrary families by j-juntas with small j is a recent powerful technique in extremal set theory.
The weak point of all known approximation by juntas results is that they work in the range n>Ck, where C is an extremely fast growing function of the input parameters. In this talk, we present a simple and essentially best possible junta approximation result for an important class of families, called shifted. As an application, we present some progress in the question of Aharoni and Howard on families with no cross-matching.
Joint work with Peter Frankl.
Several items have to be allocated among several families. In each family, there are members with different preferences over the items. The goal is to divide the items such that, in each family, as many members as possible will perceive the division as "fair".
I will show that this problem combines two seemingly-unrelated problems: fair allocation of items among individuals, and finding winning-strategies in combinatorial games. I will present division algorithms, upper bounds and some open questions.
Joint work with Warut Suksompong (Oxford University).
Full paper: https://arxiv.org/abs/1709.02564
Erdos and Purdy conjectured that for n \geq 5 one cannot find a set of n red points in general position and another set of n-1 blue points such that every line determined by two red points passes also through a blue point. This conjecture is trivially true for n odd, but turns to be very challenging for n even. The conjecture is, in fact, a special (but important) case of the Magic Configuration conjecture of Murty from 1971. The conjecture of Murty was proved in 2008 in a topological setting.
Here we present a purely algebraic proof of the conjecture of Erdos and Purdy. On the way we also provide a nice result on vectors in the two dimensional plane.
A map $Y: X \rightarrow \{+1, -1\}$ over a finite set $X \con R^d $ is (linearly) separable if there exists $w \in R^d$ such that $\sign(w \bigcdot x)=Y(x)$ for all $x \in X$. When the Euclidean norm of $w$ is $\|w\|=1$, the number $\marg (w,Y) = \min_{x \in X} {Y(x) w\bigcdot x }$ is the margin of $w$ with respect to $Y$. The number $\marg(Y) = \sup_{w \in R^d : \|w\|=1} \marg(w,Y)$ is the margin of $Y$. We call $Y$ an $\eps$-partition if its margin is at least $\eps$.
Given a set $X$ of size $n$, how many $\eps$ partitions exist?
To answer this question, we will use the classical perceptron algorithm (the first neural algorithm). We will also use the perceptron to prove a "sparse" version of Farkas' lemma and derive generalization bounds using sample compression schemes. If time permits, we will also discuss some open combinatorial problems in learning theory.
The degree anti-Ramsey number of a graph H is the smallest integer k for which there exists a graph G with maximum degree at most k such that any proper edge colouring of G yields a rainbow copy of H (i.e., all edges of this copy of H have distinct colours).
We determine the degree anti-Ramsey number of any tree, and then extend this to any forest using a classical result of Bollobas concerning cross intersecting families. We also use a topological version of Hall's Theorem due to Aharoni, Berger and Meshulam to get an upper bound (which is best possible up to a factor of 2) on the degree anti-Ramsey numbers of cycles of any length, .
Joint work with Danny Hefetz.
Let V be an n-dimensional space over a fixed finite field. The complex of flags X(V) is the simplicial complex whose vertices are the non-trivial linear subspaces of V, and whose simplices are ascending chains of subspaces. This complex, also known as the spherical building associated to the linear group GL(V), appears in a number of different mathematical areas, including topology, combinatorics and representation theory. After recalling the classical homological properties of X(V), we will discuss some more recent results including:
1. Minimal weight cocycles in the Lusztig-Dupont homology.
2. Coding theoretic aspects of X(V) and the existence of homological codes.
2. Coboundary expansion of X(V) and its applications.
The random Linial-Meshulam complex Y_d(n,p) is the higher-dimensional analogue of the random graph model G(n,p). In recent years, the properties of random hypergraphs and simplicial complexes have been studied intensively. In this talk, we consider the fundamental group of a random 2-dimensional simplicial complex.
Babson, Hoffman and Kahle proved that the threshold for the fundamental group to vanish, i.e. simple connectivity, is approximately p=n^(-1/2). We show that in fact this threshold is at most (c n)^(-1/2) for c=4^4/3^3, and conjecture that this is the true threshold. In fact, we prove a sharp threshold for the stronger property that every cycle is the boundary of a subcomplex of Y_2(n,p) that is homeomorphic to a sphere.
The talk is based on a joint work with Yuval Peled.
An order-$n$ Latin square is equivalent to a triangle-decomposition of the complete tripartite hypergraph $K_{n,n,n}$. Let $H \sim H_3(n,n,n;p)$ be a tripartite, balanced, binomial random $3$-uniform hypergraph on $3n$ vertices where each edge is present with probability $p$. What is the threshold $p$ for the property that $H$ contains a Latin square? The general heuristic is that spanning structures appear together with the disappearance of local obstructions. Thus the natural conjecture is $p = 2 \log(n) / n$, which corresponds to the disappearance of edges not contained in any triangle.
While this problem remains open, two natural approaches are to consider approximations of Latin squares, and to obtain (possibly suboptimal) upper bounds on the threshold probability. I will review results in both directions.
The lion's share of the talk will be spent discussing an application of Keevash's method of randomized algebraic construction to show an upper bound of $n^{-1/7+ o(1)}$ on the threshold probability.
Parts of the talk are the result of joint work with Zur Luria.
Helly's theorem is a classical result in combinatorial geometry about the intersection patterns of convex sets in Euclidean spaces. For the 2-dimensional case, it asserts that for a family of convex sets in the plane, if every 3 members have a point in common, then all members in the family have a point in common. The topological Helly theorem, also proved by Helly, shows that the same assertion holds for a family of open and contractible sets where each intersection is again open and contractible.
In this talk, I will present Helly-type theorems for a more general set-system: a family of open connected sets in the plane where any intersection is again open and connected. In this setting, if every 4 members have a point in common, then all members in the family have a point in common. I will also discuss a fractional generalization of this.
Aldous' spectral gap conjecture, proved in 2009 by Caputo, Liggett and Richthammer, states the following a priori very surprising fact: the spectral gap of a random walk on a finite graph is equal to the spectral gap of the interchange process on the same graph.
This seminal result has a very natural interpretation in Representation Theory, which leads to natural conjectural generalizations. In joint works with Gadi Kozma and Ori Parzanchevski we study some of these possible generalizations, clarify the picture in the case of normal generating sets and reach a more refined, albeit bold, conjecture.
Experimentally, the convex-layer decomposition of subsets of the integer grid ("grid peeling") seems to behave at the limit like the affine curve-shortening flow. We offer some theoretical arguments to explain this phenomenon. In particular, we derive some rigorous results for the special case of peeling the quarter-infinite grid: We prove that, in this case, the number of grid points removed up to iteration n is Theta(n^(3/2)log n), and moreover, the boundary at iteration n is sandwiched between two hyperbolas that are separated from each other by a constant factor.
Joint work with David Eppstein and Sariel Har-Peled.
In the last twenty years it has been noticed that many combinatorial and geometric structures also have the structure of a monoid. These include real and complex hyperplane arrangements, Bruhat order of Coxeter groups, Schubert cells of linear algebraic groups and more.
The representation theory of these monoids can be used to study random walks and give other information about these structures. Connections between combinatorial and geometric structures and representations of finite monoids has led to important developments in these fields.
In this talk, we look at the monoids associated to the Coxeter complex and to the Bruhat order of a Coxeter group. No previous knowledge required.
I'll describe a search game with a surprising geometric connection. A hunter and a rabbit move on an n-vertex graph without seeing each other until they meet. At each step, the hunter moves to a neighboring vertex or stays in place, while the rabbit is free to jump to any node. Thus they are engaged in a zero sum game, where the payoff is the capture time. We show that an optimal rabbit strategy for the cycle yields a Kakeya set: a plane set of zero area that contains a unit segment in every direction. Kakeya sets have been studied intensively in harmonic analysis since their discovery by Besicovitch (1919); their connection to search games is new and yields insights in both directions. (Based on joint work with Y. Babichenko, R. Peretz, P. Sousi and P. Winkler and on earlier work by Adler et al (2003).)
A braided vector space is a pair $(V, \Psi)$, where $V$ is a vector space
and $\Psi: V \otimes V \to V \otimes V$ is an invertible linear operator
such that $\Psi_1 \Psi_2 \Psi_1 = \Psi_2 \Psi_1 \Psi_2$. Given a braided
vector space $(V, \Psi)$, we constructed a family of braided vector spaces
$(V, \Psi^{(\epsilon)})$, where $\epsilon$ is a bitransitive function. Here a
bitransitive function is a function $\epsilon: [n] \times [n] \to \{1, -1\}$ such
that both of $\{(i,j) : \epsilon(i,j) = 1\}$ and $\{(i,j) : \epsilon(i,j) = -1\}$ are
transitive relations on $[n]$. The braidings $\Psi^{(\epsilon)}$ are monomials.
Therefore we call them monomial braidings.
We generalized this construction to the case of multi-colors. Given a braided
vector space $(V, \Psi)$, we used C-transitive functions to parametrize the
braidings on $V^{\otimes n}$ which come from $\Psi_1, \ldots, \Psi_{n-1}$.
Since $[n] \times [n]$ can be viewed as the set of edges of the bi-directed
complete graph with n vertices, a C-transitive function $\epsilon: [n] \times [n] \to C$
can be view as a C-transitive function on a bi-directed complete graph.
We generalized the concept of C-transitive functions to C-transitive functions on
any directed graphs. We showed that the number |\Epsilon_G(C)| of all C-transitive
functions on a directed graph G is a polynomial in |C|. This is a new invariant in graph
theory. It is analogue to the chromatic polynomial for an undirected graph in graph theory.
This talk is based on joint work with Arkady Berenstein and Jacob Greenstein.
In this talk, we will present an asymptotically tight bound on the largest number of distinct projections onto \alpha n coordinates guaranteed in any family of n^r binary vectors of length n, where 0 < \alpha \le 1 and r = n^{o(1)}, thus closing a gap open since a work of Bollobas and Radcliffe from 1995. For the proof, we establish a “sparse” version of a classical result, the Kruskal-Katona Theorem, where we give a stronger guarantee when the hypergraph does not induce dense subhypergraphs. We also present a geometric application regarding point-halfspace separation in R^d.
The talk is based on a recent joint work with Noga Alon and Guy Moshkovitz.
We say that a partition is odd if its dimension (computed by the hook-length formula) is odd. It turns out that the number a(n) of odd partitions of a positive integer is always a power of 2. This was proven independently by Macdonald and McKay. We will show that the subposet of the Young lattice consisting of odd partitions is a binary tree, and give an explicit recursive characterisation of this tree.
We say that a partition is chiral if the associated irreducible representation composed with the determinant map gives the sign character. Denote the number of chiral partitions of n by b(n). L. Solomon first considered the problem of enumeration of b(n) and Stanley posed it as an open problem in his book. We solve this problem by giving an explicit formula for b(n). We also show that the enumerations of a(n) and b(n) are closely related. The primary tool in our solution is J. Olsson's theory of core towers.
This is joint work with A. Prasad and S. Spallone.
It has been known since work of Feynman in the 50s that the behaviour of quantum systems is related to cycles of random permutations,
and for some systems this can be made a precise mathematical claim. Similar problems appear in the, mostly recreational, field of card shuffling.
All these problems can be attacked by representation theory, but algebra alone is not enough, as the functions involved are not class functions.
This creates an exciting analytic-algebraic nexus which has seen lots of progress recently, which I will survey in the talk.
No prior knowledge of any of the topics will be assumed.
We express some open problems in graph theory in terms of Ihara graph zeta
functions, or, equivalently, non-backtracking matrices of graphs. We focus
on "expanders" and random regular graphs, but touch on some seemingly
unrelated problems encoded in zeta functions.
We suggest that zeta functions of sheaves on graphs may have relevance to
complexity theory and to questions of Stark and Terras regarding whether
coverings of a fixed graph can ramify like number field extensions.
This talk assumes only basic linear algebra and graph theory. Part of the
material is joint work with David Kohler and Doron Puder.
Back in 2005, Berenstein, Fomin and Zelevinsky discovered a cluster
structure in the ring of regular functions on a double Bruhat cell in a
semisimple Lie group, in particular, SL_n. This structure can be easily
extended to the whole group. The compatible Poisson bracket is given by
the standard r-matrix Poisson-Lie structure on SL_n. The latter is a
particular case of Poisson-Lie structures corresponding to
quasi-triangular Lie bialgebras. Such structures where classified in 1982
by Belavin and Drinfeld. In 2012, we have conjectured that each
Poisson-Lie structure on SL_n gives rise to a cluster structure, and gave
several examples of exotic cluster structures corresponding to Poisson-Lie
structures distinct from the standard one. In my talk I will tell about the
progress in the proof of this conjecture and its modifications.
Joint with M.Gekhtman and M.Shapiro.
A number of methods of the algebraic graph theory were influenced by the spectral theory of Riemann surfaces.
We pay it back, and take some classical results for graphs to the continuous setting. In particular, I will talk about colorings, average distance and discrete random walks on surfaces.
Based on joint works with E. DeCorte and A. Kamber.
A flip graph is a graph, on a set of objects, in which adjacency reflects local change.
Flip graphs, from different domains, have surprising common properties, in terms of algebraic, combinatorial and metric properties.
In particular, they carry similar group actions, are intimately related to posets and have similar diameter formulas.
In this work, we introduce a new family of flip graphs, the Yoke graphs, which generalizes several formerly considered graphs --
on triangulations, permutations and trees.
Our main result is the computation of the diameter of an arbitrary Yoke graph.
At the heart of the proof lies the idea of transforming a diameter evaluation to an eccentricity problem.
This work forms part of a PhD thesis written under the supervision of Ron Adin and Yuval Roichman.
The famous Kazhdan-Lusztig conjectures, formulated in the late 1970s and proved soon after independently by Beilinson-Bernstein and Brylinski-Kashiwara,
underscore a deep relationship between representation theory, combinatorics and geometry.
Recent progress in representation theory of the general linear group over p-adic fields led us to speculate a relationship between particular cases of parabolic Kazhdan-Lusztig polynomials
(which are certain alternating sums of ordinary ones) and ordinary ones. I will discuss what is known theoretically and some empirical results.
No prior familiarity with these concepts will be assumed.
Based on joint work with Alberto Minguez.
The classical Helly's theorem, dated 1923, asserts that if F is a family of compact convex sets in R^d such that any d+1 sets of F have a non-empty intersection, then all sets of F can be pierced by a single point. Helly's theorem is a cornerstone in convexity theory, and the need to generalize and extend it has led mathematicians to deep and fascinating new research directions. One of the best-known extensions is the Alon-Kleitman (p,q) theorem (1992) which asserts that for F as above, if among any p sets of F some q intersect (for q>d), then all sets of F can be pierced by a bounded number c(p,q,d) of points.
In this talk we survey the quest for quantitative Helly-type theorems which aim at finding effective bounds on the piercing numbers in various scenarios. We present new bounds on c(p,q,d) for the Alon-Kleitman theorem, which are almost tight for a wide range of parameters. We also show that for several large classes of families, quantitative (p,2) theorems in the plane can be obtained, providing a strong connection between the piercing number of a family to its well-studied packing number, and giving rise to new Ramsey-type theorems.
Based on joint works with Shakhar Smorodinsky and Gabor Tardos.
The block number of a permutation is the maximal number of components in its expression as a direct sum.
The distribution of the set of left-to-right maxima over 321-avoiding permutations with block number k is shown to be equal to
the distribution of this set over 321-avoiding permutations with the last descent of the inverse permutation at position n - k.
This result is analogous to the classical Foata-Sch¨utzenberger equi-distribution theorem,
and implies that the quasi-symmetric generating function of descent set over 321-avoiding
permutations with a prescribed number of blocks is Schur-positive.
Joint work with Ron Adin and Yuval Roichman.
The goal of my talk (based on joint work with Vladimir Retakh) is to introduce and study noncommutative versions of Catalan numbers which belong to the free Laurent polynomial algebra L_n in n generators.
Our noncommutative Catalan numbers C_n admit interesting (commutative and noncommutative) specializations, one of them related to Garsia-Haiman (q,t)-versions, another -- to solving noncommutative
quadratic equations. We also establish total positivity of the corresponding (noncommutative) Hankel matrices H_n and introduce two kinds of noncommutative binomial coefficients which are instrumental
in computing the inverse of H_n and in other combinatorial identities involving C_n.
Let $G$ be a finite group, and let $\pi$ be a permutation from $S_n$. We study the distribution of probabilities of the equality
\[ a_1 a_2 \cdots a_n = a_{\pi_1}^{\epsilon_1} a_{\pi_2}^{\epsilon_2} \cdots a_{\pi_n}^{\epsilon_n}, \]
where $\pi$ varies over all the permutations in $S_n$, and $\epsilon_i$ varies either over the set $\{1, -1\}$ or over the set $\{1, b\}$, where $b$ is an involution in $G$ (two different cases of equations). The equation can also be written as
\[ a_1 a_2 \cdots a_n = a_{\pi_1} a_{\pi_2} \cdots a_{\pi_n}, \]
where $\pi$ is a signed permutation from $B_n$, and $a_{-i}$ is interpreted either as the inverse $a_i^{-1}$, in case $\epsilon_i \in \{1, -1\}$, or as the conjugate $b a_i b$, in case $\epsilon_i \in \{1, b\}$. The probability in the second case depends on the conjugacy class of the involution $b$.
First we consider the case in which all $\epsilon_i$ are $1$. It turns out that the probability, for a permutation $\pi$, depends only on the number of alternating cycles in the cycle graph of $\pi$, introduced by Bafna and Pevzner in 1998. We describe the spectrum of probabilities of permutation equalities in a finite group as $\pi$ varies over all permutations in $S_n$. We then generalize, letting a signed permutation vary over all the signed permutations in $B_n$, under the two interpretations outlined above. The spectrum turns out to be closely related to the partition of the number $2^{n}\cdot n!$ into a sum of the corresponding signed Hultman numbers (defined by Grusea and Labbare) when $\epsilon_i \in \{1, -1\}$, or into edge-signed Hultman numbers (introduced in this talk) when $\epsilon_i \in \{1, b\}$.
We introduce the notion of "one-sided epsilon-approximants", which is in strength between epsilon-nets and usual (two-sided) epsilon-approximants. Given an n-point set P in R^d, a one-sided epsilon-approximant for P (with respect to convex sets) is a multiset A such that, for every convex set C, we have |P cap C|/|P| - |A cap C|/|A| <= epsilon.
We show that, in contrast with the usual epsilon-approximants, every P has a one-sided epsilon-approximant with respect to convex sets of size g(eps, d) for some g, but independent of n.
Unfortunately, due to the use of a geometric Ramsey theorem, our bound is very weak: g(eps, d) <= 2^2^...^2^(1/epsilon)^c, with d-1 2's.
For more info, see arXiv:1603.05717
Joint work with Boris Bukh.
Hadwiger and Debrunner themselves showed that if q is very close to p, then C=p-q+1 suffices. The proof of Alon and Kleitman yields a huge bound C=O(p^{d^2+d}), and providing sharp upper bounds on the minimal possible C remains a wide open problem.
In this talk we show an improvement of the best known bound on C for all pairs (p,q). In particular, for a wide range of values of q, we reduce C all the way to the almost optimal bound p-q+1<=C<=p-q+2. This is the first near tight estimate of C since the 1957 Hadwiger-Debrunner theorem.
Joint work with Shakhar Smorodinsky and Gabor Tardos.
We show that for any rational polygon P in the plane, and any odd-sized collection of translates of P, the area of the set of points covered by an odd number of these translates is bounded away from 0 by a universal constant depending on P alone.
The key ingredient of the proof is a construction of an odd cover of the plane by translates of P. That is, we establish a family of translates of P covering (almost) every point in the plane a uniformly bounded odd number of times.
Joint work with Rom Pinchasi.
We introduce a new model for random knots and links, based on the petal projection developed by C. Adams et al. We study the distribution of various invariants of knots and links in this model. We view a knot invariant as a random variable on the set of all petal diagrams with n petals, and ask for its limiting distribution as n --> infinity. We obtain a formula for the limiting distribution of the linking number of a random two-component link. We obtain formulas for all moments of the two most basic Vassiliev invariants of knots, which are related to the Conway polynomial and the Jones polynomial. These are the first precise formulas given for the distributions or moments of invariants in any model for random knots and links.
Joint work with Chaim Even-Zohar, Joel Hass, and Nati Linial.
We discuss a generalization of k-suitable permutations, defined in 1950 by Dushnik in the context of the order dimension of the boolean lattice.
We relate suitable digraphs to communication settings and prove lower and upper bounds on the cardinality of families of (k,l)-suitable digraphs.
Joint work with Elad Haramaty, Aaron Potechin and Madhu Sudan.
The uncertainty principle in the n-dimensional hypercube states that if a non-zero function is supported in A and its Fourier transform is supported in B, then |A||B| is at least 2^n.
We consider a relaxed version, requiring only a non-negligible fraction of the l_2 norm of the function to be attained in A and of its transform in B. Provided either A or B is a Hamming ball, we give a description of the possible joint behavior of |A| and |B|. This description is tight on the exponential scale (that is, assuming both A and B are exponentially small). The main technical tool we use is a stronger version of the hypercontractive inequality for functions with exponentially small support.
As a corollary we show that any binary linear code contains "many" (in the appropriate sense) codewords whose length is close to that guaranteed by the linear programming bound.
Joint work with Yury Polyanskiy.
It is shown that for any fixed c \geq 3 and r, the maximum possible chromatic number of a graph on n vertices in which every subgraph of radius at most r is c-colorable is n^(1/r+1) up to a multiplicative factor logarithmic in n: in fact, it is O((n/log(n)) ^ (1/r+1)) and Omega(n^(1/r+1) / log(n)).
The proof is based on a careful analysis of the local and global colorability of random graphs and implies, in particular, that a random n-vertex graph with the right edge probability has typically a chromatic number as above and yet most balls of radius r in it are 2-degenerate.
Joint work with Noga Alon.
For a graph on $n$ vertices, and an integer $D$, let the $D$-local view of $G=(V,E)$ be the collection (multiset) of the unlabelled $n$ balls of distance $D$ around the vertices.
The main question that motivates this study is: what can be said about $G$ knowing only its $D$-local view for some constant $D$.
For constant bounded degree planar (or more generally hyperfinite) graphs, Newman-Sohler [2011] following a long sequence of work, show that for any $\epsilon > 0$, there is a $D$ such that the $D$-local view of the graph determines the graph up to the deletion / insertion of at most $\epsilon n$ edges. This in turn, implies that every property of planar (hyperfinite) graphs can be tested (in the sense of property testing, by constantly many queries.
What happens in non-bounded degree planar graphs? The answer is currently still open. However, we show, following Yoshida's results on forests, that the above phenomenon still holds for outerplanar graphs. The implication to testing is deteriorated, though. Testing now requires $O(poly(\log n))$ queries.
I will describe the ideas behind the two results, the later which is a joint work with Jasine Babu and Areej Khoury.
Ramanujan graphs, constructed by Lubotzky, Phillips and Sarnak and known also as the LPS graphs, are certain quotients of the Bruhat-Tits building of PGL_2(Q_p). These graphs form a family of expander graphs, and serve as an explicit construction of graphs of high girth and large chromatic number. High dimensional counterparts of the LPS graphs are the Ramanujan Complexes, constructed by Lubotzky, Samuels and Vishne, as quotients of the Bruhat-Tits building of PGL_d over a non-archimedean field of finite characteristic. I'll talk about the mixing of these complexes, which implies that they have good expansion and large chromatic number.
If time permits, I'll talk about analogous results for general hypergraphs satisfying certain regularity condition.
Joint work with S.Evra, A.Lubotzky.
May the same graph admit two different chromatic numbers in two different universes? how about infinitely many different values? and can this be achieved without changing the cardinals structure?
The key concept of our discussion is that of a perfect matching (PM) in a bipartite graph. The expansion condition in Hall's marriage theorem can be extended to an unbiased 2-sided one. This enables an alternative (and simpler) proof of Evans' (proven) Conjecture:
A partial nxn Latin square with n-1 dictated entries admits a completion to a full Latin square.
PMs are used to successively fill the square by rows, columns or diagonals. Latin square tables correspond to quasi-groups; the ones corresponding to groups are only a tiny fraction of them, as n grows. However, for Sudoku tables of order mnxmn, the completion (say by diagonals) usually fails, even if there are no dictated entries, unless they are conjugates of a twisted product of two groups, of orders n and m.
An open problem for sudoku lovers: Is there a sudoku square (of any order) which is not a conjugate of a twisted product of groups?
No prior knowledge needed.
A normally regular digraph with parameters (v,k,λ,μ) is a directed graph with adjacency matrix A satisfying the equation AAT=kI+λ(A+AT) +μ(J-I-A-AT). I.e., the number of common out-neighbours of vertices x and y is k if x=y, μ if x and y are non-adjacent, λ if x and y are adjacent in one direction and 2λ-μ if they are adjacent in both directions.
The adjacency matrix of a normally regular graph is normal, and all eigenvalues other than k are on one circle in the complex plane. This property characterizes normally regular digraphs.
We consider constructions and structural characterizations and we also consider connections to association schemes, symmetric 2-designs, generalized difference sets, and partition of a projective plane into subplanes.
The (still open) problem of determining the diameter of this graph is a trigger for an exciting tour through
reduced words of a Coxeter element in the symmetric group, a 0-Hecke algebra action, a special EL-labeling, q,t-Catalan numbers, and non-crossing alternating trees.
Joint work with Yuval Roichman.
Erdos-Ko-Rado (EKR) type theorems yield upper bounds on the size of set families under various intersection requirements on the elements. Stability versions of such theorems assert that if the size of a family is close to the maximum possible then the family itself must be close (in appropriate sense) to a maximum family.
Joint work with David Ellis and Nathan Keller.
The branching rules for representations of the symmetric group are one of the gems of representation theory. In this talk we will give a natural generalization of some branching rules to the case of a wreath product of a finite group with the symmetric group.
The rules we will generalize are the Littlewood-Richardson rule and the "classical" rules for inducting from S_{n} to S_{n+1} and restricting from S_{n+1} to S_{n}. If time allows we will give an application to the quiver computation of a natural family of categor algebras.
The goal of my talk (based on joint work with Dima Grigoriev, Anatol Kirillov, and Gleb Koshevoy) is to generalize the celebrated Robinson-Schensted-Knuth (RSK) bijection between the set of matrices with nonnegative integer entries, and the set of the planar partitions.
Namely, for any pair of injective valuations on an integral domain we construct a canonical bijection K, which we call the generalized RSK, between the images of the valuations, i.e., between certain ordered abelian monoids.
Given a semisimple or Kac-Moody group, for each reduced word ii=(i_1,...,i_m) for a Weyl group element we produce a pair of injective valuations on C[x_1,...,x_m] and argue that the corresponding bijection K=K_ii, which maps the lattice points of the positive octant onto the lattice points of a convex polyhedral cone in R^m, is the most natural generalization of the classical RSK and, moreover, K_ii can be viewed as a bijection between Lusztig and Kashiwara parametrizations of the dual canonical basis in the corresponding quantum Schubert cell.
Generalized RSKs are abundant in ``nature", for instance, any pair of polynomial maps phi,psi:C^m-->C^m with dense images determines a pair of injective valuations on C[x_1,...,x_n] and thus defines a generalized RSK bijection K_{phi,psi} between two sub-monoids of Z_+^m.
When phi and psi are birational isomorphisms, we expect that K_{phi,psi} has a geometric ``mirror image", i.e., that there is a rational function f on C^m whose poles complement the image of phi and psi so that the tropicalization of the composition psi^{-1}phi along f equals to K_{phi,psi}. We refer to such a geometric data as a (generalized) geometric RSK, and view f as a ``super-potential." This fully applies to each ii-RSK situation, and we find a super-potential f=f_ii which helps to compute K_ii.
While each K_ii has a ``crystal" flavor, its geometric (and mirror) counterpart f_ii emerges from the cluster twist of the relevant double Bruhat cell studied by Andrei Zelevinsky, David Kazhdan, and myself.
We provide tight lower and upper bound theorems for these polytopes as functions of $d,n$ and $s$, thus generalizing the classical Lower Bound Theorem by Barnette and Upper Bound Theorem by McMullen, which treat the case $s=0$. We characterize the minimizers and provide examples of maximizers, for any $d$.
Time permitting, I'll also discuss results on reconstruction problems for these and for related polytopes.
On page 155 of [Graham, Knuth and Patashnik] it says:
The numbers in Pascal's triangle satisfy, practically speaking, infinitely many identities,
so it is not surprising that we can find some surprising relationships by looking closely.
By proving some surprising identities in character tables of S_n we shall indicate that a
similar statement seem to hold for the S_n character tables .
Joint work with D. Zeilberger
In this talk we study short edge-disjoint paths in expander graphs(here it mean: graph with constant mixing time). We use the Lovasz Local Lemma to prove the following result: Given a d-regular expander graph G and a set L={(s_i,t_i)} such that each vertex of G appears at most O(d) times in the list, there exist a set of edge disjoint paths of constant length connecting each s_i to t_i. This result has applications to multiparty computation performed over networks in the presence of random noise.
Characterizing sets of permutations whose associated quasi-symmetric function is symmetric and Schur-positive is a long-standing problem in algebraic combinatorics. We will explain the significance of the problem and describe recent progress.
A general method to construct Schur-positive sets and multisets, based on pattern avoidance and geometric grids will be presented. This approach produces many new instances of Schur-positive sets, and provides a broad framework that explains the existence of known such sets that until now were sporadic cases.
Joint with Sergi Elizalde.
The classical correlation inequality of Harris asserts that any two monotone increasing families on the discrete cube are nonnegatively correlated. In 1996, Talagrand established a lower bound on the correlation in terms of how much the two families depend simultaneously on the same coordinates. Talagrand's method and results inspired a number of important works in combinatorics and probability theory.
In this talk we present stronger correlation lower bounds that hold when the increasing families satisfy natural regularity or symmetry conditions. In addition, we present several new classes of examples for which Talagrand's bound is tight.
A central tool we use is a simple lemma asserting that for monotone events noise decreases correlation. This lemma gives also a very simple derivation of the classical FKG inequality for product measures, and leads to a simplification of part of Talagrand's proof.
Joint work with Gil Kalai and Elchanan Mossel
We study the maximum possible sign rank of $N \times N$ sign matrices with a given VC dimension $d$. For $d=1$, this maximum is $3$. For $d=2$, this maximum is $\tilde{\Theta}(N^{1/2})$. Similar (slightly less accurate) statements hold for $d>2$ as well. We discuss the tightness of our methods, and describe connections to combinatorics, communication complexity and learning theory.
We also provide explicit examples of matrices with low VC dimension and high sign rank. Let $A$ be the $N \times N$ point-hyperplane incidence matrix of a finite projective geometry with order $n \geq 3$ and dimension $d \geq 2$. The VC dimension of $A$ is $d$, and we prove that its sign rank is larger than $N^{\frac{1}{2}-\frac{1}{2d}}$. The large sign rank of $A$ demonstrates yet another difference between finite and real geometries.
To analyze the sign rank of $A$, we introduce a connection between sign rank and spectral gaps, which may be of independent interest. Consider the $N \times N$ adjacency matrix of a $\Delta$-regular graph with a second eigenvalue (in absolute value) $\lambda$ and $\Delta \leq N/2$. We show that the sign rank of the signed version of this matrix is at least $\Delta/\lambda$. A similar statement holds for all regular (not necessarily symmetric) sign matrices. We also describe limitations of this approach, in the spirit of the Alon-Boppana theorem.
Joint work with Noga Alon and Amir Yehudayoff.
We discuss arrangements of equal minors in totally positive matrices. More precisely, we would like to investigate the structure of possible equalities and inequalities between the minors. We show that arrangements of equals minors of largest value are in bijection with sorted sets, which earlier appeared in the context of alcoved polytopes and Grobner bases. Maximal arrangements of this form correspond to simplices of the alcoved triangulation of the hypersimplex; and the number of such arrangements equals the Eulerian number. On the other hand, we conjecture and prove in many cases that arrangements of equal minors of smallest value are exactly the weakly separated sets. Weakly separated sets, originally introduced by Leclerc and Zelevinsky, are closely related to the positive Grassmannian and the associated cluster algebra.
This is a joint work with Alexander Postnikov.
Expander graphs have been intensively studied in the last four decades. In recent years a high dimensional theory of expanders has emerged. In this talk I will introduce the notion of high dimensional expanders and some of the motivations for studying them. As opposed to (1-dimensional) expanders, where a random bounded degree graph is an expander, a probabilistic construction of a bounded degree high dimensional expander is not known. A major open problem, formulated by Gromov, is whether *bounded degree* high dimensional expanders could exist for dimension d >= 2. I will discuss a recent construction of explicit bounded degree 2-dimensional expanders, that answer Gromov's question in the affirmative.
Joint work with David Kazhdan and Alexander Lubotzky.
We provide a simple proof of the Rota--Heron--Welsh conjecture for matroids realizable as c-arrangements in the sense of Goresky--MacPherson: we prove that the coefficients of the characteristic polynomial of the associated matroids form log-concave sequences, proving the conjecture for a family of matroids out of reach for all previous methods.
To this end, we study the L\'evy--Milman measure concentration phenomenon on natural push-forwards of uniform measures on the Grassmannian to realization spaces of arrangements under a certain extension procedure on matroids.
It is well-known that the G(n,p) model of random graphs undergoes a dramatic change around p=1/n. It is here that the random graph is, almost surely, no longer a forest, and here it first acquires a giant connected component. Several years ago, Linial and Meshulam have introduced the X_d(n,p) model, a probability space of n-vertex d-dimensional simplicial complexes, where X_1(n,p) coincides with G(n,p). Within this model we prove a natural d-dimensional analog of these graph theoretic phenomena. Specifically, we determine the exact threshold for the nonvanishing of the real d-th homology of complexes from X_d(n,p), and show that it is strictly greater than the threshold of d-collapsibility. In addition, we compute the real Betti numbers, i.e. the dimension of the homology groups, of X_d(n,p) for p=c/n. Finally, we establish the emergence of giant shadow at this threshold. (For d=1 a giant shadow and a giant component are equivalent). Unlike the case for graphs, for d > 1 the emergence of the giant shadow is a first order phase transition.
The talk will contain the necessary toplogical backgorund on simplicial complexes, and will focus on the main idea of the proof: the local weak limit of random simplicial complexes and its role in the analysis of phase transitions.
Joint work with Nati Linial.
For two graphs T and H and an integer n, let ex(n, T, H) denote the maximum possible number of copies of T in an H-free graph on n vertices. The study of this function when T = K_2 (a single edge) is one of the main subjects of extremal graph theory. We investigate the general function, focusing on the case T = K_3, which reveals several interesting phenomena.
The last statement improves (slightly) a result of Bollobas and Gyori.
Joint work with Noga Alon.
The influence of the $k$-th coordinate on a Boolean function $f$ measures how likely is $f(x)$ to change when the $k$-th coordinate of $x$ is flipped while the other coordinates remain unchanged. Influences were studied extensively in the last 25 years, and they have applications to theoretical computer science, mathematical physics, and various other fields.
In this talk we consider bounded functions on the discrete cube, i.e., $f:{-1,1}^n -> [-1,1]$. In this case, one of the natural definitions of influence is the $L_1$ influence, defined as $I_k(f)=E[ |f(x)-f(x+e_k)| ]$. We study the following question, raised by Aaronson and Ambainis in the context of quantum computation. Assume that $f$ has degree $d$ as a multilinear polynomial. Is it true that the sum of $L_1$ influences of $f$ can be bounded as a function of $d$ (independent of $n$)?
In a recent paper, Backurs and Bavarian showed an upper bound of $O(d^3)$ for general functions and $O(d^2)$ for homogeneous functions. We improve the upper bounds to $d^2$ for general functions and $O(d \log d)$ for homogeneous functions. Furthermore, we present an upper bound of $d / 2\pi$ for monotone functions and show that it is tight. Our proofs use tools from approximation theory, such as Bernstein-Markov type inequalities.
Joint work with Yuval Filmus (IAS), Hamed Hatami (McGill), and Nathan Keller.
A $d$-interval hypergraph consists of edges that are each the union of $d$ closed intervals on the real line. Kaiser showed that the ratio between the covering number and the matching number in such hypergraphs is bounded by $d^2-d+1$. I will present some new results regarding the weighted and fractional versions of this theorem, and examples for their sharpness. To this end I will describe a weighted version of Tur\'{a}n's theorem. I will also discuss an extension of the KKM theorem (due to Shapley) and use it to give a straightforward proof to Kaiser's theorem.
Joint work with R. Aharoni and T. Kaiser.
Ramsey's theorem states that for every symmetric partition of the square X2 of an infinite set X into finitely many cells, there would be a cell that covers the square Y2 of some infinite subset Y of X. Erdos and his collaborators considered various generalization of Ramsey's statement (replacing "infinite" with "uncountable", "finitely many" with "countably many", "square" with "rectangle"), and demonstraed the (consistent) failure of many of them. In this talk, we shall present this line of research, with the goal of elucidating the difference between rectangles and squares.
The theory of positional games is a branch of combinatorics,
whose main aim is to develop systematically an extensive
mathematical basis for a variety of two player perfect
information games, ranging from such commonly popular games as
Tic-Tac-Toe and Hex to purely abstract games played on graphs
and hypergraphs.
In this talk I will survey basic notions and concepts of
positional games and some recent developments in the field,
putting an emphasis on interconnections between positional games
and other branches of mathematics and computer science, in
particular probabilistic considerations.
Association schemes are one of the traditional areas of investigation in algebraic graph theory.
Catalogues of all association schemes are available from the website of Hanaki and Miyamoto. It is known that all association schemes of order up to 14 are Schurian, that is they are coming from suitable transitive permutation groups in the standard manner. First examples of non-Schurian association schemes exist on 15, 16 and 18 vertices. In particular, there are just two classes of non-Schurian association schemes of order 18.
Starting from successful computer free interpretations of these two examples, and using extensive computer algebra experiments in conjunction with further reasoning, we were able to observe the existence of at least four infinite families of non-Schurian association schemes of order 2p^2 (for p prime, p>3).
This is joint work with M. Klin.
In this talk we consider Maker-Breaker games played on random boards. Given a graph G=(V,E) and a graph property P, the Maker-Breaker game P played on G is defined as follows. In every round Maker and Breaker alternately claim free edges from E. Maker wins this game as soon as his graph possesses P. Otherwise, Breaker wins the game.
We consider the perfect matching, hamiltonicity and k-connectivity games played on a sparse random board G(n,p), p>=polylog(n)/n. It is clear that Maker needs at least n/2, n, kn/2 moves to win these games, respectively. We prove that G(n,p) is typically such that Maker has a strategy to win
within n/2+o(n), n+o(n), kn/2+o(n) moves, respectively. We also show a connection between fast strategies in Maker-Breaker games (weak games) and Maker-Maker games (strong games).
Joint work with Dennis Clemens, Anita Liebenau and Michael Krivelevich.
Note: The talk will be given in Hebrew.
For a set P of points in the plane, the Simple Spanning Tree (SST) graph on P, denoted by G(P), is a graph whose "vertices" are simple (i.e., non-crossing) trees whose set of vertices is P, such that two trees are connected by an "edge" if their symmetric difference contains only two edges.
In this talk we would like to characterize the center of G(P). It turns out that the center of G(P) is related to the notion of a blocker for SSTs, defined as a set of edges which has at least one edge in common with any SST on P.
First, we give a complete characterization of the blockers which are smallest w.r.t. the number of edges. Concretely, we show that these are either stars (i.e., trees of diameter 2) or special structures called "caterpillars", that were first studied by Harary and Schwenk in 1971, and appear in diverse applications in graph theory.
Then we use the minimal blockers to give an almost complete characterization of the center of G(P). We show that all the elements of the center are minimal blockers, and that all the "caterpillar" minimal blockers are elements of the center. Thus, the only remaining case is the stars, for which we show that some are elements of the center, while others are not.
Based on joint works with Micha Perles, Eduardo Rivera-Campo, and Virginia Urrutia-Galicia.
A knot is a circle embedded in three-space, but we immediately translate it into a bipartite graph Gamma following previous work of the author. We consider the graph G of perfect matchings of this graph Gamma, providing a combinatorial formula for the width of G. We present several properties of Gamma and construct a partition of its vertices into cycles that relate directly to G.
This work was inspired by a seminar talk by Roy Ben-Ari on part of his Masters thesis under the supervision of Ron Adin and Yuval Roichman.
This is joint work with Mina Teicher.
Coherent configurations (CC's), in the sense of D.G. Higman, play a central role in algebraic graph theory. They capture some of the combinatorial properties of permutation groups. However in contrast to other combinatorial structures, no catalogue of such configurations of small order exists. Our long term goal is to fill this gap.
We can classify coherent configurations according to the number of fibers (a combinatorial analogue of orbits of permutation groups). CC's with one fiber are actually association schemes, and for this type of structure a catalogue exists, see http://kissme.shinshu-u.ac.jp/as/.
It is natural to consider CC's with two fibers next.
One particular case of two-fiber CC's is equivalent to strongly regular designs (SRD's), a class of block designs introduced by Higman in 1988. While Higman originally was interested only in structures with primitive point and block graphs, we consider also the imprimitive case. We will
describe our approach to construct all small SRD's and will consider a list of feasible parameter sets that we generated. Then we will give two examples: A classical object (Reye's configuration, discovered in 1882) in a new disguise, and a new object, namely the smallest non-Schurian
SRD with 8 points and 12 blocks.
This is a joint project with Mikhail Klin.
Hindman's Theorem asserts that, for each finite coloring of $\N$, there are distinct $a_1, a_2, \dots \in \N$ such that all sums $a_{i_1} + a_{i_2} + \dots + a_{i_m}$ ($m \ge 1$, $i_1 < i_2 < \dots < i_m$) have the same color. Shevrin's classification of semigroups and a proof of Hindman's Theorem, due to Galvin and Glazer, imply together that, for each infinite semigroup $S$, there are distinct $a_1, a_2, \dots \in S$ such that all but finitely many of the products $a_{i_1}a_{i_2}\cdots a_{i_m}$ ($m \ge 1$, $i_1 < i_2 < \dots < i_m$) have the same color.
Using these methods, we characterize the semigroups $S$ such that, for each finite coloring of $S$, there is an infinite subsemigroup $T$ of $S$, such that all but finitely many members of $T$ have the same color.
Simple proofs. No background is needed.
Joint work with Boaz Tsaban.
The flag f-vector is a basic invariant of finite graded posets, counting chains according to the set of ranks they occupy. For Eulerian posets it is efficiently encoded by the cd-index, a noncommutative polynomial in variables $c$ and $d$ with integer coefficients. Moreover, if the poset is Gorenstien*, in particular if the order complex of its proper part is topologically a sphere, then Karu proved Stanley's conjecture that all the coefficients of the cd-index are nonnegative. What more can be said about the cd-index of Gorenstein* posets? Upper bounds? A characterization?
We characterize the cd-index for rank 5 (lower ranks are easy, rank 5 corresponds to 3-dimensional spheres), obtain upper bounds for certain coefficients in all ranks, and conjecture further upper bounds for the entire cd-index.
Reflects joint with Satoshi Murai.
All needed background will be given in the talk!
A 1-factorization of the complete graph Kn is a partition of its edges into n-1 perfect matchings. A Steiner triple system on [n] = {1,...,n} is a collection T of triples such that each pair in [n] is contained in a unique triple.
We will discuss the connections between these (and other) objects, and present previously known bounds on their number. We'll prove that the number of 1-factorizations of Kn is at most ((1+o(1)) n/e^2)^(n^2/2) and that the number of Steiner triple systems on [n] is at most ((1+o(1)) n/e^2)^(n^2/6).
The proofs make use of information entropy.
Joint work with Nati Linial.
