More Like this

1. Proof of the Goldberg–Seymour conjecture on edge–colorings of multigraphs

   https://doi.org/10.1007/s10878-025-01348-6  

   Chen, Guantao; Jing, Guangming; Zang, Wenan (September 2025, Journal of Combinatorial Optimization)

   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
2. Dimension estimates for the set of points with non-dense orbit in homogeneous spaces

   https://doi.org/10.1007/s00209-019-02386-7  

   Kleinbock, D. (January 2020, Mathematische Zeitschrift)

   Let 𝑋=𝐺/Γ, where G is a Lie group and Γ is a lattice in G, and let U be a subset of X whose complement is compact. We use the exponential mixing results for diagonalizable flows on X to give upper estimates for the Hausdorff dimension of the set of points whose trajectories miss U. This extends a recent result of Kadyrov et al. (Dyn Syst 30(2):149–157, 2015) and produces new applications to Diophantine approximation, such as an upper bound for the Hausdorff dimension of the set of weighted uniformly badly approximable systems of linear forms, generalizing an estimate due to Broderick and Kleinbock (Int J Number Theory 11(7):2037–2054, 2015). 

   more » « less
3. Hyperbolic families and coloring graphs on surfaces

   https://doi.org/https://doi.org/10.1090/btran/26  

   Postle, Luke; Thomas, Robin (December 2018, Transactions of the American Mathematical Society. Series B)

   We develop a theory of linear isoperimetric inequalities for graphs on surfaces and apply it to coloring problems, as follows. Let $ G$ be a graph embedded in a fixed surface $$ \Sigma $$ of genus $ g$ and let $$ L=(L(v):v\in V(G))$$ be a collection of lists such that either each list has size at least five, or each list has size at least four and $ G$ is triangle-free, or each list has size at least three and $ G$ has no cycle of length four or less. An $ L$-coloring of $ G$ is a mapping $$ \phi $$ with domain $ V(G)$ such that $$ \phi (v)\in L(v)$$ for every $$ v\in V(G)$$ and $$ \phi (v)\ne \phi (u)$$ for every pair of adjacent vertices $$ u,v\in V(G)$$. We prove if every non-null-homotopic cycle in $ G$ has length $$ \Omega (\log g)$$, then $ G$ has an $ L$-coloring, if $ G$ does not have an $ L$-coloring, but every proper subgraph does (``$ L$-critical graph''), then $$ \vert V(G)\vert=O(g)$$, if every non-null-homotopic cycle in $ G$ has length $$ \Omega (g)$$, and a set $$ X\subseteq V(G)$$ of vertices that are pairwise at distance $$ \Omega (1)$$ is precolored from the corresponding lists, then the precoloring extends to an $ L$-coloring of $ G$, if every non-null-homotopic cycle in $ G$ has length $$ \Omega (g)$$, and the graph $ G$ is allowed to have crossings, but every two crossings are at distance $$ \Omega (1)$$, then $ G$ has an $ L$-coloring, if $ G$ has at least one $ L$-coloring, then it has at least $$ 2^{\Omega (\vert V(G)\vert)}$$ distinct $ L$-colorings. We show that the above assertions are consequences of certain isoperimetric inequalities satisfied by $ L$-critical graphs, and we study the structure of families of embedded graphs that satisfy those inequalities. It follows that the above assertions hold for other coloring problems, as long as the corresponding critical graphs satisfy the same inequalities. 

   more » « less
4. EvaNet: Elevation-Guided Flood Extent Mapping on Earth Imagery

   Sami, Mirza Tanzim; Yan, Da; Adhikari, Saugat; Yuan, Lyuheng; Han, Jiao; Jiang, Zhe; Khalil, Jalal; Zhou, Yang (October 2024, IJCAI)

   Accurate and timely mapping of flood extent from high-resolution satellite imagery plays a crucial role in disaster management such as damage assessment and relief activities. However, current state-of-the-art solutions are based on U-Net, which cannot segment the flood pixels accurately due to the ambiguous pixels (e.g., tree canopies, clouds) that prevent a direct judgement from only the spectral features. Thanks to the digital elevation model (DEM) data readily available from sources such as United States Geological Survey (USGS), this work explores the use of an elevation map to improve flood extent mapping. We propose, EvaNet, an elevation-guided segmentation model based on the encoder-decoder architecture with two novel techniques: (1) a loss function encoding the physical law of gravity that if a location is flooded (resp. dry), then its adjacent locations with a lower (resp. higher) elevation must also be flooded (resp. dry); (2) a new (de)convolution operation that integrates the elevation map by a location-sensitive gating mechanism to regulate how much spectral features flow through adjacent layers. Extensive experiments show that EvaNet significantly outperforms the U-Net baselines, and works as a perfect drop-in replacement for U-Net in existing solutions to flood extent mapping. EvaNet is open-sourced at https://github.com/MTSami/EvaNet 

   more » « less
5. On Single-Distance Graphs on the Rational Points in Euclidean Spaces

   https://doi.org/10.4153/S0008439520000181  

   Bau, Sheng; Johnson, Peter; Noble, Matt (March 2021, Canadian Mathematical Bulletin)

   null (Ed.)

   Abstract For positive integers n and d > 0, let $$G(\mathbb {Q}^n,\; d)$$ denote the graph whose vertices are the set of rational points $$\mathbb {Q}^n$$ , with $$u,v \in \mathbb {Q}^n$$ being adjacent if and only if the Euclidean distance between u and v is equal to d . Such a graph is deemed “non-trivial” if d is actually realized as a distance between points of $$\mathbb {Q}^n$$ . In this paper, we show that a space $$\mathbb {Q}^n$$ has the property that all pairs of non-trivial distance graphs $$G(\mathbb {Q}^n,\; d_1)$$ and $$G(\mathbb {Q}^n,\; d_2)$$ are isomorphic if and only if n is equal to 1, 2, or a multiple of 4. Along the way, we make a number of observations concerning the clique number of $$G(\mathbb {Q}^n,\; d)$$ . 

   more » « less