Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userForbidden Families of Minimal Quadratic and Cubic Configurations
56
0
0.0
(
0
)
Authors
Attila Sali
Ask ChatGPT about the research
No Arabic abstract
A matrix is emph{simple} if it is a (0,1)-matrix and there are no repeated columns. Given a (0,1)-matrix $F$, we say a matrix $A$ has $F$ as a emph{configuration}, denoted $Fprec A$, if there is a submatrix of $A$ which is a row and column permutation of $F$. Let $|A|$ denote the number of columns of $A$. Let $mathcal{F}$ be a family of matrices. We define the extremal function $text{forb}(m, mathcal{F}) = max{|A|colon A text{ is an }m-text{rowed simple matrix and has no configuration } Finmathcal{F}}$. We consider pairs $mathcal{F}={F_1,F_2}$ such that $F_1$ and $F_2$ have no common extremal construction and derive that individually each $text{forb}(m, F_i)$ has greater asymptotic growth than $text{forb}(m, mathcal{F})$, extending research started by Anstee and Koch.
rate research
Read More
Recall that in a laminar family, any two sets are either disjoint or contained one in the other. Here, a parametrized weakening of this condition is introduced. Let us say that a set system $mathcal{F} subseteq 2^X$ is $t$-laminar if $A,B in mathcal{F}$ with $|A cap B| ge t$ implies $A subseteq B$ or $B subseteq A$. We obtain very close asymptotic bounds in terms of $n$ on the maximum size of a $2$-laminar family $mathcal{F} subseteq 2^{[n]}$. A construction for $3$-laminar families and a crude analysis for general $t$ are also given.
Minimal forbidden factors are a useful tool for investigating properties of words and languages. Two factorial languages are distinct if and only if they have different (antifactorial) sets of minimal forbidden factors. There exist algorithms for computing the minimal forbidden factors of a word, as well as of a regular factorial language. Conversely, Crochemore et al. [IPL, 1998] gave an algorithm that, given the trie recognizing a finite antifactorial language $M$, computes a DFA recognizing the language whose set of minimal forbidden factors is $M$. In the same paper, they showed that the obtained DFA is minimal if the input trie recognizes the minimal forbidden factors of a single word. We generalize this result to the case of a circular word. We discuss several combinatorial properties of the minimal forbidden factors of a circular word. As a byproduct, we obtain a formal definition of the factor automaton of a circular word. Finally, we investigate the case of minimal forbidden factors of the circular Fibonacci words.
A permutation group is said to be quasiregular if every its transitive constituent is regular, and a quasiregular coherent configuration can be thought as a combinatorial analog of such a group: the transitive constituents are replaced by the homogeneous components. In this paper, we are interested in the question when the configuration is schurian, i.e., formed by the orbitals of a permutation group, or/and separable, i.e., uniquely determined by the intersection numbers. In these terms, an old result of Hanna Neumann is, in a sense, dual to the statement that the quasiregular coherent configurations with cyclic homogeneous components are schurian. In the present paper, we (a) establish the duality in a precise form and (b) generalize the latter result by proving that a quasiregular coherent configuration is schurian and separable if the groups associated with homogeneous components have distributive lattices of normal subgroups.
In this note, we fix a graph $H$ and ask into how many vertices can each vertex of a clique of size $n$ can be split such that the resulting graph is $H$-free. Formally: A graph is an $(n,k)$-graph if its vertex sets is a pairwise disjoint union of $n$ parts of size at most $k$ each such that there is an edge between any two distinct parts. Let $$ f(n,H) = min {k in mathbb N : mbox{there is an $(n,k)$-graph $G$ such that $H otsubseteq G$}} . $$ Barbanera and Ueckerdt observed that $f(n, H)=2$ for any graph $H$ that is not bipartite. If a graph $H$ is bipartite and has a well-defined Turan exponent, i.e., ${rm ex}(n, H) = Theta(n^r)$ for some $r$, we show that $Omega (n^{2/r -1}) = f(n, H) = O (n^{2/r-1} log ^{1/r} n)$. We extend this result to all bipartite graphs for which an upper and a lower Turan exponents do not differ by much. In addition, we prove that $f(n, K_{2,t}) =Theta(n^{1/3})$ for any fixed $t$.
Determining the maximum size of a $t$-intersecting code in $[m]^n$ was a longstanding open problem of Frankl and Furedi, solved independently by Ahlswede and Khachatrian and by Frankl and Tokushige. We extend their result to the setting of forbidden intersections, by showing that for any $m>2$ and $n$ large compared with $t$ (but not necessarily $m$) that the same bound holds for codes with the weaker property of being $(t-1)$-avoiding, i.e. having no two vectors that agree on exactly $t-1$ coordinates. Our proof proceeds via a junta approximation result of independent interest, which we prove via a development of our recent theory of global hypercontractivity: we show that any $(t-1)$-avoiding code is approximately contained in a $t$-intersecting junta (a code where membership is determined by a constant number of co-ordinates). In particular, when $t=1$ this gives an alternative proof of a recent result of Eberhard, Kahn, Narayanan and Spirkl that symmetric intersecting codes in $[m]^n$ have size $o(m^n)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
