Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn maximal isolation sets in the uniform intersection matrix
136
0
0.0
(
0
)
Added by
Michal Parnas
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
There are distributed graph algorithms for finding maximal matchings and maximal independent sets in $O(Delta + log^* n)$ communication rounds; here $n$ is the number of nodes and $Delta$ is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on $n$ is optimal: these problems cannot be solved in $o(log^* n)$ rounds even if $Delta = 2$. However, the dependency on $Delta$ is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds. We prove that the upper bounds are tight. We show that maximal matchings and maximal independent sets cannot be found in $o(Delta + log log n / log log log n)$ rounds with any randomized algorithm in the LOCAL model of distributed computing. As a corollary, it follows that there is no deterministic algorithm for maximal matchings or maximal independent sets that runs in $o(Delta + log n / log log n)$ rounds; this is an improvement over prior lower bounds also as a function of $n$.
A $k$-uniform hypergraph with $n$ vertices is an $(n,k,ell)$-omitting system if it does not contain two edges whose intersection has size exactly $ell$. If in addition it does not contain two edges whose intersection has size greater than $ell$, then it is an $(n,k,ell)$-system. R{o}dl and v{S}iv{n}ajov{a} proved a lower bound for the independence number of $(n,k,ell)$-systems that is sharp in order of magnitude for fixed $2 le ell le k-1$. We consider the same question for the larger class of $(n,k,ell)$-omitting systems. For $kle 2ell+1$, we believe that the behavior is similar to the case of $(n,k,ell)$-systems and prove a nontrivial lower bound for the first open case $ell=k-2$. For $k>2ell+1$ we give new lower and upper bounds which show that the minimum independence number of $(n,k,ell)$-omitting systems has a very different behavior than for $(n,k,ell)$-systems. Our lower bound for $ell=k-2$ uses some adaptations of the random greedy independent set algorithm, and our upper bounds (constructions) for $k> 2ell+1$ are obtained from some pseudorandom graphs. We also prove some related results where we forbid more than two edges with a prescribed common intersection size and this leads to some applications in Ramsey theory. For example, we obtain good bounds for the Ramsey number $r_{k}(F^{k},t)$, where $F^{k}$ is the $k$-uniform Fan. Here the behavior is quite different than the case $k=2$ which reduces to the classical graph Ramsey number $r(3,t)$.
We study the problems of bounding the number weak and strong independent sets in $r$-uniform, $d$-regular, $n$-vertex linear hypergraphs with no cross-edges. In the case of weak independent sets, we provide an upper bound that is tight up to the first order term for all (fixed) $rge 3$, with $d$ and $n$ going to infinity. In the case of strong independent sets, for $r=3$, we provide an upper bound that is tight up to the second-order term, improving on a result of Ordentlich-Roth (2004). The tightness in the strong independent set case is established by an explicit construction of a $3$-uniform, $d$-regular, cross-edge free, linear hypergraph on $n$ vertices which could be of interest in other contexts. We leave open the general case(s) with some conjectures. Our proofs use the occupancy method introduced by Davies, Jenssen, Perkins, and Roberts (2017).
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 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
