betaFeedback

WorksMathematics

Spanning subhypergraphs with degree constraints

Abstract

An old result of Tutte states that any dd-regular graph contains a spanning subgraph in which every vertex has degree kk or k+1k+1, for every 1≤k≤d1\leq k\leq d. We generalize this statement to hypergraphs, showing, for example, that every 33-uniform dd-regular hypergraph contains a subgraph in which all degrees are k,k+1k, k+1 or k+2k+2, for every 1≤k≤d1\leq k\leq d. This statement is best possible in the sense that the corresponding statement with only two allowed consecutive values is not true. We provide generalizations of this statement to higher uniformities and discuss several open problems.

Introduction

Many classical problems in graph theory can be formulated as questions about finding a subgraph with prescribed degree conditions. For example, two basic theorems of graph theory, Hall’s marriage theorem [11] and Tutte’s matching theorem [22], give necessary and sufficient conditions for graphs to have a perfect matching, which is a spanning subgraph in which all degrees are one. If one asks the spanning subgraph to be 2-regular instead of 1-regular, then Petersen’s theorem [16] guarantees that such subgraphs can be found in all even-regular graphs.

The general framework for studying questions about subgraphs with prescribed degrees was introduced by Lovász [14, 15]. Suppose that every vertex v∈V(G)v \in V(G) is given a list of allowed degrees H(v)H(v). Under which conditions on the lists and on GG does there exist a subgraph G′⊆GG' \subseteq G for which deg⁡G′v∈H(v)\deg_{G'} v \in H(v) for all v∈V(G)v \in V(G)? This general problem was studied in a variety of contexts, including [1, 7, 8, 19].

Regular graphs have particularly nice properties in this context. For example, Hall’s theorem shows that regular bipartite graphs always have perfect matchings, and Petersen’s theorem shows that even-regular graphs always have 2-factors. Moreover, as Tutte [23] showed, any regular graph has a spanning subgraph in which all degrees are either 1 or 2. There is no hope of proving such statements without some regularity assumption, since the graph may be a star.

In this paper, we focus on a version of this problem for regular hypergraphs. The natural way to generalize Tutte’s theorem is to ask for which values of tt and rr it is true that any regular rr-uniform hypergraph H\mathcal{H} contains a spanning subhypergraph all of whose degrees are in the set {1,2,…,t}\{1, 2, \ldots, t\}.

The first interesting case of this question concerns regular 3-uniform hypergraphs, where the answer turns out to be t=3t=3. This is tight, as the example of the Fano plane shows.

Theorem 1.1. Let H\mathcal{H} be a nonempty regular 33-uniform hypergraph. Then, there is a spanning subhypergraph C⊆H\mathcal{C} \subseteq\mathcal{H} such that deg⁡Cv∈{1,2,3}\deg_{\mathcal{C}} v \in\{1,2,3\} for all v∈V(H)v \in V(\mathcal{H}).

A natural way to extend the above theorem is to ask about higher uniformities. In this direction, for r≥2r \ge2, we define f(r)f(r) to be the smallest value of tt for which any nonempty regular rr-uniform hypergraph contains a spanning subhypergraph with all degrees between 11 and tt. Tutte’s theorem shows that f(2)=2f(2)=2 and Theorem 1.1 shows that f(3)=3f(3)=3. The following result determines the asymptotics of f(r)f(r) for growing rr.

Theorem 1.2. Let r≥2r \ge2 be an integer, and let H\mathcal{H} be a nonempty regular rr-uniform hypergraph. Then, there exists a spanning subhypergraph C⊆H\mathcal{C} \subseteq\mathcal{H} such that 1≤deg⁡Cv≤100log⁡r1 \le\deg_{\mathcal{C}} v \le100\log r. In other words f(r)≤100log⁡rf(r) \le100\log r.

Planken and Ueckerdt [17] have constructed examples which give f(r)≥⌊log⁡2(r+1)⌋f(r) \ge\lfloor\log_2(r+1)\rfloor, showing that Theorem 1.2 is tight up to a constant factor.

Further, note that we always have f(r+1)≥f(r)f(r+1) \ge f(r). To see this, suppose that H\mathcal{H} is an rr-uniform hypergraph without a spanning subhypergraph all of whose degrees are in {1,…,t}\{1,\ldots,t\}, for some tt. Then, one can construct an (r+1)(r+1)-uniform hypergraph H′\mathcal{H}' with the same property. This can be done as follows: denote S=V(H)S=V(\mathcal{H}) and add a new vertex outside SS to each edge of H\mathcal{H}. Then, add further vertices and edges disjoint from SS until one obtains a regular (r+1)(r+1)-uniform hypergraph H′\mathcal{H}'. If H′\mathcal{H}' has a spanning subhypergraph all of whose degrees are between 11 and tt, then intersecting the edges of this hypergraph with SS would give a subhypergraph of H\mathcal{H} with the same property, which we assumed did not exist.

One can also attempt to generalize Theorem 1.1 in a different direction. To explain how, let us go back to graphs for a moment, where we have already mentioned that any regular graph contains a {1,2}\{1,2\}-factor. An even stronger statement is true: Tutte showed that for any d≥k≥1d \ge k \ge1, any dd-regular graph contains a {k,k+1}\{k,k+1\}-factor (see also [20] for a very nice proof). Our next result shows that a similar statement is true for 33-uniform hypergraphs.

Theorem 1.3. Let d≥k≥1d \ge k \ge1 be integers, and let H\mathcal{H} be a dd-regular 33-uniform hypergraph. Then, there is a spanning subhypergraph C⊆H\mathcal{C} \subseteq\mathcal{H} such that deg⁡Cv∈{k,k+1,k+2}\deg_{\mathcal{C}} v \in\{k,k+1,k+2\} for all v∈V(H)v \in V(\mathcal{H}).

If one tries to extend this result to higher uniformities, one encounters a significantly different situation from Theorem 1.2. To be precise, for r≥2r \ge2, we define g(r)g(r) to be the smallest value of tt such that for any d≥k≥1d \ge k \ge1 and any dd-regular rr-uniform hypergraph H\mathcal{H}, there exists a spanning subhypergraph C⊆H\mathcal{C} \subseteq\mathcal{H} such that for every vertex v∈V(H)v \in V(\mathcal{H}) we have deg⁡Cv∈{k,k+1,…,k+t−1}\deg_{\mathcal{C}} v \in\{k,k+1,\ldots,k+t-1\}. Again, Tutte’s theorem [24] and Theorem 1.3 show that g(2)=2g(2)=2 and g(3)=3g(3)=3. Observe that, using the same argument as in the case of f(r)f(r), one can show that gg is a nondecreasing function, i.e. that g(r+1)≥g(r)g(r+1) \ge g(r) for all rr. The following result does not describe the precise asymptotics of g(r)g(r), but shows that for large rr it is much larger than f(r)f(r).

