Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNote: Union-closed families with small average overlap densities
114
0
0.0
(
0
)
Authors
David Ellis
Ask ChatGPT about the research
No Arabic abstract
In this very short note, we point out that the average overlap density of a union-closed family $mathcal{F}$ of subsets of ${1,2,ldots,n}$ may be as small as $Theta((log log |mathcal{F}|)/(log |mathcal{F}|))$, for infinitely many positive integers $n$.
rate research
Read More
We show that the Union-Closed Conjecture holds for the union-closed family generated by the cyclic translates of any fixed set.
Let $Asubset mathbb{N}^{n}$ be an $r$-wise $s$-union family, that is, a family of sequences with $n$ components of non-negative integers such that for any $r$ sequences in $A$ the total sum of the maximum of each component in those sequences is at most $s$. We determine the maximum size of $A$ and its unique extremal configuration provided (i) $n$ is sufficiently large for fixed $r$ and $s$, or (ii) $n=r+1$.
A family of sets is called union-closed if whenever $A$ and $B$ are sets of the family, so is $Acup B$. The long-standing union-closed conjecture states that if a family of subsets of $[n]$ is union-closed, some element appears in at least half the sets of the family. A natural weakening is that the union-closed conjecture holds for large families; that is, families consisting of at least $p_02^n$ sets for some constant $p_0$. The first result in this direction appears in a recent paper of Balla, Bollobas and Eccles cite{BaBoEc}, who showed that union-closed families of at least $frac{2}{3}2^n$ sets satisfy the conjecture --- they proved this by determining the minimum possible average size of a set in a union-closed family of given size. However, the methods used in that paper cannot prove a better constant than $frac{2}{3}$. Here, we provide a stability result for the main theorem of cite{BaBoEc}, and as a consequence we prove the union-closed conjecture for families of at least $(frac{2}{3}-c)2^n$ sets, for a positive constant $c$.
The Turan number of a graph $H$, $text{ex}(n,H)$, is the maximum number of edges in a graph on $n$ vertices which does not have $H$ as a subgraph. A wheel $W_n$ is an $n$-vertex graph formed by connecting a single vertex to all vertices of a cycle $C_{n-1}$. Let $mW_{2k+1}$ denote the $m$ vertex-disjoint copies of $W_{2k+1}$. For sufficiently large $n$, we determine the Turan number and all extremal graphs for $mW_{2k+1}$. We also provide the Turan number and all extremal graphs for $W^{h}:=bigcuplimits^m_{i=1}W_{k_i}$ when $n$ is sufficiently large, where the number of even wheels is $h$ and $h>0$.
List coloring generalizes graph coloring by requiring the color of a vertex to be selected from a list of colors specific to that vertex. One refinement of list coloring, called choosability with separation, requires that the intersection of adjacent lists is sufficiently small. We introduce a new refinement, called choosability with union separation, where we require that the union of adjacent lists is sufficiently large. For $t geq k$, a $(k,t)$-list assignment is a list assignment $L$ where $|L(v)| geq k$ for all vertices $v$ and $|L(u)cup L(v)| geq t$ for all edges $uv$. A graph is $(k,t)$-choosable if there is a proper coloring for every $(k,t)$-list assignment. We explore this concept through examples of graphs that are not $(k,t)$-choosable, demonstrating sparsity conditions that imply a graph is $(k,t)$-choosable, and proving that all planar graphs are $(3,11)$-choosable and $(4,9)$-choosable.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
