Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRainbow independent sets on dense graph classes
96
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Given a family $mathcal{I}$ of independent sets in a graph, a rainbow independent set is an independent set $I$ such that there is an injection $phicolon Ito mathcal{I}$ where for each $vin I$, $v$ is contained in $phi(v)$. Aharoni, Briggs, J. Kim, and M. Kim [Rainbow independent sets in certain classes of graphs. arXiv:1909.13143] determined for various graph classes $mathcal{C}$ whether $mathcal{C}$ satisfies a property that for every $n$, there exists $N=N(mathcal{C},n)$ such that every family of $N$ independent sets of size $n$ in a graph in $mathcal{C}$ contains a rainbow independent set of size $n$. In this paper, we add two dense graph classes satisfying this property, namely, the class of graphs of bounded neighborhood diversity and the class of $r$-powers of graphs in a bounded expansion class.
rate research
Read More
For a given class $mathcal{C}$ of graphs and given integers $m leq n$, let $f_mathcal{C}(n,m)$ be the minimal number $k$ such that every $k$ independent $n$-sets in any graph belonging to $mathcal{C}$ have a (possibly partial) rainbow independent $m$-set. Motivated by known results on the finiteness and actual value of $f_mathcal{C}(n,m)$ when $mathcal{C}$ is the class of line graphs of graphs, we study this function for various other classes.
Given a graph $G$, let $f_{G}(n,m)$ be the minimal number $k$ such that every $k$ independent $n$-sets in $G$ have a rainbow $m$-set. Let $mathcal{D}(2)$ be the family of all graphs with maximum degree at most two. Aharoni et al. (2019) conjectured that (i) $f_G(n,n-1)=n-1$ for all graphs $Ginmathcal{D}(2)$ and (ii) $f_{C_t}(n,n)=n$ for $tge 2n+1$. Lv and Lu (2020) showed that the conjecture (ii) holds when $t=2n+1$. In this article, we show that the conjecture (ii) holds for $tgefrac{1}{3}n^2+frac{44}{9}n$. Let $C_t$ be a cycle of length $t$ with vertices being arranged in a clockwise order. An ordered set $I=(a_1,a_2,ldots,a_n)$ on $C_t$ is called a $2$-jump independent $n$-set of $C_t$ if $a_{i+1}-a_i=2pmod{t}$ for any $1le ile n-1$. We also show that a collection of 2-jump independent $n$-sets $mathcal{F}$ of $C_t$ with $|mathcal{F}|=n$ admits a rainbow independent $n$-set, i.e. (ii) holds if we restrict $mathcal{F}$ on the family of 2-jump independent $n$-sets. Moreover, we prove that if the conjecture (ii) holds, then (i) holds for all graphs $Ginmathcal{D}(2)$ with $c_e(G)le 4$, where $c_e(G)$ is the number of components of $G$ isomorphic to cycles of even lengths.
This paper explores the orbit structure and homomesy (constant averages over orbits) properties of certain actions of toggle groups on the collection of independent sets of a path graph. In particular we prove a generalization of a homomesy conjecture of Propp that for the action of a Coxeter element of vertex toggles, the difference of indicator functions of symmetrically-located vertices is 0-mesic. Then we use our analysis to show facts about orbit sizes that are easy to conjecture but nontrivial to prove. Besides its intrinsic interest, this particular combinatorial dynamical system is valuable in providing an interesting example of (a) homomesy in a context where large orbit sizes make a cyclic sieving phenomenon unlikely to exist, (b) the use of Coxeter theory to greatly generalize the set of actions for which results hold, and (c) the usefulness of Strikers notion of generalized toggle groups.
Grinblat (2002) asks the following question in the context of algebras of sets: What is the smallest number $mathfrak v = mathfrak v(n)$ such that, if $A_1, ldots, A_n$ are $n$ equivalence relations on a common finite ground set $X$, such that for each $i$ there are at least $mathfrak v$ elements of $X$ that belong to $A_i$-equivalence classes of size larger than $1$, then $X$ has a rainbow matching---a set of $2n$ distinct elements $a_1, b_1, ldots, a_n, b_n$, such that $a_i$ is $A_i$-equivalent to $b_i$ for each $i$? Grinblat has shown that $mathfrak v(n) le 10n/3 + O(sqrt{n})$. He asks whether $mathfrak v(n) = 3n-2$ for all $nge 4$. In this paper we improve the upper bound (for all large enough $n$) to $mathfrak v(n) le 16n/5 + O(1)$.
In this paper, firstly we show that the entropy constants of the number of independent sets on certain plane lattices are the same as the entropy constants of the corresponding cylindrical and toroidal lattices. Secondly, we consider three more complex lattices which can not be handled by a single transfer matrix as in the plane quadratic lattice case. By introducing the concept of transfer multiplicity, we obtain the lower and upper bounds of the entropy constants of crossed quadratic lattice, generalized aztec diamond lattice and 8-8-4 lattice.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
