Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSet systems related to a house allocation problem
96
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We are given a set $A$ of buyers, a set $B$ of houses, and for each buyer a preference list, i.e., an ordering of the houses. A house allocation is an injective mapping $tau$ from $A$ to $B$, and $tau$ is strictly better than another house allocation $tau eq tau$ if for every buyer $i$, $tau(i)$ does not come before $tau(i)$ in the preference list of $i$. A house allocation is Pareto optimal if there is no strictly better house allocation. Let $s(tau)$ be the image of $tau$ (i.e., the set of houses sold in the house allocation $tau$). We are interested in the largest possible cardinality $f(m)$ of the family of sets $s(tau)$ for Pareto optimal mappings $tau$ taken over all sets of preference lists of $m$ buyers. We improve the earlier upper bound on $f(m)$ given by Asinowski, Keszegh and Miltzow by making a connection between this problem and some problems in extremal set theory.
rate research
Read More
Three intersection theorems are proved. First, we determine the size of the largest set system, where the system of the pairwise unions is l-intersecting. Then we investigate set systems where the union of any s sets intersect the union of any t sets. The maximal size of such a set system is determined exactly if s+t<5, and asymptotically if s+t>4. Finally, we exactly determine the maximal size of a k-uniform set system that has the above described (s,t)-union-intersecting property, for large enough n.
A family ${A_{0},ldots,A_{d}}$ of $k$-element subsets of $[n]={1,2,ldots,n}$ is called a simplex-cluster if $A_{0}capcdotscap A_{d}=varnothing$, $|A_{0}cupcdotscup A_{d}|le2k$, and the intersection of any $d$ of the sets in ${A_{0},ldots,A_{d}}$ is nonempty. In 2006, Keevash and Mubayi conjectured that for any $d+1le klefrac{d}{d+1}n$, the largest family of $k$-element subsets of $[n]$ that does not contain a simplex-cluster is the family of all $k$-subsets that contain a given element. We prove the conjecture for all $kgezeta n$ for an arbitrarily small $zeta>0$, provided that $nge n_{0}(zeta,d)$. We call a family ${A_{0},ldots,A_{d}}$ of $k$-element subsets of $[n]$ a $(d,k,s)$-cluster if $A_{0}capcdotscap A_{d}=varnothing$ and $|A_{0}cupcdotscup A_{d}|le s$. We also show that for any $zeta nle klefrac{d}{d+1}n$ the largest family of $k$-element subsets of $[n]$ that does not contain a $(d,k,(frac{d+1}{d}+zeta)k)$-cluster is again the family of all $k$-subsets that contain a given element, provided that $nge n_{0}(zeta,d)$. Our proof is based on the junta method for extremal combinatorics initiated by Dinur and Friedgut and further developed by Ellis, Keller, and the author.
The class of even-hole-free graphs is very similar to the class of perfect graphs, and was indeed a cornerstone in the tools leading to the proof of the Strong Perfect Graph Theorem. However, the complexity of computing a maximum independent set (MIS) is a long-standing open question in even-hole-free graphs. From the hardness point of view, MIS is W[1]-hard in the class of graphs without induced 4-cycle (when parameterized by the solution size). Halfway of these, we show in this paper that MIS is FPT when parameterized by the solution size in the class of even-hole-free graphs. The main idea is to apply twice the well-known technique of augmenting graphs to extend some initial independent set.
We investigate the independence number of two graphs constructed from a polarity of $mathrm{PG}(2,q)$. For the first graph under consideration, the ErdH{o}s-Renyi graph $ER_q$, we provide an improvement on the known lower bounds on its independence number. In the second part of the paper we consider the ErdH{o}s-Renyi hypergraph of triangles $mathcal{H}_q$. We determine the exact magnitude of the independence number of $mathcal{H}_q$, $q$ even. This solves a problem posed by Mubayi and Williford.
Membrane computing is a branch of natural computingwhich abstracts fromthe structure and the functioning of living cells. The computation models obtained in the field of membrane computing are usually called P systems. P systems have been used to solve computationally hard problems efficiently on the assumption that the execution of each rule is completed in exactly one time-unit (a global clock is assumed for timing and synchronizing the execution of rules). However, in biological reality, different biological processes take different times to be completed, which can also be influenced by many environmental factors. In this work, with this biological reality, we give a time-free solution to independent set problemusing P systems with active membranes, which solve the problem independent of the execution time of the involved rules.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
