Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA stability result for the union-closed size problem
81
0
0.0
(
0
)
Authors
Tom Eccles
Ask ChatGPT about the research
No Arabic abstract
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$.
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.
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$.
Given a sequence $mathbf{k} := (k_1,ldots,k_s)$ of natural numbers and a graph $G$, let $F(G;mathbf{k})$ denote the number of colourings of the edges of $G$ with colours $1,dots,s$ such that, for every $c in {1,dots,s}$, the edges of colour $c$ contain no clique of order $k_c$. Write $F(n;mathbf{k})$ to denote the maximum of $F(G;mathbf{k})$ over all graphs $G$ on $n$ vertices. This problem was first considered by ErdH{o}s and Rothschild in 1974, but it has been solved only for a very small number of non-trivial cases. In previous work with Yilma, we constructed a finite optimisation problem whose maximum is equal to the limit of $log_2 F(n;mathbf{k})/{nchoose 2}$ as $n$ tends to infinity and proved a stability theorem for complete multipartite graphs $G$. In this paper we provide a sufficient condition on $mathbf{k}$ which guarantees a general stability theorem for any graph $G$, describing the asymptotic structure of $G$ on $n$ vertices with $F(G;mathbf{k}) = F(n;mathbf{k}) cdot 2^{o(n^2)}$ in terms of solutions to the optimisation problem. We apply our theorem to systematically recover existing stability results as well as all cases with $s=2$. The proof uses a novel version of symmetrisation on edge-coloured weighted multigraphs.
We study the inverse problem of identifying a periodic potential perturbation of the Dirichlet Laplacian acting in an infinite cylindrical domain, whose cross section is assumed to be bounded. We prove log-log stable determination of the potential with respect to the partial Dirichlet-to-Neumann map, where the Neumann data is taken on slightly more than half of the boundary of the domain.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
