We consider the algorithmic decision problem that takes as input an \( n \) -vertex \( k \) -uniform hypergraph \( H \) with minimum codegree at least \(m-c\) and decides whether it has a matching of size \( m \) . We show that this decision problem is fixed parameter tractable with respect to \( c \) . Furthermore, our algorithm not only decides the problem, but actually either finds a matching of size \( m \) or a certificate that no such matching exists. In particular, when \(m=n/k\) and \(c=O(\log n)\) , this gives a polynomial-time algorithm that, given any \( n \) -vertex \( k \) -uniform hypergraph \( H \) with minimum codegree at least \(n/k-c\) , finds either a perfect matching in \( H \) or a certificate that no perfect matching exists.

We consider the design of a positioning system where a robot determines its position from local observations. This is a well-studied problem of considerable practical importance and mathematical interest. The dominant paradigm derives from the classical theory of de Bruijn sequences, where the robot has access to a window within a larger code and can determine its position if these windows are distinct. We propose an alternative model in which the robot has more limited observational powers, which we argue is more realistic in terms of engineering: the robot does not have access to the full pattern of colours (or letters) in the window, but only to the intensity of each colour (or the number of occurrences of each letter). This leads to a mathematically interesting problem with a different flavour to that arising in the classical paradigm, requiring new construction techniques. The parameters of our construction are optimal up to a constant factor, and computing the position requires only a constant number of arithmetic operations.

Abstract. Thomassé conjectured the following strengthening of the well-known Caccetta–Häaggkvist conjecture: any digraph with minimum out-degree [Formula: see text] and girth [Formula: see text] contains a directed path of length [Formula: see text]. Bai and Manoussakis [ SIAM J. Discrete Math., 33 (2019), pp. 2444–2451] gave counterexamples to Thomassé’s conjecture for every even [Formula: see text]. In this note, we first generalize their counterexamples to show that Thomassé’s conjecture is false for every [Formula: see text]. We also obtain the positive result that any digraph with minimum out-degree [Formula: see text] and girth [Formula: see text] contains a directed path of [Formula: see text]. For small [Formula: see text] we obtain better bounds; e.g., for [Formula: see text] we show that oriented graph with minimum out-degree [Formula: see text] contains a directed path of length [Formula: see text]. Furthermore, we show that each [Formula: see text]-regular digraph with girth [Formula: see text] contains a directed path of length [Formula: see text]. Our results give the first nontrivial bounds for these problems.

We show that for any integers k ≥ 3 and c ≥ 0 there is a polynomial-time algorithm, that given any n-vertex k-uniform hypergraph H with minimum codegree at least n/k – c, finds either a perfect matching in H or a certificate that no perfect matching exists.

We give a fully polynomial-time approximation scheme (FPTAS) and an efficient sampling algorithm for the high-fugacity hard-core model on bounded-degree bipartite expander graphs and the low-temperature ferromagnetic Potts model on bounded-degree expander graphs. The results apply, for example, to random (bipartite) $\Delta$-regular graphs, for which no efficient algorithms were known for these problems (with the exception of the Ising model) in the nonuniqueness regime of the infinite $\Delta$-regular tree. We also find efficient counting and sampling algorithms for proper $q$-colorings of random $\Delta$-regular bipartite graphs when $q$ is sufficiently small as a function of $\Delta$.

We give an FPTAS and an efficient sampling algorithm for the high-fugacity hard-core model on bounded-degree bipartite expander graphs and the low-temperature ferromagnetic Potts model on bounded-degree expander graphs. The results apply, for example, to random (bipartite) Δ-regular graphs, for which no efficient algorithms were known for these problems (with the exception of the Ising model) in the non-uniqueness regime of the infinite Δ-regular tree.

Aharoni and Berger conjectured that in any bipartite multigraph that is properly edge-colored by $n$ colors with at least $n + 1$ edges of each color there must be a matching that uses each color exactly once. In this paper we consider the same question without the bipartiteness assumption. We show that in any multigraph with edge multiplicities $o(n)$ that is properly edge-colored by $n$ colors with at least $n + o(n)$ edges of each color there must be a matching of size $n-O(1)$ that uses each color at most once.

In this paper we consider spectral extremal problems for hypergraphs. We give two general criteria under which such results may be deduced from “strong stability” forms of the corresponding (pure) extremal results. These results hold for the $\alpha$-spectral radius defined using the $\alpha$-norm for any $\alpha>1$; the usual spectral radius is the case $\alpha=2$. Our results imply that any hypergraph Turán problem which has the stability property and whose extremal construction satisfies some rather mild continuity assumptions admits a corresponding spectral result. A particular example is to determine the maximum $\alpha$-spectral radius of any 3-uniform hypergraph on $n$ vertices not containing the Fano plane, when $n$ is sufficiently large. Another is to determine the maximum $\alpha$-spectral radius of any graph on $n$ vertices not containing some fixed color-critical graph, when $n$ is sufficiently large; this generalizes a theorem of Nikiforov who proved stronger results in the case $\alpha=2$. We also obtain an $\alpha$-spectral version of the Erdös--Ko--Rado theorem on $t$-intersecting $k$-uniform hypergraphs.