Theorem 1.4. For any r≥3r \ge3, we have ⌊r/2⌋≤g(r)≤2r−3\lfloor\sqrt{r/2}\rfloor\le g(r) \le2r-3.

Note that the upper bound g(r)≤2r−3g(r) \le2r-3 immediately implies Theorems 1.1 and 1.3 by setting r=3r=3. Thus, we will only focus on proving Theorems 1.2 and 1.4. Our proofs of the upper bounds in the above theorems are algorithmic in nature, meaning that they provide an efficient procedure to find a subhypergraph with required degree conditions.

The paper [10] describing an AI-generated proof of the Komlós Conjecture was posted in the arXiv essentially simultaneously with our manuscript. Corollary 1.2 in that paper implies that the hereditary discrepancy of any set system in which every point belongs to at most rr sets is smaller than 32πr3\sqrt{2\pi r}. Combining it with the known relation between the linear discrepancy and the hereditary discrepancy of set systems (see, e.g., [4], Theorem 13.3.2) this implies that the function g(r)g(r) satisfies

g(r)≤62πr.g(r) \le6\sqrt{2\pi r}.

This improves the bound in Theorem 1.4 for all r≥60r \ge60, and shows that for large rr, g(r)=Θ(r)g(r) = \Theta(\sqrt{r}). The proof in [10] does not provide an efficient algorithm.

One can also extend Theorem 1.4 to arbitrary sets of allowed degrees. Namely, if H\mathcal{H} is a dd-regular rr-uniform hypergraph and every vertex vv is assigned a list H(v)H(v) of more than ⌈r−1rd⌉\left\lceil\frac{r-1}{r}d \right\rceil allowed degrees between 00 and dd, then a simple modification of the Shirazi-Verstraëte argument from [19] shows that there is a spanning subhypergraph H′⊆H\mathcal{H}' \subseteq\mathcal{H} for which deg⁡H′v∈H(v)\deg_{\mathcal{H}'}v \in H(v) for all vertices v∈V(H)v \in V(\mathcal{H}). This proof is based on the Combinatorial Nullstellensatz [3] and so it does not provide an efficient algorithm for finding this subhypergraph.

During the work on this paper we also found a proof of the weaker result that for r=3r = 3 one can find a subhypergraph with all degrees in {1,2,3,4}\{1,2,3,4\}, using a completely different argument that is ultimately based on topological methods. For completeness, we present this different perspective as well.

Related work

A spanning subhypergraph C⊆H\mathcal{C} \subseteq\mathcal{H} in which all degrees are between 11 and tt is closely related to the notion of tt-shallow hitting sets introduced by Keszegh and Pálvölgyi [12]. They were initially interested in the polycolorability of geometric hypergraphs, where the question is to determine for a given rr-uniform hypergraph H\mathcal{H} (usually coming from a geometric setting) the maximum kk for which vertices of H\mathcal{H} can be colored using kk colors such that every edge of H\mathcal{H} receives all colors. A natural way to construct such a coloring is to find a set S⊆V(H)S \subseteq V(\mathcal{H}) which intersects every hyperedge in at least 11 and at most tt elements. Setting these vertices aside as one color class, we are then left with a hypergraph in which all edges have size at least r−tr-t, and if one can iterate this procedure, it is possible to obtain a coloring using ⌊r/t⌋\lfloor r/t \rfloor colors in which every hyperedge contains all colors.

A set SS intersecting every hyperedge in at least 11 and at most tt vertices is then called a tt-shallow hitting set (see [17]). A natural dual notion is a set of edges F⊆E(H)F \subseteq E(\mathcal{H}) which covers every vertex at least once and at most tt times. We call such an FF a tt-shallow hitting edge set.

Planken and Ueckerdt [17] have studied when tt-shallow hitting edge sets exist in a variety of settings, including the setting of regular rr-uniform hypergraphs. In particular, they have shown that f(r)≥⌈log⁡2(r+1)⌉f(r) \ge\lceil\log_2(r+1) \rceil and f(r)≤O(r)f(r) \le O(r). Theorem 1.2 improves the upper bound and shows that f(r)≤O(log⁡r)f(r) \le O(\log r), thus obtaining a bound which is tight up to a constant factor.

Shallow hitting edge sets seem to be useful for finding other spanning structures in dense hypergraphs, see e.g. [13].

Further questions

Let us now discuss some questions in similar spirit that we could not answer precisely.

Firstly, it seems possible that the conclusion of Theorem 1.1 could be strengthened if one restricts to tripartite hypergraphs (observe that the Fano plane, which shows the tightness of Theorem 1.1, is not tripartite).

Conjecture 1.5. Let H\mathcal{H} be a nonempty regular tripartite 33-uniform hypergraph. Then, H\mathcal{H} contains a spanning subhypergraph whose vertices each have degree either 11 or 22.

Although we are unable to show this statement in general, as partial evidence towards it we provide a simple argument based on Seymour’s work [18] that proves the conjecture for 3-regular tripartite hypergraphs.

Secondly, recall that Theorem 1.1 shows that any regular 3-uniform hypergraph has a spanning subgraph all of whose degrees are in {1,2,3}\{1,2,3\}. What can be said about regular 4-uniform hypergraphs? What is the value of f(4)f(4)? We know that f(4)≤2⋅4−3=5f(4) \leq2 \cdot4 - 3 = 5 from Theorem 1.4 and f(4)≥f(3)=3f(4) \geq f(3) = 3 by the monotonicity properties of ff.

While we can say little about this question in general, we note that an old result of Thomassen shows that any 4-regular 4-uniform hypergraph has property B (see Theorem 5.1 in [21]). The dual of this statement says that the edge set of any 4-regular 4-uniform hypergraph H\mathcal{H} can be partitioned into E(H)=E1∪E2E(\mathcal{H}) = E_1 \cup E_2, where each vertex is covered between 1 and 3 times. In other words, there exists a spanning subhypergraph C⊆H\mathcal{C} \subseteq\mathcal{H} for which deg⁡Cv∈{1,2,3}\deg_{\mathcal{C}} v \in\{1,2,3\}. This suggests that we perhaps have f(4)=3f(4) = 3, although this may be too specific a case to be an indicator of general conclusions.

