Extremal functions of forbidden multidimensional matrices

Pattern avoidance is a central topic in graph theory and combinatorics. Pattern avoidance in matrices has applications in computer science and engineering, such as robot motion planning and VLSI circuit design. A $d$-dimensional zero–one matrix $A$ avoids another$d$-dimensional zero–one matrix $P$ if no submatrix of $A$ can be transformed to $P$ by changing some ones to zeros. A fundamental problem is to study the maximum number of nonzero entries in a $d$-dimensional $n\times ?\times n$ matrix that avoids $P$. This maximum number, denoted by $f(n,P,d)$, is called the extremal function.We advance the extremal theory of matrices in two directions. The methods that we use come from combinatorics, probability, and analysis. Firstly, we obtain non-trivial lower and upper bounds on $f(n,P,d)$ when $n$ is large for every $d$-dimensional block permutation matrix $P$. We establish the tight bound $\Theta \left(n^{d?1}\right)$ on $f(n,P,d)$ for every $d$-dimensional tuple permutation matrix $P$. This tight bound has the lowest possible order that an extremal function of a nontrivial matrix can ever achieve. Secondly, we show that the limit inferior of the sequence $\left\{\frac{f(n,P,d)}{n^{d?1}}\right\}$ has a lower bound $2^{\Omega \left(k^{1∕2}\right)}$ for a family of $k\times ?\times k$ permutation matrices $P$. We also improve the upper bound on the limit superior from $2^{O(klogk)}$ to $2^{O\left(k\right)}$ for all $k\times ?\times k$ permutation matrices and show that the new upper bound also holds for tuple permutation matrices.     

Chained permutations and alternating sign matrices—Inspired by three-person chess

We define and enumerate two new two-parameter permutation families, namely, placements of a maximum number of non-attacking rooks on $k$ chained-together $n\times n$ chessboards, in either a circular or linear configuration. The linear case with $k=1$ corresponds to standard permutations of $n$, and the circular case with $n=4$ and $k=6$ corresponds to a three-person chessboard. We give bijections of these rook placements to matrix form, one-line notation, and matchings on certain graphs. Finally, we define chained linear and circular alternating sign matrices, enumerate them for certain values of $n$ and $k$, and give bijections to analogues of monotone triangles, square ice configurations, and fully-packed loop configurations.     

Minorations non triviales du plus petit commun multiple de certaines suites finies d'entiers

We present here a method which allows to derive a nontrivial lower bounds for the least common multiple of some finite sequences of integers. We obtain efficient lower bounds (which in a way are optimal) for the arithmetical progressions and lower bounds less efficient (but nontrivial) for some class of quadratic sequences.In the last part of this Note, we study the integer $\mathrm{lcm}(n,n+1,\dots ,n+k)$ ($k\in \mathbb{N},n\in {\mathbb{N}}^1$). We show that it has a divisor $d_{n,k}$ simple in its dependence on n and k, and a multiple $m_{n,k}$ also simple in its dependence on n. In addition, we prove that both equalities: $\mathrm{lcm}(n,n+1,\dots ,n+k)=d_{n,k}$ and $\mathrm{lcm}(n,n+1,\dots ,n+k)=m_{n,k}$ hold for infinitely many pairs $(n,k)$. To cite this article: B. Farhi, C. R. Acad. Sci. Paris, Ser. I 341 (2005).     

Realization of affine type A Kirillov–Reshetikhin crystals via polytopes

On the polytope defined by Feigin, Fourier and Littelmann, associated to any highest weight corresponding to a rectangular partition, we define a crystal structure of type $A_n$. We show that this crystal is isomorphic to the one obtained from Kashiwara?s crystal bases theory. Further we define on this polytope a bijective map and show that this map satisfies the properties of a weak promotion operator. This implies in particular that we provide an explicit realization of Kirillov–Reshetikhin crystals for the affine type $A_n^{(1)}$ via polytopes.     

A discrete isodiametric result: The Erdős–Ko–Rado theorem for multisets

There are many generalizations of the Erdős–Ko–Rado theorem. Here the new results (and problems) concern families of $t$-intersecting $k$-element multisets of an $n$-set. We point out connections to coding theory and geometry. We verify the conjecture that for $n\ge t(k-t)+2$ such a family can have at most $\left(\genfrac{}{}{00}{}{n+k-t-1}{k-t}\right)$ members.     

More odd graph theory from another point of view

The Kneser graph $K(n,k)$ has as vertices all $k$-element subsets of $\left[n\right]=\{1,2,\dots ,n\}$ and an edge between any two vertices that are disjoint. If $n=2k+1$, then $K(n,k)$ is called an odd graph. Let $n>4$ and $1<k<\frac{n}{2}$. In the present paper, we show that if the Kneser graph $K(n,k)$ is of even order where $n$ is an odd integer or both of the integers $n,k$ are even, then $K(n,k)$ is a vertex-transitive non Cayley graph. Although, these are special cases of Godsil [7], unlike his proof that uses some very deep group-theoretical facts, ours uses no heavy group-theoretic facts. We obtain our results by using some rather elementary facts of number theory and group theory. We show that ‘almost all’ odd graphs are of even order, and consequently are vertex-transitive non Cayley graphs. Finally, we show that if $k>4$ is an even integer such that $k$ is not of the form $k=2^t$ for some $t>2$, then the line graph of the odd graph $O_{k+1}$ is a vertex-transitive non Cayley graph.     

Stability in the Erdős–Gallai Theorem on cycles and paths,II

The Erd?s–Gallai Theorem states that for $k\ge 3$, any $n$-vertex graph with no cycle of length at least $k$ has at most $\frac{1}{2}(k?1)(n?1)$ edges. A stronger version of the Erd?s–Gallai Theorem was given by Kopylov: If $G$ is a 2-connected $n$-vertex graph with no cycle of length at least $k$, then $e\left(G\right)\le max\{h(n,k,2),h(n,k,?\frac{k?1}{2}?)\}$, where $h(n,k,a)?\left(\genfrac{}{}{0ex}{}{k?a}{2}\right)+a(n?k+a)$. Furthermore, Kopylov presented the two possible extremal graphs, one with $h(n,k,2)$ edges and one with $h(n,k,?\frac{k?1}{2}?)$ edges.In this paper, we complete a stability theorem which strengthens Kopylov’s result. In particular, we show that for $k\ge 3$ odd and all $n\ge k$, every $n$-vertex 2-connected graph $G$ with no cycle of length at least $k$ is a subgraph of one of the two extremal graphs or $e\left(G\right)\le max\{h(n,k,3),h(n,k,\frac{k?3}{2})\}$. The upper bound for $e\left(G\right)$ here is tight.