Let H be a k-graph on n vertices, with minimum codegree at least n/k + cn for some fixed c > 0. In this paper we construct a polynomial-time algorithm which finds either a perfect matching in H or a certificate that none exists. This essentially solves a problem of Karpinski, Rucinski and Szymanska, who previously showed that this problem is NP-hard for a minimum codegree of n/k - cn. Our algorithm relies on a theoretical result of independent interest, in which we characterise any such hypergraph with no perfect matching using a family of lattice-based constructions.

Let $D$ be a digraph. The chromatic number $\chi(D)$ of $D$ is the smallest number of colors needed to color the vertices of $D$ such that every color class induces an acyclic subdigraph. The girth of $D$ is the length of a shortest directed cycle, or $\infty$ if $D$ is acyclic. Let $G(k,n)$ be the maximum possible girth of a digraph on $n$ vertices with $\chi(D) > k$. It is shown that $G(k,n) \ge \left\lfloor n^{1/k}\right\rfloor$ and $G(k,n) \le (3\log_2 n \log_2\log_2 n)^{1-1/k} n^{1/k}$ for $n \ge 3$ and $k \ge 2$.

We show that for each $\beta > 0$, every digraph G of sufficiently large order n whose outdegree and indegree sequences $d_1^+ \leq \cdots \leq d_n^+$ and $d_1^- \leq \cdots \leq d_n^-$ satisfy $d_i^+, d_i^- \geq \min{\{i + \beta n, n/2\}}$ is Hamiltonian. In fact, we can weaken these assumptions to (i) $d_i^+ \geq \min{\{i + \beta n, n/2\}}$ or $d^-_{n - i - \beta n} \geq n-i$, (ii) $d_i^- \geq \min{\{i + \beta n, n/2\}}$ or $d^+_{n - i - \beta n} \geq n-i$, and still deduce that G is Hamiltonian. This provides an approximate version of a conjecture of Nash-Williams from 1975 and improves a previous result of Kühn, Osthus, and Treglown.

Let $\mathcal{F}$ be a k‐uniform set system defined on a ground set of size n with no singleton intersection; i.e., no pair $A,B\in\mathcal{F}$ has $|A\cap B|=1$. Frankl showed that $|\mathcal{F}|\leq\binom{n-2}{k-2}$ for $k\geq4$ and n sufficiently large, confirming a conjecture of Erdo˝s and Sós. We determine the maximum size of $\mathcal{F}$ for $k=4$ and all n, and also establish a stability result for general k, showing that any $\mathcal{F}$ with size asymptotic to that of the best construction must be structurally similar to it.

A set system is L-intersecting if any pairwise intersection size lies in L, where L is some set of s nonnegative integers. The celebrated Frankl--Ray-Chaudhuri--Wilson theorems give tight bounds on the size of an L-intersecting set system on a ground set of size n. Such a system contains at most $\binom{n}{s}$ sets if it is uniform and at most $\sum_{i=0}^s \binom{n}{i}$ sets if it is nonuniform. They also prove modular versions of these results. We consider the following extension of these problems. Call the set systems $\mathcal{A}_1,\ldots,\mathcal{A}_k$ {\em L-cross-intersecting} if for every pair of distinct sets A,B with $A \in \mathcal{A}_i$ and $B \in \mathcal{A}_j$ for some $i \neq j$ the intersection size $|A \cap B|$ lies in L. For any k and for n > n 0 (s) we give tight bounds on the maximum of $\sum_{i=1}^k |\mathcal{A}_i|$. It is at most $\max\, \{k\binom{n}{s}, \binom{n}{\lfloor n/2 \rfloor}\}$ if the systems are uniform and at most $ \max\, \{k sum_{i=0}^s \binom{n}{i} , (k-1) \sum_{i=0}^{s-1} \binom{n}{i} + 2^n\}$ if they are nonuniform. We also obtain modular versions of these results. Our proofs use tools from linear algebra together with some combinatorial ideas. A key ingredient is a tight lower bound for the rank of the inclusion matrix of a set system. The s*-inclusion matrix of a set system $\mathcal{A}$ on [n] is a matrix M with rowsindexed by $\mathcal{A}$ and columns by the subsets of [n] of size at most s, where if $A \in \mathcal{A}$ and $B \subset [n]$ with $|B| \leq s$, we define M AB to be 1 if $B \subset A$ and 0 otherwise. Our bound generalizes the well-known result that if $|\mathcal{A}| < 2^{s+1}$, then M has full rank $|\mathcal{A}|$. In a combinatorial setting this fact was proved by Frankl and Pach in the study of null t-designs; it can also be viewed as determining the minimum distance of the Reed--Muller codes.