اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدClique decompositions of multipartite graphs and completion of Latin squares
70
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Our main result essentially reduces the problem of finding an edge-decomposition of a balanced r-partite graph of large minimum degree into r-cliques to the problem of finding a fractional r-clique decomposition or an approximate one. Together with very recent results of Bowditch and Dukes as well as Montgomery on fractional decompositions into triangles and cliques respectively, this gives the best known bounds on the minimum degree which ensures an edge-decomposition of an r-partite graph into r-cliques (subject to trivially necessary divisibility conditions). The case of triangles translates into the setting of partially completed Latin squares and more generally the case of r-cliques translates into the setting of partially completed mutually orthogonal Latin squares.
قيم البحث
اقرأ أيضاً
Let $G$ be a graph whose edges are coloured with $k$ colours, and $mathcal H=(H_1,dots , H_k)$ be a $k$-tuple of graphs. A monochromatic $mathcal H$-decomposition of $G$ is a partition of the edge set of $G$ such that each part is either a single edg
e or forms a monochromatic copy of $H_i$ in colour $i$, for some $1le ile k$. Let $phi_{k}(n,mathcal H)$ be the smallest number $phi$, such that, for every order-$n$ graph and every $k$-edge-colouring, there is a monochromatic $mathcal H$-decomposition with at most $phi$ elements. Extending the previous results of Liu and Sousa [Monochromatic $K_r$-decompositions of graphs, Journal of Graph Theory}, 76:89--100, 2014], we solve this problem when each graph in $mathcal H$ is a clique and $nge n_0(mathcal H)$ is sufficiently large.
Our main result is that every graph $G$ on $nge 10^4r^3$ vertices with minimum degree $delta(G) ge (1 - 1 / 10^4 r^{3/2} ) n$ has a fractional $K_r$-decomposition. Combining this result with recent work of Barber, Kuhn, Lo and Osthus leads to the bes
t known minimum degree thresholds for exact (non-fractional) $F$-decompositions for a wide class of graphs~$F$ (including large cliques). For general $k$-uniform hypergraphs, we give a short argument which shows that there exists a constant $c_k>0$ such that every $k$-uniform hypergraph $G$ on $n$ vertices with minimum codegree at least $(1- c_k /r^{2k-1}) n $ has a fractional $K^{(k)}_r$-decomposition, where $K^{(k)}_r$ is the complete $k$-uniform hypergraph on $r$ vertices. (Related fractional decomposition results for triangles have been obtained by Dross and for hypergraph cliques by Dukes as well as Yuster.) All the above new results involve purely combinatorial arguments. In particular, this yields a combinatorial proof of Wilsons theorem that every large $F$-divisible complete graph has an $F$-decomposition.
We develop a limit theory of Latin squares, paralleling the recent limit theories of dense graphs and permutations. We introduce a notion of density, an appropriate version of the cut distance, and a space of limit objects - so-called Latinons. Key r
esults of our theory are the compactness of the limit space and the equivalence of the topologies induced by the cut distance and the left-convergence. Last, using Keevashs recent results on combinatorial designs, we prove that each Latinon can be approximated by a finite Latin square.
We prove a conjecture by Garbe et al. [arXiv:2010.07854] by showing that a Latin square is quasirandom if and only if the density of every 2x3 pattern is 1/720+o(1). This result is the best possible in the sense that 2x3 cannot be replaced with 2x2 or 1xN for any N.
We introduce a notion of parity for transversals, and use it to show that in Latin squares of order $2 bmod 4$, the number of transversals is a multiple of 4. We also demonstrate a number of relationships (mostly congruences modulo 4) involving $E_1,
dots, E_n$, where $E_i$ is the number of diagonals of a given Latin square that contain exactly $i$ different symbols. Let $A(imid j)$ denote the matrix obtained by deleting row $i$ and column $j$ from a parent matrix $A$. Define $t_{ij}$ to be the number of transversals in $L(imid j)$, for some fixed Latin square $L$. We show that $t_{ab}equiv t_{cd}bmod2$ for all $a,b,c,d$ and $L$. Also, if $L$ has odd order then the number of transversals of $L$ equals $t_{ab}$ mod 2. We conjecture that $t_{ac} + t_{bc} + t_{ad} + t_{bd} equiv 0 bmod 4$ for all $a,b,c,d$. In the course of our investigations we prove several results that could be of interest in other contexts. For example, we show that the number of perfect matchings in a $k$-regular bipartite graph on $2n$ vertices is divisible by $4$ when $n$ is odd and $kequiv0bmod 4$. We also show that $${rm per}, A(a mid c)+{rm per}, A(b mid c)+{rm per}, A(a mid d)+{rm per}, A(b mid d) equiv 0 bmod 4$$ for all $a,b,c,d$, when $A$ is an integer matrix of odd order with all row and columns sums equal to $kequiv2bmod4$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
