English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A family of permutations $\mathcal{F} \subset S_{n}$ is said to be$t$-intersecting if any two permutations in $\mathcal{F}$ agree on at least $t$points. It is said to be $(t-1)$-intersection-free if no two permutations in$\mathcal{F}$ agree on exactly $t-1$ points. If $S,T \subset \{1,2,\ldots,n\}$with $|S|=|T|$, and $\pi: S \to T$ is a bijection, the $\pi$-star in $S_n$ isthe family of all permutations in $S_n$ that agree with $\pi$ on all of $S$. An$s$-star is a $\pi$-star such that $\pi$ is a bijection between sets of size$s$. Friedgut and Pilpel, and independently the first author, showed that if$\mathcal{F} \subset S_n$ is $t$-intersecting, and $n$ is sufficiently largedepending on $t$, then $|\mathcal{F}| \leq (n-t)!$; this proved a conjecture ofDeza and Frankl from 1977. Equality holds only if $\mathcal{F}$ is a $t$-star.  In this paper, we give a more `robust' proof of a strengthening of theDeza-Frankl conjecture, namely that if $n$ is sufficiently large depending on$t$, and $\mathcal{F} \subset S_n$ is $(t-1)$-intersection-free, then$|\mathcal{F} \leq (n-t)!$, with equality only if $\mathcal{F}$ is a $t$-star.The main ingredient of our proof is a `junta approximation' result, namely,that any $(t-1)$-intersection-free family of permutations is essentiallycontained in a $t$-intersecting {\em junta} (a `junta' being a union of abounded number of $O(1)$-stars). The proof of our junta approximation resultrelies, in turn, on a weak regularity lemma for families of permutations, acombinatorial argument that `bootstraps' a weak notion of pseudorandomness intoa stronger one, and finally a spectral argument for pairs ofhighly-pseudorandom fractional families. Our proof employs four differentnotions of pseudorandomness, three being combinatorial in nature, and one beingalgebraic.

Approximation by juntas in the symmetric group, and forbidden intersection problems