An official website of the United States government
Abstract Let {G(k)}denote the least numbershaving the property that everysufficiently large natural number is the sum of at mostspositive integralk-th powers.Then for all {k\in\mathbb{N}}, one has G(k)\leqslant\lceil k(\log k+4.20032)\rceil. Our new methods improve on all bounds available hitherto when {k\geqslant 14}.
more »
« less
This content will become publicly available on September 26, 2026
Proof of the Goldberg–Seymour conjecture on edge–colorings of multigraphs
Abstract Given a multigraph$$G=(V,E)$$, the edge-coloring problem (ECP) is to color the edges ofGwith the minimum number of colors so that no two adjacent edges have the same color. This problem can be naturally formulated as an integer program, and its linear programming relaxation is referred to as the fractional edge-coloring problem (FECP). The optimal value of ECP (resp. FECP) is called the chromatic index (resp. fractional chromatic index) ofG, denoted by$$\chi '(G)$$(resp.$$\chi ^*(G)$$). Let$$\Delta (G)$$be the maximum degree ofGand let$$\Gamma (G)$$be the density ofG, defined by$$\begin{aligned} \Gamma (G)=\max \left\{ \frac{2|E(U)|}{|U|-1}:\,\, U \subseteq V, \,\, |U|\ge 3 \hspace{5.69054pt}\textrm{and} \hspace{5.69054pt}\textrm{odd} \right\} , \end{aligned}$$whereE(U) is the set of all edges ofGwith both ends inU. Clearly,$$\max \{\Delta (G), \, \lceil \Gamma (G) \rceil \}$$is a lower bound for$$\chi '(G)$$. As shown by Seymour,$$\chi ^*(G)=\max \{\Delta (G), \, \Gamma (G)\}$$. In the early 1970s Goldberg and Seymour independently conjectured that$$\chi '(G) \le \max \{\Delta (G)+1, \, \lceil \Gamma (G) \rceil \}$$. Over the past five decades this conjecture, a cornerstone in modern edge-coloring, has been a subject of extensive research, and has stimulated an important body of work. In this paper we present a proof of this conjecture. Our result implies that, first, there are only two possible values for$$\chi '(G)$$, so an analogue to Vizing’s theorem on edge-colorings of simple graphs holds for multigraphs; second, although it isNP-hard in general to determine$$\chi '(G)$$, we can approximate it within one of its true value, and find it exactly in polynomial time when$$\Gamma (G)>\Delta (G)$$; third, every multigraphGsatisfies$$\chi '(G)-\chi ^*(G) \le 1$$, and thus FECP has a fascinating integer rounding property.
more »
« less
- PAR ID:
- 10639889
- Publisher / Repository:
- Springer
- Date Published:
- Journal Name:
- Journal of Combinatorial Optimization
- Volume:
- 50
- Issue:
- 3
- ISSN:
- 1382-6905
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract The purpose of this paper is to introduce and study the following graph-theoretic paradigm. Let$$ \begin{align*}T_Kf(x)=\int K(x,y) f(y) d\mu(y),\end{align*} $$where$$f: X \to {\Bbb R}$$,Xa set, finite or infinite, andKand$$\mu $$denote a suitable kernel and a measure, respectively. Given a connected ordered graphGonnvertices, consider the multi-linear form$$ \begin{align*}\Lambda_G(f_1,f_2, \dots, f_n)=\int_{x^1, \dots, x^n \in X} \ \prod_{(i,j) \in {\mathcal E}(G)} K(x^i,x^j) \prod_{l=1}^n f_l(x^l) d\mu(x^l),\end{align*} $$where$${\mathcal E}(G)$$is the edge set ofG. Define$$\Lambda _G(p_1, \ldots , p_n)$$as the smallest constant$$C>0$$such that the inequality(0.1)$$ \begin{align} \Lambda_G(f_1, \dots, f_n) \leq C \prod_{i=1}^n {||f_i||}_{L^{p_i}(X, \mu)} \end{align} $$holds for all nonnegative real-valued functions$$f_i$$,$$1\le i\le n$$, onX. The basic question is, how does the structure ofGand the mapping properties of the operator$$T_K$$influence the sharp exponents in (0.1). In this paper, this question is investigated mainly in the case$$X={\Bbb F}_q^d$$, thed-dimensional vector space over the field withqelements,$$K(x^i,x^j)$$is the indicator function of the sphere evaluated at$$x^i-x^j$$, and connected graphsGwith at most four vertices.more » « less
-
Abstract Given graph$$G=(V,E)$$ with vertex setVand edge setE, the maxk-cut problem seeks to partition the vertex setVinto at mostksubsets that maximize the weight (number) of edges with endpoints in different parts. This paper proposes a graph folding procedure (i.e., a procedure that reduces the number of the vertices and edges of graphG) for the weighted maxk-cut problem that may help reduce the problem’s dimensionality. While our theoretical results hold for any$$k \ge 2$$ , our computational results show the effectiveness of the proposed preprocessonlyfor$$k=2$$ and on two sets of instances. Furthermore, we observe that the preprocess improves the performance of a MIP solver on a set of large-scale instances of the max cut problem.more » « less
-
Abstract We introduce partitioned matching games as a suitable model for international kidney exchange programmes, where in each round the total number of available kidney transplants needs to be distributed amongst the participating countries in a “fair” way. A partitioned matching game (N, v) is defined on a graph$$G=(V,E)$$ with an edge weightingwand a partition$$V=V_1 \cup \dots \cup V_n$$ . The player set is$$N = \{ 1, \dots , n\}$$ , and player$$p \in N$$ owns the vertices in$$V_p$$ . The valuev(S) of a coalition $$S \subseteq N$$ is the maximum weight of a matching in the subgraph ofGinduced by the vertices owned by the players in S. If$$|V_p|=1$$ for all$$p\in N$$ , then we obtain the classical matching game. Let$$c=\max \{|V_p| \; |\; 1\le p\le n\}$$ be the width of (N, v). We prove that checking core non-emptiness is polynomial-time solvable if$$c\le 2$$ but co--hard if$$c\le 3$$ . We do this via pinpointing a relationship with the known class ofb-matching games and completing the complexity classification on testing core non-emptiness forb-matching games. With respect to our application, we prove a number of complexity results on choosing, out of possibly many optimal solutions, one that leads to a kidney transplant distribution that is as close as possible to some prescribed fair distribution.more » « less
-
Abstract In 1967, Gerencsér and Gyárfás [16] proved a result which is considered the starting point of graph-Ramsey theory: In every 2-coloring of$$K_n$$, there is a monochromatic path on$$\lceil (2n+1)/3\rceil $$vertices, and this is best possible. There have since been hundreds of papers on graph-Ramsey theory with some of the most important results being motivated by a series of conjectures of Burr and Erdős [2, 3] regarding the Ramsey numbers of trees (settled in [31]), graphs with bounded maximum degree (settled in [5]), and graphs with bounded degeneracy (settled in [23]). In 1993, Erdős and Galvin [13] began the investigation of a countably infinite analogue of the Gerencsér and Gyárfás result: What is the largestdsuch that in every$$2$$-coloring of$$K_{\mathbb {N}}$$there is a monochromatic infinite path with upper density at leastd? Erdős and Galvin showed that$$2/3\leq d\leq 8/9$$, and after a series of recent improvements, this problem was finally solved in [7] where it was shown that$$d={(12+\sqrt {8})}/{17}$$. This paper begins a systematic study of quantitative countably infinite graph-Ramsey theory, focusing on infinite analogues of the Burr-Erdős conjectures. We obtain some results which are analogous to what is known in finite case, and other (unexpected) results which have no analogue in the finite case.more » « less
