Regular behaviour of the maximal hypergraph chromatic number

?

Regular behaviour of the maximal hypergraph chromatic number

2019.

Cherkashin D., Petrov F.

Let m(n, r) denote the minimal number of edges in an n-uniform hypergraph which is not r-colorable. It is known that for a fixed n one has c_n r^n < m(n, r) < C_n r^n . We prove that for any fixed n the sequence a_r := m(n, r)/r^n has a limit, which was conjectured by Alon. We also prove the list colorings analogue of this statement.

Priority areas: mathematics

Language: English

Full text

Text on another site

Pairings on the algebra of Laurent series over a ring

Levashev V., / Series arXiv "math". 2026. No. 2609.06010.

We prove that continuous A-bilinear pairings on the ring of Laurent series that are invariant under continuous automorphisms coincide, up to a constant, with the pairing given by the residue of a differential form over any commutative associative ring with identity. ...

Added: September 24, 2026

Iterative construction of the R-matrices in arbitrary dimensions

Pyatov P. N., Pivovarov P. A., / Series math "arxiv.org". 2026. No. 2609.06274.

We investigate a special ansats that allows for an iterative solution of the constant Yang-Baxter equation. Testing this ansatz, we construct four sequences of the constant R-matrices. In each sequence the R-matrices act on the tensor squares of vector spaces of linearly growing dimensions. Each R-matrix also depends on a single complex parameter. By analyzing the ...

Added: September 24, 2026

On static manifolds with boundary admitting a nowhere-vanishing static potential

Medvedev V., / Series arXiv "math". 2026.

We study complete static manifolds with boundary admitting a nowhere-vanishing static potential. Our main result shows that, under a natural lower bound relating the scalar curvature and the boundary mean curvature, a simple static manifold with boundary must in fact have positive scalar curvature, negative boundary mean curvature, and be compact; we also obtain explicit ...

Added: September 19, 2026

Vague stimulating ideas, images and metaphors in scientific thinking: researchers' work with horizons of unclear knowledge

Poddiakov A., / Series Social Science Research Network "Social Science Research Network". 2026. No. 7437658.

Clarity of knowledge and reasoning is necessary in many cases. Yet vagueness in scientific thinking related to surprise, curiosity, "ability to engage with not-knowing" (de Freitas) and abductive reasoning is also a crucially important source of scientific creativity which supplements combinatorial logic when dealing with the already known. Starting from studies by C. S. Peirce ...

Added: September 15, 2026

On phase-lock area parquet in a special slow-fast limit of model of Josephson junction.

Glutsyuk A., / Series arXiv "math". 2026.

B.Josephson (Nobel Prize, 1973) predicted a tunnelling effect for a system of two superconductors separated by a narrow dielectric (such a system is called Josephson junction): existence of a supercurrent through it and equations governing it. The overdamped Josephson junction is modeled by the family of differential equations on the 2-torus, dθdτ=1ω(cosθ+B+Acosτ), which is known as ...

Added: September 8, 2026

Infinitely many graph manifolds with unique geometrical piece that admit arbitrarily many Anosov flows

Pochinka O., Shmukler V., / Series math.RT "arXiv:1808.06395 [math.RT]". 2026.

Anosov flows have a long and rich history, firstly motivated by the study of geodesic flows in negative curvature surface by Anosov and Sinai. Not every closed manifold admits an Anosov flow for well-known reasons: the fundamental group of a 3-manifold M admitting an Anosov flow must have exponential growth, and M must be universally covered by R3. Nevertheless, there ...

Added: August 31, 2026

New bound on S1× S2-setting Bell locality of a nonseparable Werner state

Loubenets E. R., / Series arxiv.org "quant-ph". 2026. No. 2607.18050.

In many quantum applications it is important to know whether or not a Bell nonlocal two-qudit state exhibits its nonlocality under correlation scenarios with some given numbers S1,S2≥1 of generalized quantum measurements at two sites. In the present article, we find analytically a new general locality condition sufficient for a nonseparable Werner state with a ...

Added: July 21, 2026

On functional equations for Chow polylogarithms

Bolbachan V., / Series math "arxiv.org". 2024.

Chow polylogarithms are some special functions arising in explicit description of the Beilinson regulator map. The most interesting functional equation for this function reflects its vanishing on the boundary in the Bloch's cycle complex. We show that this functional equation formally follows from more simple ones, namely skew-symmetry, functoriality and multiplicativity. To prove this, we study ...

Added: July 16, 2026

On Goncharov’s conjecture in next to Milnor degree

Bolbachan V., / Series math "arxiv.org". 2024.

Let K be a field of characteristic zero. We prove that its motivic cohomology in degree m−1 and weight m is rationally isomorphic to the cohomology of the polylogarithmic complex. This gives a partial extension of A. Suslin theorem describing the indecomposable K3 of a field. ...

Added: July 16, 2026

Statistical inference based on band-limited kernels: Rational-infinitely divisible distributions and beyond

Panov V., Ryabchenko A., / Series arXiv "stat.ME". 2026. No. 2607.05048.

This paper investigates the problem of statistical inference for a mixture distribution consisting of a discrete and a continuous component, with a particular focus on the class of rational-infinitely divisible distributions. We consider non-parametric estimation of both components of the mixture as well as the quasi-L{é}vy measure, assuming that the mixture belongs to the class ...

Added: July 9, 2026

Strong Approximations for Markov Chains Weakly Converging to Diffusions

Konakov V., Kucher D., Mammen E., / Series arXiv "math". 2026. No. 2606.11142v1.

In this paper, we construct strong approximations for discrete-time Markov chains weakly converging to continuous diffusion processes, as well as for their perturbed counterparts. Under the assumption of bounded coefficients, we construct closely coupled versions of these processes on a shared probability space. In particular, for both non-degenerate and degenerate cases, we maximize the probability ...

