An official website of the United States government
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
Contact graphs, boundaries, and a central limit theorem for $\mathrm{CAT}(0)$ cubical complexes
LetXbe a nonelementary\mathrm{CAT}(0)cubical complex. We prove that ifXis essential and irreducible, then the contact graph ofX(introduced by Hagen (2014)) is unbounded and its boundary is homeomorphic to the regular boundary ofX(defined by Fernós (2018) and Kar–Sageev (2016)). Using this, we reformulate the Caprace–Sageev’s rank-rigidity theorem in terms of the action on the contact graph. LetGbe a group with a nonelementary action onX, and let (Z_{n})be a random walk corresponding to a generating probability measure onGwith finite second moment. Using this identification of the boundary of the contact graph, we prove a central limit theorem for (Z_{n}), namely that\frac{d(Z_{n} o,o)-nA}{\sqrt{n}}converges in law to a non-degenerate Gaussian distribution (A\hspace{-0.7pt}=\hspace{-0.7pt}\lim_{n\to\infty}\hspace{-0.7pt}\frac{d(Z_{n}o,o)}{n}is the drift of the random walk, ando\in Xis an arbitrary basepoint).
more »
« less
- Award ID(s):
- 2005640
- PAR ID:
- 10552511
- Publisher / Repository:
- EMS Press
- Date Published:
- Journal Name:
- Groups, Geometry, and Dynamics
- Volume:
- 18
- Issue:
- 2
- ISSN:
- 1661-7207
- Page Range / eLocation ID:
- 677 to 704
- Subject(s) / Keyword(s):
- 20F67 (primary) 60F05 (secondary).
- 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
-
Let\Sigmabe a strictly convex, compact patch of aC^{2}hypersurface in\mathbb{R}^{n}, with non-vanishing Gaussian curvature and surface measured\sigmainduced by the Lebesgue measure in\mathbb{R}^{n}. The Mizohata–Takeuchi conjecture states that \int |\widehat{g d\sigma}|^{2} w \leq C \|Xw\|_{\infty} \int |g|^{2} for allg\in L^{2}(\Sigma)and all weightsw \colon \mathbb{R}^{n}\rightarrow [0,+\infty), whereXdenotes theX-ray transform. As partial progress towards the conjecture, we show, as a straightforward consequence of recently-established decoupling inequalities, that for every\varepsilon>0, there exists a positive constantC_{\varepsilon}, which depends only on\Sigmaand\varepsilon, such that for allR \geq 1and all weightsw \colon \mathbb{R}^{n}\rightarrow [0,+\infty), we have \int_{B_R}|\widehat{g d\sigma}|^{2} w \leq C_{\varepsilon} R^{\varepsilon} \sup_{T} \Big(\int_{T} w^{(n+1)/2}\Big)^{2/(n+1)}\int |g|^{2}, whereTranges over the family of tubes in\mathbb{R}^{n}of dimensionsR^{1/2}\times \cdots \times R^{1/2}\times R. From this we deduce the Mizohata–Takeuchi conjecture with anR^{(n-1)/(n+1)}-loss; i.e., that \int_{B_R}|\widehat{g d\sigma}|^{2} w \leq C_{\varepsilon} R^{\frac{n-1}{n+1}+ \varepsilon}\|Xw\|_{\infty} \int |g|^{2} for any ballB_{R}of radiusRand any\varepsilon>0. The power(n-1)/(n+1)here cannot be replaced by anything smaller unless properties of\widehat{g d\sigma}beyond ‘decoupling axioms’ are exploited. We also provide estimates which improve this inequality under various conditions on the weight, and discuss some new cases where the conjecture holds.more » « less
-
Abstract For a subgraph$$G$$of the blow-up of a graph$$F$$, we let$$\delta ^*(G)$$be the smallest minimum degree over all of the bipartite subgraphs of$$G$$induced by pairs of parts that correspond to edges of$$F$$. Johansson proved that if$$G$$is a spanning subgraph of the blow-up of$$C_3$$with parts of size$$n$$and$$\delta ^*(G) \ge \frac{2}{3}n + \sqrt{n}$$, then$$G$$contains$$n$$vertex disjoint triangles, and presented the following conjecture of Häggkvist. If$$G$$is a spanning subgraph of the blow-up of$$C_k$$with parts of size$$n$$and$$\delta ^*(G) \ge \left(1 + \frac 1k\right)\frac n2 + 1$$, then$$G$$contains$$n$$vertex disjoint copies of$$C_k$$such that each$$C_k$$intersects each of the$$k$$parts exactly once. A similar conjecture was also made by Fischer and the case$$k=3$$was proved for large$$n$$by Magyar and Martin. In this paper, we prove the conjecture of Häggkvist asymptotically. We also pose a conjecture which generalises this result by allowing the minimum degree conditions in each bipartite subgraph induced by pairs of parts of$$G$$to vary. We support this new conjecture by proving the triangle case. This result generalises Johannson’s result asymptotically.more » « less
-
On a smooth, compact, Riemannian manifold without boundary(M,g), let\Delta_{g}be the Laplace–Beltrami operator. We define the orthogonal projection operator \Pi_{I_\lambda}\colon L^{2}(M)\to \bigoplus_{\mathclap{\lambda_j\in I_\lambda}}\ker(\Delta_{g}+\lambda_{j}^{2}) for an intervalI_{\lambda}centered around\lambda\in\Rof a small, fixed length. The Schwartz kernel,\Pi_{I_\lambda}(x,y), of this operator plays a key role in the analysis of monochromatic random waves, a model for high energy eigenfunctions. It is expected that\Pi_{I_\lambda}(x,y)has universal asymptotics as\lambda \to \inftyin a shrinking neighborhood of the diagonal inM\times M(providedI_{\lambda}is chosen appropriately) and hence that certain statistics for monochromatic random waves have universal behavior. These asymptotics are well known for the torus and the round sphere, and were recently proved to hold near points inMwith few geodesic loops by Canzani–Hanin. In this article, we prove that the same universal asymptotics hold in the opposite case of Zoll manifolds (manifolds all of whose geodesics are closed with a common period) under an assumption on the volume of loops with length incommensurable with the minimal common period.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.4171/GGD/775