Paper organization. We prove the upper bound from Theorem 1.4 in Section 2, and we note that this immediately implies Theorem 1.1 and Theorem 1.3. We also prove Theorem 1.2 in Section 2. Then we present an argument proving Conjecture 1.5 for 3-regular hypergraphs in Section 3. Our alternative argument for the weaker version of Theorem 1.1 is given in the appendix.

Proofs of Theorems 1.2 and 1.4

In this section, we show that every dd-regular rr-uniform hypergraph contains a spanning subhypergraph with all degrees in the set {k,…,k+2r−4}\{k,\ldots,k+2r-4\}, for any k≤dk \leq d. Let us now briefly outline the proof ideas needed for this result. Our proof of the upper bound g(r)≤2r−3g(r) \leq2r-3 is inspired by the proof of the Beck-Fiala theorem [5], which states that if a set system S\mathcal{S} on the ground set XX has the property that no element is contained in more than nn sets, then one can color the elements of XX red and blue so that the difference between the number of red and blue elements in any set A∈SA \in\mathcal{S} is at most 2n−12n-1. The proof is based on the floating-variables method, in which every element v∈Xv \in X is assigned a real number xv∈[−1,1]x_v \in[-1,1], with all numbers starting at 0. Then, the variables are gradually changed with the goal of each of them reaching either 1 (at which point we color the element red and do not change xvx_v further) or −1-1 (at which point we color the element blue and do not change xvx_v further). Throughout this process, one maintains ∑v∈Axv=0\sum_{v \in A} x_v = 0 for all A∈SA \in\mathcal{S}, in order to ensure that the number of red and blue elements is balanced in each set. For the full proof of the Beck-Fiala theorem, see e.g. Section 13 of [4].

Our proof of Theorem 1.4 proceeds along very similar lines, and we explain it for 3-uniform hypergraphs for the sake of concreteness. The goal is to show that any dd-regular hypergraph contains a spanning subhypergraph with degrees in the set {k,k+1,k+2}\{k,k+1,k+2\}, if d≥kd \geq k. We begin by assigning a variable xe∈[0,1]x_e \in[0,1] to every edge e∈E(H)e \in E(\mathcal{H}), starting at xe=k+1dx_e = \frac{k+1}{d} (observe that if d=kd = k or d=k+1d = k+1, then the statement is trivial, so we may assume d≥k+2d \geq k+2, so 0<xe<10 < x_e < 1). We proceed to move these values until one of them reaches either 0 or 1, at which point the edge is either excluded or included in our subhypergraph C\mathcal{C} and the variable xex_e is not moved further. As before, throughout this process of moving the variables, we ensure that ∑e∋vxe=k+1\sum_{e \ni v} x_e = k+1 for all vertices v∈V(H)v \in V(\mathcal{H}).

As long as the number of free variables coming from edges with xe∈(0,1)x_e \in(0,1) is larger than the number of constraints coming from vertices, we can find a direction to move the variables until one of them reaches either 0 or 1. Crucially, in order to reduce the number of constraints as the process progresses, we observe that any vertex with two nonfixed edges remaining will, no matter what values are assigned to these nonfixed edges, have between kk and k+2k+2 incident edges at the end. Thus, as soon as all but two edges incident to a vertex are fixed, we can forget about the constraint corresponding to this vertex. As a consequence of a simple double counting, the only place where this process can get stuck is if we are left with a 3-regular hypergraph, from which we can then choose the remaining edges directly by a simple procedure. Finally, Theorem 1.2 can be derived from the above statement using a simple application of the Lovász Local Lemma.

This method is quite robust, and it allows for the assumptions to be significantly relaxed. For example, it is sufficient to assume that the hypergraphs in question have rank rr instead of uniformity rr (in other words, we can allow for edges of cardinality smaller than rr). Additionally, the only place where the regularity assumption is used is to construct a fractional spanning subgraph with all fractional degrees k+r−2k+r-2, which is an assignment of weights we∈[0,1]w_e \in[0,1] to all edges e∈E(H)e \in E(\mathcal{H}) satisfying ∑e∋vwe=k+r−2\sum_{e\ni v} w_e = k+r-2 for all v∈V(H)v \in V(\mathcal{H}). Hence, Theorems 1.1–1.4 apply to all hypergraphs with such a fractional spanning subgraph, or equivalently, all rr-uniform hypergraphs with a perfect fractional matching in which all weights are at most 1/(k+r−2)1/(k+r-2).

Proof of the upper bound in Theorem 1.4. Given H\mathcal{H}, finding a subhypergraph C⊆H\mathcal{C} \subseteq\mathcal{H} that witnesses g(r)≤2r−3g(r) \le2r-3 for H\mathcal{H} corresponds to finding a vector of weights x∈{0,1}E(H)x \in\{0,1\}^{E(\mathcal{H})} such that for every vertex v∈V(H)v \in V(\mathcal{H}) we have ∑e∋vxe∈{k,…,k+2r−4}\sum_{e\ni v} x_e \in\{k,\ldots,k+2r-4\} (where xe=1x_e=1 means that the edge ee is included in the cover C\mathcal{C} and xe=0x_e=0 means that it is not). Note that we may assume that d≥k+2r−3d \ge k+2r-3, as otherwise taking C=H\mathcal{C}=\mathcal{H} already satisfies the needed conditions.

We find these values using the following algorithm. We start by setting xe=k+r−2dx_e=\frac{k+r-2}{d} for each e∈E(H)e \in E(\mathcal{H}) and we will vary these variables until we arrive at a {0,1}\{0,1\}-valued vector satisfying ∑e∋vxe∈{k,…,k+2r−4}\sum_{e\ni v}x_e \in\{k,\ldots,k+2r-4\} for each v∈V(H)v \in V(\mathcal{H}).

The algorithm maintains a partition of the edge set into active and fixed edges, E(H)=Ea∪EfE(\mathcal{H})=E_a\cup E_f, and a partition of the vertex set into safe and unsafe vertices, V(H)=Vs∪VuV(\mathcal{H})=V_s\cup V_u.

The active edges will be the ones having 0<xe<10<x_e<1, and these values will be changed throughout the rest of the algorithm. On the other hand, when a variable xex_e reaches value 00 or 11, it becomes fixed and remains fixed for the rest of the process. If a vertex vv has at most r−1r-1 active incident edges, then we declare vv to be safe until the end of the algorithm.

