اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدSet systems related to a house allocation problem
96
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 n
onempty. 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 n
umber. 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 sol
ve 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
