Recent zbMATH articles in MSC 05C65https://www.zbmath.org/atom/cc/05C652021-04-16T16:22:00+00:00WerkzeugTurán and Ramsey numbers in linear triple systems.https://www.zbmath.org/1456.050862021-04-16T16:22:00+00:00"Gyárfás, András"https://www.zbmath.org/authors/?q=ai:gyarfas.andras"Sárközy, Gábor N."https://www.zbmath.org/authors/?q=ai:sarkozy.gabor-nSummary: In this paper we study Turán and Ramsey numbers in linear triple systems, defined as 3-uniform hypergraphs in which any two triples intersect in at most one vertex.
A famous result of \textit{I. Z. Ruzsa} and \textit{E. Szemerédi} [in: Combinatorics. Combinatorial colloquium held at Keszthely, Hungary, from 28 June to 3 July 1976. Vol. I and II. Amsterdam-Oxford-New York: North-Holland Publishing Company. 939--945 (1978; Zbl 0393.05031)] is that for any fixed \(c > 0\) and large enough \(n\) the following Turán-type theorem holds. If a linear triple system on \(n\) vertices has at least \(c n^2\) edges then it contains a triangle: three pairwise intersecting triples without a common vertex. In this paper we extend this result from triangles to other triple systems, called \(s\)-configurations. The main tool is a generalization of the induced matching lemma from \(a b a\)-patterns to more general ones.
We slightly generalize \(s\)-configurations to extended \(s\)-configurations. For these we cannot prove the corresponding Turán-type theorem, but we prove that they have the weaker, Ramsey property: they can be found in any \(t\)-coloring of the blocks of any sufficiently large Steiner triple system. Using this, we show that all unavoidable configurations with at most 5 blocks, except possibly the ones containing the sail \(C_{15} \) (configuration with blocks 123, 345, 561 and 147), are \(t\)-Ramsey for any \(t \geq 1\). The most interesting one among them is the wicket, \( D_4\), formed by three rows and two columns of a \(3 \times 3\) point matrix. In fact, the wicket is 1-Ramsey in a very strong sense: all Steiner triple systems except the Fano plane must contain a wicket.Hypergraph edge elimination -- a symbolic phase for Hermitian eigensolvers based on rank-1 modifications.https://www.zbmath.org/1456.650262021-04-16T16:22:00+00:00"Kahl, Karsten"https://www.zbmath.org/authors/?q=ai:kahl.karsten"Lang, Bruno"https://www.zbmath.org/authors/?q=ai:lang.brunoSummary: It is customary to identify sparse matrices with the corresponding adjacency or incidence graphs. For the solution of a linear system of equations using Gaussian elimination, the representation by its adjacency graph allows a symbolic factorization that can be used to predict memory footprints and enables the determination of near-optimal elimination orderings based on heuristics. The Hermitian eigenvalue problem on the other hand seems to evade such treatment at first glance due to its inherent iterative nature. In this paper we prove this assertion wrong by revealing a tight connection of Hermitian eigensolvers based on rank-\(1\) modifications with a symbolic edge elimination procedure. A symbolic calculation based on the incidence graph of the matrix can be used in analogy to the symbolic phase of Gaussian elimination to develop heuristics which reduce memory footprint and computations. Yet, we also show that the question of an optimal elimination strategy remains NP-complete, in analogy to the linear systems case.On-line and list on-line colorings of graphs and hypergraphs.https://www.zbmath.org/1456.050642021-04-16T16:22:00+00:00"Khuzieva, Alina E."https://www.zbmath.org/authors/?q=ai:khuzieva.alina-e"Shabanov, Dmitry A."https://www.zbmath.org/authors/?q=ai:shabanov.dmitry-a"Svyatokum, Polina O."https://www.zbmath.org/authors/?q=ai:svyatokum.polina-oSummary: The paper deals with on-line and list on-line colorings of graphs and hypergraphs. On-line coloring of a hypergraph is a game with two players, lister and painter, in which lister picks a vertex one by one (or a set of vertices) and painter should choose a color for the given vertex (or choose a subset to be colored). The problem is to find an extremal value of some characteristics which admits a winning strategy for painter. We establish the asymptotic behavior of the list on-line chromatic number for the complete multipartite graphs and hypergraphs. We also prove some results for the related property B-type problems for on-line colorings.The effect on the spectral radius of \(r\)-graphs by grafting or contracting edges.https://www.zbmath.org/1456.051082021-04-16T16:22:00+00:00"Li, Wei"https://www.zbmath.org/authors/?q=ai:li.wei.11"Chang, An"https://www.zbmath.org/authors/?q=ai:chang.anSummary: Let \(\mathcal{H}_n^{( r)}\) be the set of all connected \(r\)-graphs with given size \(n\). In this paper, we investigate the effect on the spectral radius of \(r\)-uniform hypergraphs by grafting or contracting an edge and then give the ordering of the \(r\)-graphs with small spectral radius over \(\mathcal{H}_n^{( r)}\), when \(n \geq 20\).The reliability analysis based on the generalized connectivity in balanced hypercubes.https://www.zbmath.org/1456.050922021-04-16T16:22:00+00:00"Wei, Chao"https://www.zbmath.org/authors/?q=ai:wei.chao"Hao, Rong-Xia"https://www.zbmath.org/authors/?q=ai:hao.rongxia"Chang, Jou-Ming"https://www.zbmath.org/authors/?q=ai:chang.jou-mingSummary: Recently, network connectivity analysis in terms of reliability has received attention from the network research community. Although traditional connectivity can be used to assess the strength of the connection between two nodes, however, such measures are inadequate for evaluating the connectivity among a set of multiple nodes in a network. Given a set \(S\) of vertices in a graph \(G\) with \(|S| \geqslant 2\), we say that a tree in \(G\) is an \(S\)-tree if it connects all vertices of \(S\). Two \(S\)-trees \(T\) and \(T^\prime\) in \(G\) are internally disjoint if \(E(T) \cap E (T^\prime) = \emptyset\) and \(V(T) \cap V (T^\prime) = S\). Let \(\kappa_G (S)\) denote the maximum number of \(S\)-trees in \(G\) such that every pair of them are internally disjoint. For an integer \(k \geqslant 2\), the generalized \(k\)-connectivity of graph \(G\) is defined as \(\kappa_k (G) = \min \{\kappa_G (S) \mid S \subseteq V (G) \text{ and } |S| = k\}\). In this paper, we investigate the problem of finding the generalized 3-connectivity of the \(n\)-dimensional balanced hypercube \(B H_n\), which is a hypercube-variant network and is superior to hypercube due to having a smaller diameter. As a result, we prove that \(\kappa_3 (BH_n) = 2n - 1\) for \(n \geqslant 1\).Spectral gap of the discrete Laplacian on triangulations.https://www.zbmath.org/1456.050992021-04-16T16:22:00+00:00"Chebbi, Yassin"https://www.zbmath.org/authors/?q=ai:chebbi.yassinSummary: Our goal in this paper is to find an estimate for the spectral gap of the Laplacian on a two-simplicial complex consisting on a hypergraph of a complete graph. An upper estimate is given by generalizing the Cheeger constant. The lower estimate is obtained from the first non-zero eigenvalue of the discrete Laplacian acting on the functions of certain sub-graphs.Automorphisms of the cube \(n^d\).https://www.zbmath.org/1456.051212021-04-16T16:22:00+00:00"Dvořák, Pavel"https://www.zbmath.org/authors/?q=ai:dvorak.pavel"Valla, Tomáš"https://www.zbmath.org/authors/?q=ai:valla.tomasSummary: Consider a hypergraph \(n^d\) where the vertices are points of the \(d\)-dimensional cube \([ n ]^d\) and the edges are all sets of \(n\) points such that they are in one line. We study the structure of the group of automorphisms of \(n^d\), i.e., permutations of points of \([ n ]^d\) preserving the edges. In this paper we provide a complete characterization. Moreover, we consider the Colored Cube Isomorphism problem of deciding whether for two colorings of the vertices of \(n^d\) there exists an automorphism of \(n^d\) preserving the colors. We show that this problem is \(\mathsf{GI} \)-complete.Conditions for a bigraph to be super-cyclic.https://www.zbmath.org/1456.050882021-04-16T16:22:00+00:00"Kostochka, Alexandr"https://www.zbmath.org/authors/?q=ai:kostochka.alexandr-v"Lavrov, Mikhail"https://www.zbmath.org/authors/?q=ai:lavrov.mikhail"Luo, Ruth"https://www.zbmath.org/authors/?q=ai:luo.ruth"Zirlin, Dara"https://www.zbmath.org/authors/?q=ai:zirlin.daraSummary: A hypergraph \(\mathcal H\) is super-pancyclic if for each \(A \subseteq V(\mathcal{H})\) with \(|A| \geqslant 3, \mathcal{H}\) contains a Berge cycle with base vertex set \(A\). We present two natural necessary conditions for a hypergraph to be super-pancyclic, and show that in several classes of hypergraphs these necessary conditions are also sufficient. In particular, they are sufficient for every hypergraph \(\mathcal{H}\) with \(\delta(\mathcal{H})\geqslant \max\{|V(\mathcal{H})|, \frac{|E(\mathcal H)|+10}{4}\} \).
We also consider super-cyclic bipartite graphs: \((X,Y)\)-bigraphs \(G\) such that for each \(A \subseteq X\) with \(|A| \geqslant 3, G\) has a cycle \(C_A\) such that \(V(C_A)\cap X=A\). Such graphs are incidence graphs of super-pancyclic hypergraphs, and our proofs use the language of such graphs.Link-aware semi-supervised hypergraph.https://www.zbmath.org/1456.681522021-04-16T16:22:00+00:00"Jin, Taisong"https://www.zbmath.org/authors/?q=ai:jin.taisong"Cao, Liujuan"https://www.zbmath.org/authors/?q=ai:cao.liujuan"Jie, Feiran"https://www.zbmath.org/authors/?q=ai:jie.feiran"Ji, Rongrong"https://www.zbmath.org/authors/?q=ai:ji.rongrongSummary: Hypergraph learning has been widely applied to various learning tasks. To ensure learning accuracy, it is essential to construct an informative hypergraph structure that effectively modulates data correlations. However, existing hypergraph construction methods essentially resort to an unsupervised learning paradigm, which ignores supervisory information, such as pairwise links/non-links. In this article, to exploit the supervisory information, we propose a novel link-aware hypergraph learning model, which modulates high-order correlations of data samples in a semi-supervised manner. To construct a hypergraph, a coefficients matrix of the entire dataset is first calculated by solving a linear regression problem. Then, pairwise link constraints are exploited and propagated to the unconstrained samples, upon which the coefficients matrix is adjusted accordingly. Finally, the adjusted coefficients are used to generate a set of the hyperedges, as well as calculate the corresponding weights. We have validated the proposed link-aware semi-supervised hypergraph model on the problem of image clustering. Superior performance over the state-of-the-art methods demonstrates the effectiveness of the proposed hypergraph model.On the strong chromatic number of a random 3-uniform hypergraph.https://www.zbmath.org/1456.050532021-04-16T16:22:00+00:00"Balobanov, Arseniy E."https://www.zbmath.org/authors/?q=ai:balobanov.arseniy-e"Shabanov, Dmitry A."https://www.zbmath.org/authors/?q=ai:shabanov.dmitry-aSummary: This paper deals with estimating the threshold for the strong \(r\)-colorability of a random 3-uniform hypergraph in the binomial model \(H ( n , 3 , p )\). A vertex coloring is said to be strong for a hypergraph if every two vertices sharing a common edge are colored with distinct colors. It is known that the threshold corresponds to the sparse case, when the expected number of edges is a linear function of \(n, p \left(\substack{ n \ 3}\right) = c n\), and \(c > 0\) depends on \(r\), but not on \(n\). We establish the threshold as a bound on the parameter \(c\) up to an additive constant. In particular, by using the second moment method we prove that for large enough \(r\) and \(c < \frac{ r \ln r}{ 3} - \frac{ 5}{ 18} \ln r - \frac{ 1}{ 3} - r^{- 1 \slash 6} \), the random hypergraph \(H ( n , 3 , p )\) is strongly \(r\)-colorable with high probability and, vice versa, for \(c > \frac{ r \ln r}{ 3} - \frac{ 5}{ 18} \ln r + O ( \ln r \slash r )\), it is not strongly \(r\)-colorable with high probability.