Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPartitioning the power set of $[n]$ into $C_k$-free parts
180
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We show that for $n geq 3, n e 5$, in any partition of $mathcal{P}(n)$, the set of all subsets of $[n]={1,2,dots,n}$, into $2^{n-2}-1$ parts, some part must contain a triangle --- three different subsets $A,B,Csubseteq [n]$ such that $Acap B$, $Acap C$, and $Bcap C$ have distinct representatives. This is sharp, since by placing two complementary pairs of sets into each partition class, we have a partition into $2^{n-2}$ triangle-free parts. We also address a more general Ramsey-type problem: for a given graph $G$, find (estimate) $f(n,G)$, the smallest number of colors needed for a coloring of $mathcal{P}(n)$, such that no color class contains a Berge-$G$ subhypergraph. We give an upper bound for $f(n,G)$ for any connected graph $G$ which is asymptotically sharp (for fixed $k$) when $G=C_k, P_k, S_k$, a cycle, path, or star with $k$ edges. Additional bounds are given for $G=C_4$ and $G=S_3$.
rate research
Read More
We show that for any colouring of the edges of the complete bipartite graph $K_{n,n}$ with 3 colours there are 5 disjoint monochromatic cycles which together cover all but $o(n)$ of the vertices. In the same situation, 18 disjoint monochromatic cycles together cover all vertices.
For a subgraph $G$ of the blow-up of a graph $F$, we let $delta^*(G)$ be the smallest minimum degree over all of the bipartite subgraphs of $G$ induced by pairs of parts that correspond to edges of $F$. In [Triangle-factors in a balanced blown-up triangle. Discrete Mathematics, 2000], Johansson proved that if $G$ is a spanning subgraph of the blow-up of $C_3$ with parts of size $n$ and $delta^*(G) ge frac{2}{3}n + sqrt{n}$, then $G$ contains $n$ vertex-disjoint triangles, and presented the following conjecture of Haggkvist: If $G$ is a spanning subgraph of the blow-up of $C_k$ with parts of size $n$ and $delta^*(G) ge (1 + 1/k)n/2 + 1$, then $G$ contains $n$ vertex disjoint copies of $C_k$ such that each $C_k$ intersects each of the $k$ parts exactly once. The degree condition of this conjecture is tight when $k=3$ and cannot be strengthened by more than one when $k ge 4$., A similar conjecture was also made by Fischer in [Variants of the Hajnal-Szemeredi Theorem. Journal of Graph Theory, 1999] and the triangle case was proved for large $n$ by Magyar and Martin in [Tripartite version of the Corradi-Hajnal Theorem. Discrete Mathematics, 2002]. In this paper, we prove this Conjecture asymptotically. We also pose a conjecture which generalizes this result by allowing the minimum degree conditions on the nonempty bipartite subgraphs induced by pairs of parts to vary. Our second result supports this new conjecture by proving the triangle case. This result generalizes Johannsons result asymptotically.
In this paper, we exploit the theory of dense graph limits to provide a new framework to study the stability of graph partitioning methods, which we call structural consistency. Both stability under perturbation as well as asymptotic consistency (i.e., convergence with probability $1$ as the sample size goes to infinity under a fixed probability model) follow from our notion of structural consistency. By formulating structural consistency as a continuity result on the graphon space, we obtain robust results that are completely independent of the data generating mechanism. In particular, our results apply in settings where observations are not independent, thereby significantly generalizing the common probabilistic approach where data are assumed to be i.i.d. In order to make precise the notion of structural consistency of graph partitioning, we begin by extending the theory of graph limits to include vertex colored graphons. We then define continuous node-level statistics and prove that graph partitioning based on such statistics is consistent. Finally, we derive the structural consistency of commonly used clustering algorithms in a general model-free setting. These include clustering based on local graph statistics such as homomorphism densities, as well as the popular spectral clustering using the normalized Laplacian. We posit that proving the continuity of clustering algorithms in the graph limit topology can stand on its own as a more robust form of model-free consistency. We also believe that the mathematical framework developed in this paper goes beyond the study of clustering algorithms, and will guide the development of similar model-free frameworks to analyze other procedures in the broader mathematical sciences.
A Kakeya set $S subset (mathbb{Z}/Nmathbb{Z})^n$ is a set containing a line in each direction. We show that, when $N$ is any square-free integer, the size of the smallest Kakeya set in $(mathbb{Z}/Nmathbb{Z})^n$ is at least $C_{n,epsilon} N^{n - epsilon}$ for any $epsilon$ -- resolving a special case of a conjecture of Hickman and Wright. Previously, such bounds were only known for the case of prime $N$. We also show that the case of general $N$ can be reduced to lower bounding the $mathbb{F}_p$ rank of the incidence matrix of points and hyperplanes over $(mathbb{Z}/p^kmathbb{Z})^n$.
A defensive $k$-alliance in a graph is a set $S$ of vertices with the property that every vertex in $S$ has at least $k$ more neighbors in $S$ than it has outside of $S$. A defensive $k$-alliance $S$ is called global if it forms a dominating set. In this paper we study the problem of partitioning the vertex set of a graph into (global) defensive $k$-alliances. The (global) defensive $k$-alliance partition number of a graph $Gamma=(V,E)$, ($psi_{k}^{gd}(Gamma)$) $psi_k^{d}(Gamma)$, is defined to be the maximum number of sets in a partition of $V$ such that each set is a (global) defensive $k$-alliance. We obtain tight bounds on $psi_k^{d}(Gamma)$ and $psi_{k}^{gd}(Gamma)$ in terms of several parameters of the graph including the order, size, maximum and minimum degree, the algebraic connectivity and the isoperimetric number. Moreover, we study the close relationships that exist among partitions of $Gamma_1times Gamma_2$ into (global) defensive $(k_1+k_2)$-alliances and partitions of $Gamma_i$ into (global) defensive $k_i$-alliances, $iin {1,2}$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
