An official website of the United States government
Abstract The classical Hadwiger conjecture dating back to 1940s states that any graph of chromatic number at leastrhas the clique of orderras a minor. Hadwiger's conjecture is an example of a well‐studied class of problems asking how large a clique minor one can guarantee in a graph with certain restrictions. One problem of this type asks what is the largest size of a clique minor in a graph onnvertices of independence numberat mostr. If true Hadwiger's conjecture would imply the existence of a clique minor of order. Results of Kühn and Osthus and Krivelevich and Sudakov imply that if one assumes in addition thatGisH‐free for some bipartite graphHthen one can find a polynomially larger clique minor. This has recently been extended to triangle‐free graphs by Dvořák and Yepremyan, answering a question of Norin. We complete the picture and show that the same is true for arbitrary graphH, answering a question of Dvořák and Yepremyan. In particular, we show that any‐free graph has a clique minor of order, for some constantdepending only ons. The exponent in this result is tight up to a constant factor in front of theterm.
more »
« less
Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth
Abstract In this paper, we consider a randomized greedy algorithm for independent sets inr‐uniformd‐regular hypergraphsGonnvertices with girthg. By analyzing the expected size of the independent sets generated by this algorithm, we show that, whereconverges to 0 asg → ∞for fixeddandr, andf(d, r) is determined by a differential equation. This extends earlier results of Garmarnik and Goldberg for graphs [8]. We also prove that when applying this algorithm to uniform linear hypergraphs with bounded degree, the size of the independent sets generated by this algorithm concentrate around the mean asymptotically almost surely.
more »
« less
- Award ID(s):
- 1800832
- PAR ID:
- 10237374
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 59
- Issue:
- 1
- ISSN:
- 1042-9832
- Page Range / eLocation ID:
- p. 79-95
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of annvertex graph, and need to output a clique. We show that if the input graph is drawn at random from(and hence is likely to have a clique of size roughly), then for everyδ<2 and constantℓ, there is anα<2 (that may depend onδandℓ) such that no algorithm that makesnδprobes inℓrounds is likely (over the choice of the random graph) to output a clique of size larger than.more » « less
-
Abstract In this paper, we are interested in the following question: given an arbitrary Steiner triple systemonvertices and any 3‐uniform hypertreeonvertices, is it necessary thatcontainsas a subgraph provided? We show the answer is positive for a class of hypertrees and conjecture that the answer is always positive.more » « less
-
Abstract We study the stability and nonlinear local dynamics of spectrally stable periodic wave trains of the Korteweg‐de Vries/Kuramoto‐Sivashinsky equation when subjected to classes of periodic perturbations. It is known that for each, such a‐periodic wave train is asymptotically stable to‐periodic, i.e., subharmonic, perturbations, in the sense that initially nearby data will converge asymptotically to a small Galilean boost of the underlying wave, with exponential rates of decay. However, both the allowable size of initial perturbations and the exponential rates of decay depend onand, in fact, tend to zero as, leading to a lack of uniformity in such subharmonic stability results. Our goal here is to build upon a recent methodology introduced by the authors in the reaction–diffusion setting and achieve a subharmonic stability result, which is uniform in. This work is motivated by the dynamics of such wave trains when subjected to perturbations that are localized (i.e., integrable on the line).more » « less
-
We prove the endpoint case of a conjecture of Khot and Moshkovitz related to the unique games conjecture, less a small error. Letn ≥ 2. Suppose a subset Ω ofn‐dimensional Euclidean spacesatisfies −Ω = Ωcand Ω + v = Ωc(up to measure zero sets) for every standard basis vector. For anyand for anyq ≥ 1, letand let. For anyx ∈ ∂Ω, letN(x) denote the exterior normal vector atxsuch that ‖N(x)‖2 = 1. Let. Our main result shows thatBhas the smallest Gaussian surface area among all such subsets Ω, less a small error:In particular,Standard arguments extend these results to a corresponding weak inequality for noise stability. Removing the factor 6 × 10−9would prove the endpoint case of the Khot‐Moshkovitz conjecture. Lastly, we prove a Euclidean analogue of the Khot and Moshkovitz conjecture. The full conjecture of Khot and Moshkovitz provides strong evidence for the truth of the unique games conjecture, a central conjecture in theoretical computer science that is closely related to the P versus NP problem. So, our results also provide evidence for the truth of the unique games conjecture. Nevertheless, this paper does not prove any case of the unique games conjecture.more » « less