Throughout the algorithm, we maintain the following set of constraints.

∑e∋vxe=k+r−2 for every v∈Vu and 0≤xe≤1 for every e∈E(H).\sum_{e\ni v} x_e = k+r-2 \text{ for every } v \in V_u \text{ and } 0 \le x_e \le1 \text{ for every } e \in E(\mathcal{H}).

In a general step of the algorithm, as long as the number of active edges exceeds the number of vertex constraints, i.e. as long as ∣Ea∣>∣Vu∣|E_a|>|V_u|, we do the following. We find a solution to the system of equations

∑e∋ve∈Eaye=0 for every v∈Vu.\sum_{\substack{e\ni v\\e\in E_a}} y_e=0 \text{ for every } v\in V_u.

If ∣Ea∣>∣Vu∣|E_a|>|V_u|, this system is underdetermined and so there exists a nontrivial solution (ye)e∈Ea(y_e)_{e\in E_a} to this system. We then take this solution, define ye=0y_e=0 for all fixed edges and update the variables xe↦xe+λyex_e\mapsto x_e+\lambda y_e for some real number λ\lambda. Observe that the new values of xex_e still satisfy ∑e∋vxe=k+r−2\sum_{e\ni v}x_e=k+r-2 for every v∈Vuv\in V_u. Moreover, to choose the value of λ\lambda, we start at λ=0\lambda=0 and increase it until one (or more) of the variables xex_e becomes 00 or 11. At this point, we fix xex_e, we check if there is any vertex vv which becomes safe, and proceed to the next step of the algorithm. The algorithm terminates when ∣Ea∣=∣Vu∣|E_a|=|V_u|.

Let us make a couple of observations about this algorithm. First of all, we observe that if a vertex vv is declared to be safe, then no matter whether the remaining active edges incident to vv are included in the cover or not, vv will have degree between kk and k+2r−4k+2r-4 in the cover. To see this, we argue based on how many edges incident to vv have been fixed with xe=1x_e=1, at the moment when vv is declared to be safe. If all edges incident to vv are fixed when vv is declared safe, then vv will surely have degree k+r−2k+r-2 in the final subhypergraph. So, suppose that this is not the case.

Since at least one and at most r−1r-1 active edges are incident to vv, we have 0<∑e∋ve∈Eaxe<r−10<\sum_{\substack{e\ni v\\e\in E_a}}x_e<r-1. Moreover, this quantity is an integer, and thus ∑e∋ve∈Efxe=k+r−2−∑e∋ve∈Eaxe∈{k,…,k+r−3}\sum_{\substack{e\ni v\\e\in E_f}}x_e=k+r-2-\sum_{\substack{e\ni v\\e\in E_a}}x_e\in\{k,\ldots,k+r-3\}. In other words, between kk and k+r−3k+r-3 fixed edges containing vv have xe=1x_e=1. Thus, no matter what happens with the remaining r−1r-1 edges, vv will have degree between kk and k+2r−4k+2r-4 in the resulting subhypergraph.

Let H′\mathcal{H}' be the hypergraph of rank at most rr on the vertex set VuV_u, with edges given by e∩Vue\cap V_u for e∈Eae\in E_a. Let us show that when the algorithm terminates with ∣Ea∣=∣Vu∣|E_a|=|V_u|, the hypergraph H′\mathcal{H}' is rr-regular and rr-uniform. Note that every vertex of VuV_u is incident to at least rr edges of EaE_a, so the average degree is at least rr. On the other hand, the average degree of H′\mathcal{H}' can be calculated as follows:

dˉ(H′)=1∣Vu∣∑e∈Ea∣e∩Vu∣≤r∣Ea∣∣Vu∣≤r.\bar{d}(\mathcal{H}')=\frac{1}{|V_u|}\sum_{e\in E_a}|e\cap V_u|\leq\frac{r|E_a|}{|V_u|}\leq r.

Hence, we have the equality all the way through, meaning that each edge of EaE_a is completely contained in VuV_u and that H′\mathcal{H}' is an rr-regular, rr-uniform hypergraph.

So, when the algorithm terminates, we have obtained a partial subhypergraph C0C_0 consisting of those fixed edges having xe=1x_e=1. Let fv=deg⁡C0vf_v=\deg_{C_0}v denote the degree already assigned to the vertex vv. It can be computed from the equation fv+∑e∋ve∈Eaxe=k+r−2f_v+\sum_{\substack{e\ni v\\e\in E_a}}x_e=k+r-2.

To complete the proof, we need to decide which of the remaining active edges we add to the set C0C_0 to form the final hypergraph CC having the property that deg⁡Cv∈{k,…,k+2r−4}\deg_C v\in\{k,\ldots,k+2r-4\}. We do that as follows: if an edge has xe≥1/2x_e\geq1/2 when the above algorithm terminates, we include it in the final hypergraph CC, and otherwise we leave it out.

The number of additional edges incident to vv differs from ∑e∋ve∈Eaxe\sum_{\substack{e\ni v\\e\in E_a}}x_e by at most r/2r/2, since the rounding of every edge contributes at most 1/21/2 to the difference. Hence, the degree of vv in the final hypergraph CC satisfies

∣deg⁡Cv−(k+r−2)∣≤∣deg⁡Cv−fv−∑e∋ve∈Eaxe∣≤r/2<r−1.\left|\deg_C v-(k+r-2)\right|\leq\left|\deg_C v-f_v-\sum_{\substack{e\ni v\\e\in E_a}}x_e\right|\leq r/2<r-1.

Since deg⁡Cv\deg_C v is an integer, we conclude deg⁡Cv∈{k,…,k+2r−4}\deg_C v\in\{k,\ldots,k+2r-4\}, thus completing the proof. □

We now discuss the proof of the lower bound in Theorem 1.4. It is a simple consequence of the following well-known lower bound construction in discrepancy theory (see e.g. Corollary 2.10 in [6]).

Theorem 2.1. Let H\mathcal{H} be a projective plane of order qq, i.e. a (q+1)(q+1)-uniform (q+1)(q+1)-regular hypergraph on the ground set [q2+q+1][q^2+q+1] for which each pair of elements is contained together in exactly one set. Then, no matter how the vertices of [q2+q+1][q^2+q+1] are colored red and blue, there is an edge of H\mathcal{H} which contains at least q\sqrt{q} more vertices of one color than the other.

Recall that the dual of a hypergraph H\mathcal{H} is the hypergraph with vertex set E(H)E(\mathcal{H}) and edge set {{e∋v}:v∈V(H)}\{\{e\ni v\}:v\in V(\mathcal{H})\}.

Proof of the lower bound in Theorem 1.4. Let qq be a prime between r/2r/2 and r−1r-1, and let H\mathcal{H} be a projective plane of order qq, which is a (q+1)(q+1)-uniform (q+1)(q+1)-regular hypergraph. By Theorem 2.1, no matter how one colors the vertices of H\mathcal{H} red and blue, there always exists an edge in which there are at least q\sqrt{q} more red points than blue points (or vice versa). If H′\mathcal{H}' is the dual of the hypergraph H\mathcal{H}, note that its edges cannot be partitioned into two sets E(H′)=E1∪E2E(\mathcal{H}')=E_1\cup E_2 such that each deg⁡E1v∈{(q+1)/2−⌊q/2⌋,…,(q+1)/2+⌊q/2⌋}\deg_{E_1}v\in\{(q+1)/2-\lfloor\sqrt{q}/2\rfloor,\ldots,(q+1)/2+\lfloor\sqrt{q}/2\rfloor\} (otherwise, this would provide a balanced coloring of the vertices of the hypergraph H\mathcal{H}). This shows that g(r)≥g(q+1)≥⌊q⌋≥⌊r/2⌋g(r)\ge g(q+1)\ge\lfloor\sqrt{q}\rfloor\ge\lfloor\sqrt{r/2}\rfloor.

