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.

Abstract. A [Formula: see text]-graph system [Formula: see text] is a family of not necessarily distinct [Formula: see text]-graphs on the same [Formula: see text]-vertex set [Formula: see text], and a [Formula: see text]-graph [Formula: see text] on [Formula: see text] is said to be [Formula: see text]-transversal provided that there exists an injection [Formula: see text] such that [Formula: see text] for all [Formula: see text]. We show that given [Formula: see text], sufficiently large [Formula: see text], and an [Formula: see text]-vertex [Formula: see text]-graph system [Formula: see text], if [Formula: see text] for each [Formula: see text], then there exists an [Formula: see text]-transversal tight Hamilton cycle. This extends the result of Rödl, Ruciński, and Szemerédi [ Combinatorica, 28 (2008), pp. 229–260] on single [Formula: see text]-graphs.

Abstract. We prove that for [Formula: see text] with [Formula: see text] and [Formula: see text], there exist [Formula: see text] and [Formula: see text] such that for every [Formula: see text], every [Formula: see text]-vertex graph [Formula: see text] with [Formula: see text] and [Formula: see text] contains an [Formula: see text]th power of a Hamilton cycle. We also show that the minimum degree condition is asymptotically sharp for [Formula: see text] and the [Formula: see text] case was recently conjectured by Staden and Treglown.

