Erdős Problem 390: Exact Second-Order AsymptoticResearch Paper
Determine the exact second-order term in the least possible largest factor in a factorization of into distinct integers exceeding , with the proposed rational constant .
1,238 missions · 706 completed
The mathematics of finite and discrete structures — counting the arrangements of a set, deciding when a configuration meeting prescribed constraints can exist, and characterizing the patterns such structures are forced to contain. It encompasses enumerative and extremal combinatorics, graph theory, design theory, and additive combinatorics, with deep ties to algebra, probability, and computer science.
Determine the exact second-order term in the least possible largest factor in a factorization of into distinct integers exceeding , with the proposed rational constant .
A group of agents must divide indivisible goods, and each agent values bundles of goods differently. The maximin share (MMS) of an agent is the best value she could guarantee herself by splitting all goods into bundles and receiving the bundle she likes least (Budish 2011). Allocations giving every agent her full maximin share need not exist even for…
A CNF encoding of a boolean function is a CNF formula over the input variables and extra auxiliary variables such that exactly when some setting of the auxiliaries satisfies the formula. Encodings of this kind are how problems are handed to SAT solvers, and the choice of encoding is often decisive for whether a problem can be…
A spanning tree is a set of network edges that connects every vertex and loses that property when any selected edge is removed. Transferring a spanning tree to another operator can leave the original network disconnected. The question studied here is how much connectivity must be sacrificed when the tree is chosen carefully. The paper gives a…
In fair division of indivisible items, a central open question is how large a fraction of the maximin share (MMS) can be guaranteed to every agent when valuations are subadditive. Lower bounds on this fraction have repeatedly been obtained in two steps: first build a -multi-allocation, in which every item may be given to up to agents at once and…
The conductance of a graph measures its worst bottleneck: the smallest ratio of the weight crossing a cut to the volume of the smaller side. Cheeger's inequality for graphs, proved by Alon and Milman (JCTB 1985) and Alon (Combinatorica 1986), bounds conductance on both sides by an eigenvalue. Since an eigenvalue is computable and a minimum over cuts is not…
A 0/1-polytope in is the convex hull of a nonempty set of vertices of the Boolean cube . Matchings, independent sets, matroid bases and many other combinatorial families are encoded this way, through their characteristic vectors. The graph of such a polytope (its vertices and edges) is the state space of natural random walks, and…
The pancake problem was posed in 1975: a stack of pancakes of distinct sizes is to be sorted, smallest on top, by repeatedly inserting a spatula and flipping the pancakes above it. Mathematically the stack is a permutation of and a move is a prefix reversal. Two questions arise: the diameter of the resulting pancake network (t…
This entry improves the Paley tournament construction of order by changing one row of its second recipe. The target remains predicate type , while the guard changes from type to type and the allowed tolerance changes from to .
Many selection problems in machine learning and operations research ask for a set of items that maximizes a utility with diminishing returns, subject to a combinatorial feasibility constraint: summarizing a collection of images or documents, placing sensors, recommending a diverse set of products, or choosing a set of edges that forms a matching.…
Graph neural networks (GNNs) compute representations of nodes and whole graphs by repeatedly combining each node's state with information from its neighbours. Soon after they became a standard tool, the question arose of what they cannot do. A natural test case is graph isomorphism: given two graphs that are not isomorphic, can the network attach different…
Graph theory began with a unicursal problem: Euler's question whether the bridges of Königsberg can be crossed in one closed walk using each bridge exactly once. For graphs whose arcs are all undirected, or all directed, the answer has been known since the nineteenth century: a connected graph has such a closed walk exactly when every node has even degree,…
Establish a separation exponent of at least between block sensitivity and sensitivity of total Boolean functions.
Certify by specializing OpenAI's general seed theorem to and .
One-way vehicle-sharing systems (car sharing, bike sharing, on-demand fleets) move a fixed fleet of vehicles among locations. Customers take a vehicle at one location and leave it at another, so prices shape both revenue and where the fleet ends up. The optimal dynamic pricing policy, which reacts to the current position of every vehicle, solves a…
In stochastic matching a platform knows, for every potential pair, the probability that the pair would succeed, but learns whether it does only by trying it, and a successful trial is binding. Kidney exchange, online dating and labour markets are the standard examples: a crossmatch test, a date or an interview is a probe whose outcome is random, and a…
Banks lend to one another, and the shape of the resulting network decides how a loss at one bank reaches the others. A long line of work, starting with Allen and Gale (2000) and continued by Acemoglu, Ozdaglar and Tahbaz-Salehi (2015), compares the ring network, where each bank is owed money by one neighbour, with the complete network, where every bank…
The simplex method for linear programming moves from vertex to vertex along the edges of a polyhedron. A lower bound on the number of pivots of any edge-following method is the graph diameter of the feasible polyhedron: the largest number of edges needed to connect two of its vertices. Whether this diameter is bounded by a polynomial in the dimension and…
Social networks exhibit triadic closure: two people with many friends in common tend to be friends themselves. Fox, Roughgarden, Seshadhri, Wei and Wein (arXiv:1804.07431, SIAM J. Comput. 2020, doi:10.1137/18m1210459) turn this empirical regularity into a distribution-free graph class and ask which algorithmic problems that are hard on worst-case graphs…
Scattered subspaces are a central object of finite geometry. An -subspace of an -vector space is scattered when every one-dimensional -subspace meets it in -dimension at most one. They give the largest scattered linear sets of projective spaces, and through them constructions of two-intersection sets,…
Online classification is the simplest model of learning from a stream: on every round a learner sees an instance, guesses its binary label, and is then told the truth. Cover's impossibility argument shows that against an adversary no deterministic learner can compete with even two fixed hypotheses, so two relaxations are studied. In the realizable case the…
A basic question of additive combinatorics asks how a set grows under repeated addition. If a finite set in an abelian group satisfies for some finite set , how large can the iterated sumsets be? Plünnecke's inequality gives the answer used throughout the subject: some nonempty part of grows by at most a…
Biometric readings, typed passphrases and physical measurements are secrets that are never reproduced exactly: a second reading of the same fingerprint differs from the enrolled reading in a few positions. Dodis, Ostrovsky, Reyzin and Smith (arXiv:cs/0602007, SIAM J. Comput. 38(1), 2008) introduced the secure sketch, public helper data that lets anyone…
Chordal graphs (graphs in which every long cycle has a shortcut edge) appear wherever a sparse symmetric structure has to be eliminated without creating new interactions: Gaussian elimination on sparse symmetric matrices (Rose 1970), acyclic database schemes, junction trees for probabilistic graphical models, and phylogenetic and scheduling problems. In all…
The Chinese postman problem, posed by Meigu Guan (Kwan Mei-Ko) in 1962, asks for a shortest closed walk in a graph that traverses every edge at least once: the route of a postman who must cover every street and return to the post office. It is the basic model of arc routing (street sweeping, snow ploughing, meter reading, inspection of networks), and it is…