We close this section by giving the proof of Theorem 1.2, which states that regular rr-uniform hypergraphs contain spanning subhypergraphs with all degrees between 1 and 100log⁡r100\log r. By passing to the dual, we see that Theorem 1.2 is equivalent to the following statement.

Proposition 2.2. If F\mathcal{F} is an rr-regular dd-uniform hypergraph, then there exists a set of vertices S⊆V(F)S\subseteq V(\mathcal{F}) such that for any e∈E(F)e\in E(\mathcal{F}) we have 1≤∣e∩S∣≤100log⁡r1\le|e\cap S|\le100\log r.

We split the proof of this proposition into two parts: first, we discuss what happens when d≤O(r)d\le O(r), in which an application of Lovász’s local lemma [9] suffices to prove the statement. When dd is much larger than rr, a simple application of Theorem 1.4 allows us to reduce to the previous case. In the case d≤O(r)d\le O(r), we prove the following statement.

Lemma 2.3. Let F\mathcal{F} be an rr-regular hypergraph, with all edges having size between kk and 3k3k, for some 1≤k≤r1\le k\le r. Then there exists a set S⊆V(F)S\subseteq V(\mathcal{F}) such that 1≤∣e∩S∣≤100log⁡r1\le|e\cap S|\le100\log r for every e∈E(F)e\in E(\mathcal{F}).

Proof. Let SS be a random set of vertices, obtained by including every v∈V(F)v\in V(\mathcal{F}) independently with probability 10log⁡rk\frac{10\log r}{k} (we may assume that k≥10log⁡rk\ge10\log r, as otherwise one may take S=V(F)S=V(\mathcal{F})). We aim to show that with positive probability one has 1≤∣e∩S∣≤100log⁡r1\le|e\cap S|\le100\log r for every e∈E(F)e\in E(\mathcal{F}). Our main goal will be to show that for every fixed hyperedge e∈E(F)e\in E(\mathcal{F}) we have

P[1≤∣e∩S∣≤100log⁡r]≥1−110kr.\mathbb{P}[1\le|e\cap S|\le100\log r]\ge1-\frac{1}{10kr}.