Added: June 11, 2026

Bifurcations and Structural Stability of Generic PC-HC Families

Dorovskiy A., / Series arXiv "math". 2026.

In this paper the structural stability of generic families of vector fields of the PC-HC class on the two-dimensional sphere is proved. A classification of these families up to moderate equivalence in neighborhoods of their large bifurcation supports is presented, based on such invariants as the configuration and the characteristic set. The realization lemma is proved. ...

Added: May 14, 2026

On the minimum number of maximal distance-k independent sets in trees

Taletskii D., / Series arXiv "math". 2026.

A vertex subset of a graph is called a \textit{distance-$k$ independent set} if the distance between any two of its distinct vertices is at least $k + 1$. For all $n,k \geq 1$, we determine the minimum possible number of inclusion-wise maximal distance-$k$ independent sets among all $n$-vertex trees. It equals~$n$ if $n \leq k ...

Added: May 1, 2026

On Arithmetic Mirror Symmetry for smooth Fano fourfolds

Ovcharenko M., / Series arXiv "math". 2026.

We introduce an explicit class of tempered Laurent polynomials in the sense of Villegas and Doran--Kerr in n⩽4 variables including all Landau--Ginzburg models for smooth Fano threefolds with very ample anticanonical class. We check that it contains Landau--Ginzburg models for various Fano fourfolds which are complete intersections in smooth toric varieties and Grassmannians of planes, ...

Added: April 30, 2026

On weak solutions to the 1d compressible Navier-Stokes equations: a Lipschitz continuous dependence on data in weaker norms and an error of their homogenization

Zlotnik Alexander, / Series arXiv "math". 2026. No. 2602.03481v1.

We deal with the global in time weak solutions to the 1D compressible Navier-Stokes system of equations for large discontinuous initial data and nonhomogeneous boundary conditions of three standard types. We prove the Lipschitz-type continuous dependence of the solution $(\eta,u,\theta)$, in a norm slightly stronger than $L^{2,\infty}(Q)\times L^2(Q)\times L^2(Q)$, on the initial data $(\eta^0,u^0,e^0)$ in a ...

Added: April 18, 2026

On the dimension of the space of static potentials on three-manifolds

Medvedev V., / Series arXiv "math". 2026.

We investigate the interplay between the dimension of the space of static potentials and the geometric and topological structure of the underlying static three-manifold. A partial classification of boundaryless static manifolds is obtained in terms of this dimension. We also treat the case of static manifolds with boundary. In particular, we prove that if a ...

Added: April 3, 2026

Using predefined vector systems to speed up neural network multimillion class classification

Gabdullin N., Androsov I., / Series Computer Science "arxiv.org". 2026.

Label prediction in neural networks (NNs) has O(n) complexity proportional to the number of classes. This holds true for classification using fully connected layers and cosine similarity with some set of class prototypes. In this paper we show that if NN latent space (LS) geometry is known and possesses specific properties, label prediction complexity can ...

Added: April 2, 2026

On small n-uniform hypergraphs with positive discrepancy

Cherkashin D., Petrov F., Journal of Combinatorial Theory. Series B 2019 Vol. 139 P. 353–359

A two-coloring of the vertices V of the hypergraph H=(V, E) by red and blue has discrepancy d if d is the largest difference between the number of red and blue points in any edge. Let f(n) be the fewest number of edges in an n-uniform hypergraph without a coloring with discrepancy 0. Erdos and Sos asked: is f(n) unbounded? N. Alon, D. J. ...

Added: October 7, 2019

Регулярность минимайзеров функционала максимального расстояния

Teplitskaya Y., Записки научных семинаров ПОМИ РАН 2017 Т. 462 С. 103–111

In this paper, it is announced that every maximum distance minimizer is a union of finitely many curves having one-sided tangent lines at every point. This shows that a maximum distance minimizer is isotopic to a finite Steiner tree even for a “bad” compact set M, which distinguishes it from a solution of the Steiner ...

Added: October 19, 2018

A note on random greedy coloring of uniform hypergraphs

Cherkashin D., Kozik J., Random Structures and Algorithms 2015 Vol. 47 No. 3 P. 407–413

The smallest number of edges forming an n-uniform hypergraph which is not r-colorable is denoted by m(n,r). Erd\H{o}s and Lov\'{a}sz conjectured that m(n,2)=\theta(n 2^n)$. The best known lower bound m(n,2)=\Omega(sqrt(n/log(n)) 2^n) was obtained by Radhakrishnan and Srinivasan in 2000. We present a simple proof of their result. The proof is based on analysis of random ...

Added: September 10, 2018

Coloring cross-intersecting families

Cherkashin Danila, Electronic Journal of Combinatorics 2018 Vol. 25 No. #P1.47 P. 1–9

Intersecting and cross-intersecting families usually appear in extremal combinatorics in the vein of the Erd˝os–Ko–Rado theorem [4]. On the other hand, P. Erd˝os and L. Lov´asz in the noted paper [6] posed problems on coloring intersecting families as a restriction of classical hypergraph coloring problems to a special class of hypergraphs. This note deals with ...

Added: August 6, 2018

Regularity of the Monge-Ampère equation in Besov's space

Kolesnikov A., Tikhonov S. Y., / Series math "arxiv.org". 2012. No. 1203.3457.

Let $\mu = e^{-V} \ dx$ be a probability measure and $T = \nabla \Phi$ be the optimal transportation mapping pushing forward $\mu$ onto a log-concave compactly supported measure $\nu = e^{-W} \ dx$. In this paper, we introduce a new approach to the regularity problem for the corresponding Monge--Amp{\`e}re equation $e^{-V} = \det D^2 ...

Added: March 28, 2013