More Like this

1. On the rank of a random binary matrix

   https://doi.org/10.1137/1.9781611975482.58  

   Cooper, Colin; Frieze, Alan; Pegden, Wesley (January 2019, Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms)

   We study the rank of a random n × m matrix An, m; k with entries from GF(2), and exactly k unit entries in each column, the other entries being zero. The columns are chosen independently and uniformly at random from the set of all (nk) such columns. We obtain an asymptotically correct estimate for the rank as a function of the number of columns m in terms of c, n, k, and where m = cn/k. The matrix An, m; k forms the vertex-edge incidence matrix of a k-uniform random hypergraph H. The rank of An, m; k can be expressed as follows. Let |C2| be the number of vertices of the 2-core of H, and | E (C2)| the number of edges. Let m* be the value of m for which |C2| = |E(C2)|. Then w.h.p. for m < m* the rank of An, m; k is asymptotic to m, and for m ≥ m* the rank is asymptotic to m – |E(C2)| + |C2|. In addition, assign i.i.d. U[0, 1] weights Xi, i ∊ 1, 2, … m to the columns, and define the weight of a set of columns S as X(S) = ∑j∊S Xj. Define a basis as a set of n – 1 (k even) linearly independent columns. We obtain an asymptotically correct estimate for the minimum weight basis. This generalises the well-known result of Frieze [On the value of a random minimum spanning tree problem, Discrete Applied Mathematics, (1985)] that, for k = 2, the expected length of a minimum weight spanning tree tends to ζ(3) ∼ 1.202. 

   more » « less
2. Extremal Numbers and Sidorenko’s Conjecture

   https://doi.org/10.1093/imrn/rnae071  

   Conlon, David; Lee, Joonkyung; Sidorenko, Alexander (April 2024, International Mathematics Research Notices)

   Abstract Sidorenko’s conjecture states that, for all bipartite graphs $$H$$, quasirandom graphs contain asymptotically the minimum number of copies of $$H$$ taken over all graphs with the same order and edge density. While still open for graphs, the analogous statement is known to be false for hypergraphs. We show that there is some advantage in this, in that if Sidorenko’s conjecture does not hold for a particular $$r$$-partite $$r$$-uniform hypergraph $$H$$, then it is possible to improve the standard lower bound, coming from the probabilistic deletion method, for its extremal number $$\textrm{ex}(n,H)$$, the maximum number of edges in an $$n$$-vertex $$H$$-free $$r$$-uniform hypergraph. With this application in mind, we find a range of new counterexamples to the conjecture for hypergraphs, including all linear hypergraphs containing a loose triangle and all $$3$$-partite $$3$$-uniform tight cycles. 

   more » « less
3. Real-valued Group Testing for Quantitative Molecular Assays

   Saeedi, S.; Serrano, M.; Yang, D.G.; Brooks, J.P.; Buck, G.A.; Arodz, T. (January 2022, Research in Computational Molecular Biology RECOMB 2022)

   Pe'er, I. (Ed.)

   Combinatorial group testing and compressed sensing both focus on recovering a sparse vector of dimensionality n from a much smaller number 𝑚<𝑛 of measurements. In the first approach, the problem is defined over the Boolean field – the goal is to recover a Boolean vector and measurements are Boolean; in the second approach, the unknown vector and the measurements are over the reals. Here, we focus on real-valued group testing setting that more closely fits modern testing protocols relying on quantitative measurements, such as qPCR, where the goal is recovery of a sparse, Boolean vector and the pooling matrix needs to be Boolean and sparse, but the unknown input signal vector and the measurement outcomes are nonnegative reals, and the matrix algebra implied in the test protocol is over the reals. With the recent renewed interest in group testing, focus has been on quantitative measurements resulting from qPCR, but the method proposed for sample pooling were based on matrices designed with Boolean measurements in mind. Here, we investigate constructing pooling matrices dedicated for the real-valued group testing. We provide conditions for pooling matrices to guarantee unambiguous decoding of positives in this setting. We also show a deterministic algorithm for constructing matrices meeting the proposed condition, for small matrix sizes that can be implemented using a laboratory robot. Using simulated data, we show that the proposed approach leads to matrices that can be applied for higher positivity rates than combinatorial group testing matrices considered for viral testing previously. We also validate the approach through wet lab experiments involving SARS-CoV-2 nasopharyngeal swab samples. 

   more » « less
4. On Set Representation of Bounded Degree Hypergaphs

   https://doi.org/10.37236/12845  

   Basu, Ayush; Johnston, Griffin; Rödl, Vojtěch; Sales, Marcelo (February 2025, The Electronic Journal of Combinatorics)

   In their classical paper, Erdős, Goodman and Pósa studied the representation of a graph with vertex set $[n]$ by a family of subsets $$S_1,\dots, S_n$$ with the property that $$\{i,j\}$$ is an edge if and only if $$S_i\cap S_j\neq \emptyset$$. In this note, we consider a similar representation of bounded degree $$r$$-uniform hypergraphs and establish some bounds for a corresponding problem. 

   more » « less
5. A Hypergraph Analog of Dirac's Theorem for Long Cycles in 2-Connected Graphs, II: Large Uniformities

   https://doi.org/10.37236/12486  

   Kostochka, Alexandr; Luo, Ruth; McCourt, Grace (January 2025, The Electronic Journal of Combinatorics)

   Dirac proved that each $$n$$-vertex $$2$$-connected graph with minimum degree $$k$$ contains a cycle of length at least $$\min\{2k, n\}$$. We obtain analogous results for Berge cycles in hypergraphs. Recently, the authors proved an exact lower bound on the minimum degree ensuring a Berge cycle of length at least $$\min\{2k, n\}$$ in $$n$$-vertex $$r$$-uniform $$2$$-connected hypergraphs when $$k \geq r+2$$. In this paper we address the case $$k \leq r+1$$ in which the bounds have a different behavior. We prove that each $$n$$-vertex $$r$$-uniform $$2$$-connected hypergraph $$H$$ with minimum degree $$k$$ contains a Berge cycle of length at least $$\min\{2k,n,|E(H)|\}$$. If $$|E(H)|\geq n$$, this bound coincides with the bound of the Dirac's Theorem for 2-connected graphs. 

   more » « less