Suppose we have shown this. Then, a simple application of the local lemma suffices to complete the proof as follows. For every e∈E(F)e\in E(\mathcal{F}), define the bad event BeB_e as the complement of the event 1≤∣e∩S∣≤100log⁡r1\le|e\cap S|\le100\log r. Since the event BeB_e only depends on whether the vertices of ee are included in SS or not, it is independent of all Be′B_{e'} with e∩e′=∅e\cap e'=\varnothing. So, the maximum degree of the dependency graph is at most 3k⋅r3k\cdot r, since ∣e∣≤3k|e|\le3k and every vertex of ee is contained in at most rr other edges. Since e(3kr+1)⋅110kr<1\mathrm{e}(3kr+1)\cdot\frac{1}{10kr}<1, the local lemma implies that with positive probability no bad event BeB_e occurs, showing that we have 1≤∣e∩S∣≤100log⁡r1\le|e\cap S|\le100\log r for every e∈E(F)e\in E(\mathcal{F}). So, it remains to bound P[1≤∣e∩S∣≤100log⁡r]\mathbb{P}[1\le|e\cap S|\le100\log r]. To do this, note first that

P[e∩S=∅]≤(1−10log⁡rk)k≤e−10log⁡r=r−10.\mathbb{P}[e\cap S=\varnothing]\le\left(1-\frac{10\log r}{k}\right)^k\le\mathrm{e}^{-10\log r}=r^{-10}.

On the other hand, by the union bound, for any tt we have

P[∣e∩S∣≥t]≤(3kt)(10log⁡rk)t≤(3ekt)t(10log⁡rk)t≤(3e⋅10log⁡rt)t.\mathbb{P}[|e\cap S|\ge t]\le\binom{3k}{t}\left(\frac{10\log r}{k}\right)^t\le\left(\frac{3\mathrm{e}k}{t}\right)^t\left(\frac{10\log r}{k}\right)^t\le\left(\frac{3\mathrm{e}\cdot10\log r}{t}\right)^t.

Putting t=100log⁡rt=100\log r gives

P[∣e∩S∣≥100log⁡r]≤(3e⋅10log⁡r100log⁡r)100log⁡r≤0.9100log⁡r≤r−10,\mathbb{P}[|e\cap S|\ge100\log r]\le\left(\frac{3\mathrm{e}\cdot10\log r}{100\log r}\right)^{100\log r}\le0.9^{100\log r}\le r^{-10},

where we have used that 30e/100<0.930\mathrm{e}/100<0.9 and 0.9100≤e−100.9^{100}\le\mathrm{e}^{-10}. By a simple union bound, we obtain that P[1≤∣e∩S∣≤100log⁡r]≥1−2r−10≥1−110kr\mathbb{P}[1\le|e\cap S|\le100\log r]\ge1-2r^{-10}\ge1-\frac{1}{10kr}, which completes the proof as we already explained.

Let us now give the proof of Proposition 2.2 (and thus of Theorem 1.2, which is its dual).

Proof of Theorem 1.2 and Proposition 2.2. Let H\mathcal{H} be the given dd-regular rr-uniform hypergraph and let F\mathcal{F} be its dual. If we have d≥3rd \ge3r, then by Theorem 1.4 applied with k=rk=r we find a spanning subhypergraph C⊆H\mathcal{C} \subseteq\mathcal{H} in which all degrees are in {r,…,3r−4}\{r,\ldots,3r-4\}. Taking its dual hypergraph F′\mathcal{F}' corresponds to restricting the set of vertices of F\mathcal{F} such that all hyperedges have size between rr and 3r−43r-4. Hence, by Lemma 2.3 applied with k=rk=r we find a subset S⊆V(F′)S \subseteq V(\mathcal{F}') with the property that 1≤∣S∩e∣≤100log⁡r1 \le|S \cap e| \le100 \log r for all e∈E(F′)e \in E(\mathcal{F}'). The set of hyperedges in H\mathcal{H} dual to SS then gives a subhypergraph in which every vertex v∈V(H)v \in V(\mathcal{H}) has degree between 1 and 100log⁡r100 \log r.

In the case d≤3rd \le3r we argue similarly, by directly applying Lemma 2.3 with k=⌈d/3⌉k=\lceil d/3\rceil to obtain a set SS of vertices for which 1≤∣S∩e∣≤100log⁡r1 \le|S \cap e| \le100 \log r. As we noted above, considering its dual gives the subhypergraph we need in H\mathcal{H}.

Tripartite 3-regular hypergraphs

In this section, we present an argument which proves Conjecture 1.5 for 3-regular hypergraphs.

Proposition 3.1. Let H\mathcal{H} be a 3-regular tripartite 3-uniform hypergraph. Then, H\mathcal{H} has a spanning subhypergraph whose degrees are all either 1 or 2.

As in Section 2, it is natural to consider the dual hypergraph F\mathcal{F}, whose vertex set is E(H)E(\mathcal{H}) and whose edges are given by the collections {e:e∋v}\{e:e \ni v\} for each vertex v∈V(H)v \in V(\mathcal{H}). Finding a spanning subhypergraph of H\mathcal{H} whose degrees are all 1 or 2 corresponds to finding a subset of vertices S⊆V(F)S \subseteq V(\mathcal{F}) such that every hyperedge e∈E(F)e \in E(\mathcal{F}) contains one or two of these vertices. In other words, it corresponds to finding a bicoloring of V(F)V(\mathcal{F}) where no edge of F\mathcal{F} is monochromatic, which is saying precisely that F\mathcal{F} has Property B.

To prove Proposition 3.1, we use a simple adaptation of Seymour’s argument from [18], by exploiting the fact that F\mathcal{F} has at least two (in fact, three) disjoint perfect matchings whenever H\mathcal{H} is a tripartite hypergraph. The heart of the argument is the following claim.

Claim 3.2. Let F\mathcal{F} be a hypergraph, and suppose that every proper subhypergraph of F\mathcal{F} has property B. Let us assign a vector xv∈R∣E(F)∣x_v \in\mathbb{R}^{|E(\mathcal{F})|} to each vertex of the hypergraph F\mathcal{F}, where xv(e)=1x_v(e)=1 if v∈ev \in e and xv(e)=0x_v(e)=0 otherwise. If the vectors xvx_v are linearly dependent, then F\mathcal{F} has property B. In particular, if ∣E(F)∣<∣V(F)∣|E(\mathcal{F})|<|V(\mathcal{F})|, then F\mathcal{F} has Property B.

Proof. If the vectors xvx_v are linearly dependent, there exists a linear dependency ∑vαvxv=0\sum_v \alpha_v x_v=0 with not all αv\alpha_v equal to zero. In other words, for every edge e∈E(F)e \in E(\mathcal{F}) we have ∑v∈eαv=0\sum_{v\in e}\alpha_v=0.

Let R={v:αv<0}R=\{v:\alpha_v<0\} and B={v:αv>0}B=\{v:\alpha_v>0\}, and color the vertices of RR red and vertices of BB blue. Note that some vertices may have αv=0\alpha_v=0 and thus remain uncolored. Since ∑v∈eαv=0\sum_{v\in e}\alpha_v=0, any edge containing a red vertex also must contain a blue vertex. Let UU be the set of uncolored vertices, and let F[U]\mathcal{F}[U] be the induced subhypergraph on this set. By assumption, F[U]\mathcal{F}[U] can be bicolored without monochromatic edges. Extending the coloring using the sets R,BR,B gives a bicoloring of F\mathcal{F} without monochromatic edges, as we wanted.

Lemma 3.3. Let F\mathcal{F} be a 3-uniform hypergraph of maximum degree 3 with two edge-disjoint perfect matchings. Then, F\mathcal{F} has Property B.

Proof. Suppose that F\mathcal{F} does not have Property B, and let C⊆F\mathcal{C} \subseteq\mathcal{F} be the minimal subgraph of F\mathcal{F} which also does not have Property B.

To start, let us show that ∣E(C)∣≤∣V(C)∣|E(\mathcal{C})| \le|V(\mathcal{C})|. Indeed, note that the average degree of C\mathcal{C} is at most 3, since this is the maximum degree of C\mathcal{C}. On the other hand, the average degree of C\mathcal{C} is at least 3∣E(C)∣/∣V(C)∣3|E(C)|/|V(C)|, since CC is a 3-uniform hypergraph. Combining these two bounds gives ∣E(C)∣≤∣V(C)∣|E(C)| \le|V(C)|.

On the other hand, since CC is a minimal subhypergraph not having Property B, by Claim 3.2, we must have ∣E(C)∣≥∣V(C)∣|E(C)| \ge|V(C)|. Hence, all of the inequalities of the previous paragraph must be equalities, and in particular all vertices of CC must have degree 3 in CC. This means that no edge contains vertices of both CC and F∖C\mathcal{F}\setminus C, and so every perfect matching of F\mathcal{F} restricts to a perfect matching of CC. Hence, CC has two distinct perfect matchings.

This implies that the vectors {xv:v∈V(C)}\{x_v : v \in V(C)\} cannot be linearly independent, as follows. Consider the vertex-edge incidence matrix AA of the hypergraph CC, which has the vectors xvx_v as rows. If the rows of this square matrix are linearly independent, so are the columns. In other words, if ye∈R∣V(C)∣y_e \in\mathbb{R}^{|V(C)|} is the indicator vector of the edge ee, the vectors {ye:e∈E(C)}\{y_e : e \in E(C)\} are linearly independent.

However, this is not the case: if M,M′M, M' are the perfect matchings of CC, then ∑e∈Mye=∑e∈M′ye\sum_{e\in M} y_e = \sum_{e\in M'} y_e is a nontrivial linear dependence between the columns of AA (both sums give an all-ones vector since M,M′M, M' are perfect). Hence, the rows of AA must also be linearly dependent, which is what we aimed to show. By Claim 3.2 this means that CC has property B, contradiction.

Proof of Proposition 3.1. To prove Proposition 3.1, it suffices to observe that the dual F\mathcal{F} of a tripartite 3-uniform hypergraph H\mathcal{H} has three disjoint perfect matchings. Indeed, the vertices inside each of the three partite sets of H\mathcal{H} are incident to distinct edges, and thus they correspond to a perfect matching in the dual. Hence, Proposition 3.1 follows directly by dualizing Lemma 3.3.

Acknowledgment. Part of the research on this project was done during a visit of the first and last authors at the Institute of Mathematical Sciences, National University of Singapore in 2026. We thank our hosts at the Institute for their hospitality.

AI disclosure. We have tried to use AI tools to resolve Conjecture 1.5. Although this attempt was ultimately unsuccessful, it pointed us to Seymour’s argument from [18], which resolves the 3-regular case and which we decided to include in the paper.

An alternative proof of f(3)≤4f(3) \le4

Here we provide an alternative proof that regular hypergraphs contain shallow edge hitting sets. We first present an argument which gives a subhypergraph with maximum degree 5, and then modify it to show that 5 can be reduced to 4.

This proof is reminiscent of the proof of Petersen’s theorem on 2-factors of even-regular graphs. However, since we are working with hypergraphs instead of graphs, we substitute Hall’s theorem with a consequence of the Aharoni–Haxell hypergraph matching theorem [2]. Before we state it, let us recall that a 3-uniform hypergraph H\mathcal{H} is called bipartite if there is a partition V(H)=A∪BV(\mathcal{H}) = A \cup B such that each edge e∈E(H)e \in E(\mathcal{H}) has ∣e∩A∣=1|e \cap A| = 1 and ∣e∩B∣=2|e \cap B| = 2. Also, let us recall that the link graph of a set SS is the graph LSL_S on the vertex set V(H)V(\mathcal{H}) in which xyxy is an edge if and only if there exists s∈Ss \in S such that {x,y,s}∈E(H)\{x,y,s\} \in E(\mathcal{H}). We denote by ν(G)\nu(G) the maximum size of a matching in a graph GG, and by τ(G)\tau(G) the minimum size of a vertex set that intersects every edge of GG.

Theorem A.1 (Corollary 1.2 in [2]). Suppose that H\mathcal{H} is a bipartite 33-uniform hypergraph. If every set S⊆AS \subseteq A has ν(LS)≥2∣S∣\nu(L_S) \ge2|S|, then there exists a matching MM in H\mathcal{H} saturating AA.

Proposition A.2. If H\mathcal{H} is a nonempty regular 33-uniform hypergraph, then H\mathcal{H} has a spanning subhypergraph with degrees in the set {1,2,3,4,5}\{1,2,3,4,5\}.

Proof. Consider the following auxiliary hypergraph A\mathcal{A}. The vertex set of A\mathcal{A} consists of five copies of V(H)V(\mathcal{H}), i.e. for each vertex v∈V(H)v \in V(\mathcal{H}) we add the vertices v(1),v(2),v(3),v(4),v(5)v^{(1)}, v^{(2)}, v^{(3)}, v^{(4)}, v^{(5)} to V(A)V(\mathcal{A}). The edge set of A\mathcal{A} is defined as follows: for each edge e={x,y,z}∈E(H)e = \{x,y,z\} \in E(\mathcal{H}), we add to E(A)E(\mathcal{A}) the following six edges

{x(1),y(2),z(3)},{y(1),z(2),x(3)},{z(1),x(2),y(3)},{x(1),y(4),z(5)},{y(1),z(4),x(5)},{z(1),x(4),y(5)}.\begin{aligned} &\{x^{(1)},y^{(2)},z^{(3)}\},\quad\{y^{(1)},z^{(2)},x^{(3)}\},\quad\{z^{(1)},x^{(2)},y^{(3)}\},\\ &\{x^{(1)},y^{(4)},z^{(5)}\},\quad\{y^{(1)},z^{(4)},x^{(5)}\},\quad\{z^{(1)},x^{(4)},y^{(5)}\}. \end{aligned}

Note that the resulting hypergraph A\mathcal{A} is tripartite, since every edge contains one vertex from each of the three sets A={v(1):v∈V(H)}A = \{v^{(1)} : v \in V(\mathcal{H})\}, B={v(2),v(4):v∈V(H)}B = \{v^{(2)},v^{(4)} : v \in V(\mathcal{H})\} and C={v(3),v(5):v∈V(H)}C = \{v^{(3)},v^{(5)} : v \in V(\mathcal{H})\}. See the illustration in Figure 1. Further, since H\mathcal{H} is dd-regular, every vertex of AA has degree 2d2d, while every vertex of BB and CC has degree dd.

Figure 1. The auxiliary hypergraph A\mathcal{A}.

The goal is to show that there exists a matching covering AA in this auxiliary hypergraph. To show this, note that for any S⊆AS \subseteq A, the link graph LSL_S is a bipartite multigraph between BB and CC with maximum degree dd and 2∣S∣d2|S|d edges, since every vertex of SS contributes at least 2d2d edges to the link graph. Hence, the cover number of this bipartite graph must be at least 2∣S∣2|S|, and so by König’s theorem we have ν(LS)=τ(LS)≥2∣S∣\nu(L_S) = \tau(L_S) \ge2|S|. By Theorem A.1, this shows that A\mathcal{A} contains a matching MM saturating AA.

In other words, for every v∈V(H)v \in V(\mathcal{H}), there exists a unique edge of MM containing v(1)v^{(1)}, say {v(1),u(2),w(3)}\{v^{(1)},u^{(2)},w^{(3)}\} (or {v(1),u(4),w(5)}\{v^{(1)},u^{(4)},w^{(5)}\}). We construct the subhypergraph CC by adding the edge {v,u,w}\{v,u,w\} for each vv. We claim that every vertex appears in at most 5 edges of CC. Indeed, if a vertex vv appears in an edge of CC, it must be that one of its copies in A\mathcal{A} was present in one of the edges of the matching MM. But there are 5 copies of vv in A\mathcal{A}, and so vv can appear in at most 5 edges of CC. This shows that CC has maximum degree at most 5, as we wanted. □

Proposition A.3. If H\mathcal{H} is a nonempty regular 33-uniform hypergraph, then H\mathcal{H} has a spanning subhypergraph with degrees in the set {1,2,3,4}\{1,2,3,4\}.

Proof. We start from the subhypergraph CC obtained in Proposition A.2 and remove some edges to reduce its maximum degree by one. Note that we treat CC as a multihypergraph.

The main observation is that if a vertex vv has deg⁡Cv=5\operatorname{deg}_{C} v = 5, then we may delete the edge containing v(1)v^{(1)} in the matching MM (which we included in order to cover vv) and reduce the degree of vv in this way. However, one must be careful in which order the vertices vv are chosen, in order to ensure that every vertex is still covered after several edges get deleted in this process.

We call the edge containing v(1)v^{(1)} in the matching MM the special edge of vv, and we use the same term to refer to the corresponding edge in CC.

Let DD be an auxiliary directed graph on the set of vertices of degree 5. We put a directed edge in DD from uu to vv if vv is contained in the special edge of uu and v≠uv \ne u. The goal is to delete some special edges associated to the vertices of DD, and we will use DD to guide the order in which we do this.

The maximum outdegree in DD is 2, and hence there exists a vertex vv of indegree at most 2. We now delete the special edge eve_v of the vertex vv from CC.

We claim that even though eve_v was deleted, vv will still be covered at the end of this procedure. This is simple to see: since vv had at most 2 inedges, at most two additional edges covering vv will be deleted. Since vv had appeared in 5 edges of CC, even after all the deletions, vv will still be covered.

We further claim that no other vertex ww of eve_v is left uncovered. If ww never had degree 5, then the special edge ewe_w will not be deleted from CC and ww will remain covered. If ww had degree 5 and the special edge ewe_w was deleted in the past, we have just argued in the previous paragraph that ww will remain covered.

We iterate this process on the remaining vertices that are covered at least 5 times, until all vertices are covered at most 4 times, which completes the proof.

References

  1. [1]L. Addario-Berry, K. Dalal, B. A. Reed, Degree constrained subgraphs, Discrete Appl. Math., 156 (2008) 1168–1174.
  2. [2]R. Aharoni, P. E. Haxell, Hall’s theorem for hypergraphs, J. Graph Theory, 35 (2000) 83–88.doi.org/10.1002/1097-0118(200010)35:2<83::aid-jgt2>3.0.co;2-v
  3. [3]N. Alon, Combinatorial Nullstellensatz, Combin. Probab. Comput., 8(1999) 7–29.
  4. [4]N. Alon, J. H. Spencer, The Probabilistic Method, third ed., Wiley-Interscience, Hoboken, NJ, 2008.
  5. [5]J. Beck, T. Fiala, “Integer-making” theorems, Discrete Appl. Math., 3 (1981) 1–8.DOI
  6. [6]J. Beck, V. T. Sós, Discrepancy theory, in R. L. Graham, M. Grötschel, L. Lovász (eds.), Handbook of Combinatorics, Vol. 2, Elsevier, Amsterdam (1995) 1405–1446.
  7. [7]C. Berge, M. Las Vergnas, On the existence of subgraphs with degree constraints, Nederl. Akad. Wetensch. Indag. Math., 40 (1978) 165–176.
  8. [8]G. Cornuéjols, General factors of graphs, J. Combin. Theory Ser. B, 45 (1988) 185–198.DOI
  9. [9]P. Erdős, L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, in: Infinite and Finite Sets, Colloq. Math. Soc. János Bolyai, vol. 10, North-Holland, Amsterdam, 1975, pp. 609–627.
  10. [10]S. Guo, E. X. Fang and J. Lu, Vector Balancing via Directional Total Variation, arXiv:2609.11189v1, 2026.arxiv.org/abs/2609.11189
  11. [11]P. Hall, On representatives of subsets, J. Lond. Math. Soc., 10 (1935) 26–30.
  12. [12]B. Keszegh, D. Pálvölgyi, An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalflanes, J. Comput. Geom., 10 (2019) 1–26.
  13. [13]R. Lang, N. Sanhueza-Matamala, On sufficient conditions for spanning structures in dense graphs, Proc. Lond. Math. Soc., 127 (2023) 709–791.arxiv.org/abs/2110.14547
  14. [14]L. Lovász, Subgraphs with prescribed valencies, J. Combin. Theory, 8 (1970) 391–416.DOI
  15. [15]L. Lovász, The factorization of graphs. II, Acta Math. Acad. Sci. Hungar., 23 (1972) 223–246.DOI
  16. [16]J. Petersen, Die Theorie der regulären Graphs, Acta Math., 15 (1891) 193–220.DOI
  17. [17]T. Planken, T. Ueckerdt, Shallow hitting edge sets in uniform hypergraphs, preprint, arXiv:2307.05757 (2023).arxiv.org/abs/2307.05757
  18. [18]P. D. Seymour, On the two-colouring of hypergraphs, Q. J. Math., 25 (1974) 303–311.DOI
  19. [19]H. Shirazi, J. Verstraëte, A note on polynomials and f-factors of graphs, Electron. J. Combin., 15 (2008) Paper No. N22.DOI
  20. [20]C. Thomassen, A remark on the factor theorems of Lovász and Tutte, J. Graph Theory, 5 (1981) 441–442.DOI
  21. [21]C. Thomassen, The even cycle problem for directed graphs, J. Amer. Math. Soc., 5 (1992) 217–229.
  22. [22]W. T. Tutte, The factorization of linear graphs, J. Lond. Math. Soc., 22 (1947) 107–111.DOI
  23. [23]W. T. Tutte, The 1-factors of oriented graphs, Proc. Amer. Math. Soc., 4 (1953) 922–931.
  24. [24]W. T. Tutte, The subgraph problem, Ann. Discrete Math., 3 (1978) 289–295.DOI

Paper details

vlnc:W_fafcpz54
Version
v2 · latest
Published
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents