ﻻ يوجد ملخص باللغة العربية
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 firs
A hypergraph is a generalization of a graph where edges can connect any number of vertices. In this paper, we extend the study of locating-dominating sets to hypergraphs. Along with some basic results, sharp bounds for the location-domination number
For a given hypergraph, an orientation can be assigned to the vertex-edge incidences. This orientation is used to define the adjacency and Laplacian matrices. In addition to studying these matrices, several related structures are investigated includi
In this paper, we study independent domination in directed graphs, which was recently introduced by Cary, Cary, and Prabhu. We provide a short, algorithmic proof that all directed acyclic graphs contain an independent dominating set. Using linear alg
The notion of a Riordan graph was introduced recently, and it is a far-reaching generalization of the well-known Pascal graphs and Toeplitz graphs. However, apart from a certain subclass of Toeplitz graphs, nothing was known on independent sets in Ri