Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMaximal $2$-distance sets containing the regular simplex
162
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A finite subset $X$ of the Euclidean space is called an $m$-distance set if the number of distances between two distinct points in $X$ is equal to $m$. An $m$-distance set $X$ is said to be maximal if any vector cannot be added to $X$ while maintaining the $m$-distance condition. We investigate a necessary and sufficient condition for vectors to be added to a regular simplex such that the set has only $2$ distances. We construct several $d$-dimensional maximal $2$-distance sets that contain a $d$-dimensional regular simplex. In particular, there exist infinitely many maximal non-spherical $2$-distance sets that contain both the regular simplex and the representation of a strongly resolvable design. The maximal $2$-distance set has size $2s^2(s+1)$, and the dimension is $d=(s-1)(s+1)^2-1$, where $s$ is a prime power.
rate research
Read More
A set $X$ in the Euclidean space $mathbb{R}^d$ is called an $m$-distance set if the set of Euclidean distances between two distinct points in $X$ has size $m$. An $m$-distance set $X$ in $mathbb{R}^d$ is said to be maximal if there does not exist a vector $x$ in $mathbb{R}^d$ such that the union of $X$ and ${x}$ still has only $m$ distances. Bannai--Sato--Shigezumi (2012) investigated the maximal $m$-distance sets which contain the Euclidean representation of the Johnson graph $J(n,m)$. In this paper, we consider the same problem for the Hamming graph $H(n,m)$. The Euclidean representation of $H(n,m)$ is an $m$-distance set in $mathbb{R}^{m(n-1)}$. We prove that the maximum $n$ is $m^2 + m - 1$ such that the representation of $H(n,m)$ is not maximal as an $m$-distance set. Moreover we classify the largest $m$-distance sets which contain the representation of $H(n,m)$ for $mleq 4$ and any $n$. We also classify the maximal $2$-distance sets in $mathbb{R}^{2n-1}$ which contain the representation of $H(n,2)$ for any $n$.
We show that, in contrast to the integers setting, almost all even order abelian groups $G$ have exponentially fewer maximal sum-free sets than $2^{mu(G)/2}$, where $mu(G)$ denotes the size of a largest sum-free set in $G$. This confirms a conjecture of Balogh, Liu, Sharifzadeh and Treglown.
Nielsen proved that the maximum number of maximal independent sets (MISs) of size $k$ in an $n$-vertex graph is asymptotic to $(n/k)^k$, with the extremal construction a disjoint union of $k$ cliques with sizes as close to $n/k$ as possible. In this paper we study how many MISs of size $k$ an $n$-vertex graph $G$ can have if $G$ does not contain a clique $K_t$. We prove for all fixed $k$ and $t$ that there exist such graphs with $n^{lfloorfrac{(t-2)k}{t-1}rfloor-o(1)}$ MISs of size $k$ by utilizing recent work of Gowers and B. Janzer on a generalization of the Ruzsa-Szemeredi problem. We prove that this bound is essentially best possible for triangle-free graphs when $kle 4$.
A frequency square is a square matrix in which each row and column is a permutation of the same multiset of symbols. A frequency square is of type $(n;lambda)$ if it contains $n/lambda$ symbols, each of which occurs $lambda$ times per row and $lambda$ times per column. In the case when $lambda=n/2$ we refer to the frequency square as binary. A set of $k$-MOFS$(n;lambda)$ is a set of $k$ frequency squares of type $(n;lambda)$ such that when any two of the frequency squares are superimposed, each possible ordered pair occurs equally often. A set of $k$-maxMOFS$(n;lambda)$ is a set of $k$-MOFS$(n;lambda)$ that is not contained in any set of $(k+1)$-MOFS$(n;lambda)$. For even $n$, let $mu(n)$ be the smallest $k$ such that there exists a set of $k$-maxMOFS$(n;n/2)$. It was shown in [Electron. J. Combin. 27(3) (2020), P3.7] that $mu(n)=1$ if $n/2$ is odd and $mu(n)>1$ if $n/2$ is even. Extending this result, we show that if $n/2$ is even, then $mu(n)>2$. Also, we show that whenever $n$ is divisible by a particular function of $k$, there does not exist a set of $k$-maxMOFS$(n;n/2)$ for any $kle k$. In particular, this means that $limsup mu(n)$ is unbounded. Nevertheless we can construct infinite families of maximal binary MOFS of fixed cardinality. More generally, let $q=p^u$ be a prime power and let $p^v$ be the highest power of $p$ that divides $n$. If $0le v-uh<u/2$ for $hge1$ then we show that there exists a set of $(q^h-1)^2/(q-1)$-maxMOFS$(n;n/q)$.
Let $A_{k,t}$ be the matrix that represents the adjacency matrix of the intersection bipartite graph of all subsets of size $t$ of ${1,2,...,k}$. We give constructions of large isolation sets in $A_{k,t}$, where, for a large enough $k$, our constructions are the best possible. We first prove that the largest identity submatrix in $A_{k,t}$ is of size $k-2t+2$. Then we provide constructions of isolations sets in $A_{k,t}$ for any $tgeq 2$, as follows: begin{itemize} item If $k = 2t+r$ and $0 leq r leq 2t-3$, there exists an isolation set of size $2r+3 = 2k-4t+3$. item If $k geq 4t-3$, there exists an isolation set of size $k$. end{itemize} The construction is maximal for $kgeq 4t-3$, since the Boolean rank of $A_{k,t}$ is $k$ in this case. As we prove, the construction is maximal also for $k = 2t, 2t+1$. Finally, we consider the problem of the maximal triangular isolation submatrix of $A_{k,t}$ that has ones in every entry on the main diagonal and below it, and zeros elsewhere. We give an optimal construction of such a submatrix of size $({2t choose t}-1) times ({2t choose t}-1)$, for any $t geq 1$ and a large enough $k$. This construction is tight, as there is a matching upper bound, which can be derived from a theorem of Frankl about skew matrices.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