Given 1 ≤ 𝓁 < k and δ ≥ 0, let PM(k,𝓁,δ) be the decision problem for the existence of perfect matchings in n-vertex k-uniform hypergraphs with minimum 𝓁-degree at least δ binom(n-𝓁,k-𝓁). For k ≥ 3, the decision problem in general k-uniform hypergraphs, equivalently PM(k,𝓁,0), is one of Karp’s 21 NP-complete problems. Moreover, for k ≥ 3, a reduction of Szymańska showed that PM(k, 𝓁, δ) is NP-complete for δ < 1-(1-1/k)^{k-𝓁}. A breakthrough by Keevash, Knox and Mycroft [STOC '13] resolved this problem for 𝓁 = k-1 by showing that PM(k, k-1, δ) is in P for δ > 1/k. Based on their result for 𝓁 = k-1, Keevash, Knox and Mycroft conjectured that PM(k, 𝓁, δ) is in P for every δ > 1-(1-1/k)^{k-𝓁}. In this paper it is shown that this decision problem for perfect matchings can be reduced to the study of the minimum 𝓁-degree condition forcing the existence of fractional perfect matchings. That is, we hopefully solve the "computational complexity" aspect of the problem by reducing it to a well-known extremal problem in hypergraph theory. In particular, together with existing results on fractional perfect matchings, this solves the conjecture of Keevash, Knox and Mycroft for 𝓁 ≥ 0.4k.

We consider a semantic cipher system, in which we protect only the semantic information of the source. The optimal tradeoff is characterized among the coding rate, the secret key rate, the semantic information leakage rate, the source reconstruction distortion, and the semantic distortion. It is shown that an efficient key with a small size suffices to protect the semantic information.

For all integers $k,d$ such that $k \geq 3$ and $k/2\leq d \leq k-1$, let $n$ be a sufficiently large integer ( which may not be divisible by $k$ ) , and let $s\le \lfloor n/k\rfloor-1$. We show that if $H$ is a $k$-uniform hypergraph on $n$ vertices with $\delta_{d}(H)>\binom{n-d}{k-d}-\binom{n-d-s+1}{k-d}$, then $H$ contains a matching of size $s$. This improves a recent result of Lu, Yu, and Yuan and also answers a question of Kühn, Osthus, and Townsend. In many cases, our result can be strengthened to $s\leq \lfloor n/k\rfloor$, which then covers the entire possible range of $s$. On the other hand, there are examples showing that the result does not hold for certain $n, k, d$, and $s= \lfloor n/k\rfloor$.

A k-graph H is called (p, μ)-dense if for all not necessarily disjoint sets A1, …, Ak ⊆ V(H) we have e(A1, …, Ak) ≥ p|A1| ⃛ |Ak| – μ|V(H)|k. This is believed to be the weakest form of quasi-randomness in k-graphs and also known as linear quasi-randomness. In this paper we show that for ℓ < k satisfying (k – ℓ) ∤ k, (p, μ)-denseness plus a minimum (ℓ + 1)-vertex-degree αnk–ℓ–1 guarantees Hamilton ℓ-cycles, but requiring a minimum ℓ-vertex-degree Ω(nk–ℓ) instead is not sufficient. This answers a question of Lenz–Mubayi–Mycroft and characterizes the triples (k, ℓ, d) such that degenerate choices of p and α force ℓ-Hamiltonicity. We actually prove a general result on ℓ-Hamiltonicity in quasi-random k-graphs, assuming a minimum vertex degree and essentially that every two ℓ-sets can be connected by a constant length ℓ-path. This result reduces the ℓ-Hamiltonicity problem to the study of the connection property. Moreover, we note that our proof can be turned into a deterministic polynomial-time algorithm that outputs the Hamilton ℓ-cycle. Our proof uses the lattice-based absorption method in the non-standard way and is the first one that embeds a nonlinear Hamilton cycle in linear quasi-random k-graphs.

We investigate the emergence of spanning structures in sparse pseudo-random k-uniform hypergraphs, using the following comparatively weak notion of pseudorandomness. A k-uniform hypergraph H on n vertices is called (p, α, ε)-pseudo-random if for all not necessarily disjoint sets A1, …, Ak ⊂ V (H) with |A1|···|Ak| > αnk we have e(A1, …, Ak) = (1 ± ε)p|A1|···|Ak|. For any linear k-uniform F we provide a bound on α = α(n) in terms of p = p(n) and F, such that (under natural divisibility assumptions on n) any (p, α, o(1))-pseudo-random n-vertex H with a mild minimum degree condition contains an F-factor. The approach also enables us to establish the existence of loose Hamilton cycles in sufficiently pseudo-random hypergraphs and all results imply corresponding bounds for stronger notions of hypergraph pseudo-randomness such as jumbledness or large spectral gap. As a consequence of our results, perfect matchings appear at α = o(pk) while loose Hamilton cycles appear at α = o(pk–1). This extends the works of Lenz–Mubayi, and Lenz–Mubayi–Mycroft who studied the analogous problems in the dense setting.

A configuration is a finite set of points in the plane. Two configurations A and B have the same order type if there exists a bijection between them preserving the orientation of every ordered triple. We investigate extremal and probabilistic problems related to configurations in general position. We focus on problems involving forbidden configurations or monotone/hereditary properties. Thus, we typically have a given configuration B and we consider the property of being “B-free”: a configuration A is B-free if no subset of points of A has the same order type as B. We prove a significant bound on the number of B-free N-point configurations contained in the m × m grid [m]2 for arbitrary configurations B. We consider random N-point configurations UN in the unit square, in which each of the N points is chosen uniformly at random and independently of all other points. The above-mentioned enumeration result for B-free configurations in the grid is then used to prove strong bounds for the probability that the random set UN should be B-free for any given B. We also investigate the threshold function N0 = N0(n) for the property that UN should be n-universal, that is, should contain all n-point configurations in general position. As it turns out, N0 = N0(n) is doubly exponential in n; we prove that log log N0 = Θ(n). Our arguments are mostly geometric and combinatorial, with the recent container method playing an important role. Also important for us is how large a grid one needs to consider when representing n-point configurations in general position.

We prove a new upper bound for the minimum $d$-degree threshold for perfect matchings in $k$-uniform hypergraphs when $d

Suppose $k\nmid n$ and $H$ is an $n$-vertex $k$-uniform hypergraph. A near perfect matching in $H$ is a matching of size $\lfloor n/k\rfloor$. We give a divisibility barrier construction that prevents the existence of near perfect matchings in $H$. This generalizes the divisibility barrier for perfect matchings. We give a conjecture on the minimum $d$-degree threshold forcing a (near) perfect matching in $H$ which generalizes a well-known conjecture on perfect matchings. We also verify our conjecture for various cases. Our proof makes use of the lattice-based absorbing method that we used recently to solve two other problems on matching and tilings for hypergraphs.