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
Finding cliques using few probes
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
- PAR ID:
- 10121830
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 56
- Issue:
- 1
- ISSN:
- 1042-9832
- Page Range / eLocation ID:
- p. 142-153
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
We study a noisy graph isomorphism problem, where the goal is to perfectly recover the vertex correspondence between two edge‐correlated graphs, with an initial seed set of correctly matched vertex pairs revealed as side information. We show that it is possible to achieve the information‐theoretic limit of graph sparsity in time polynomial in the number of verticesn. Moreover, we show the number of seeds needed for perfect recovery in polynomial‐time can be as low asin the sparse graph regime (with the average degree smaller than) andin the dense graph regime, for a small positive constant. Unlike previous work on graph matching, which used small neighborhoods or small subgraphs with a logarithmic number of vertices in order to match vertices, our algorithms match vertices if their large neighborhoods have a significant overlap in the number of seeds.more » « less
-
Abstract N‐Type thermoelectrics typically consist of small molecule dopant+polymer host. Only a few polymer dopant+polymer host systems have been reported, and these have lower thermoelectric parameters. N‐type polymers with high crystallinity and order are generally used for high‐conductivity () organic conductors. Few n‐type polymers with only short‐range lamellar stacking for high‐conductivity materials have been reported. Here, we describe an n‐type short‐range lamellar‐stacked all‐polymer thermoelectric system with highestof 78 S−1, power factor (PF) of 163 μW m−1 K−2, and maximum Figure of merit (ZT) of 0.53 at room temperature with a dopant/host ratio of 75 wt%. The minor effect of polymer dopant on the molecular arrangement of conjugated polymer PDPIN at high ratios, high doping capability, high Seebeck coefficient (S) absolute values relative to, and atypical decreased thermal conductivity () with increased doping ratio contribute to the promising performance.more » « less
-
Abstract Nitrification, the microbial conversion of ammonium to nitrite then to nitrate, occurs throughout the oceanic water column, yet the environmental factors influencing the production of nitrate in the euphotic zone (EZ) remain unclear. In this study, the natural abundances of N and O isotopes (δ15N and δ18O, respectively) in nitrate were used in an existing model framework to quantify nitrate contributed by EZ nitrification in the California Current Ecosystem (CCE) during two anomalously warm years. Model data estimated that between 6% and 36% of the EZ nitrate reservoirs were derived from the combined steps of nitrification within the EZ. The CCE data set found nitrification contributions to EZ nitrate to be positively correlated with nitrite concentrations () at the depth of the primary nitrite maximum (PNM). Building on this correlation, EZ nitrification in the southern California Current was estimated to contribute on average 20% ± 6% to EZ nitrate as inferred using the PNMof the long‐term California Cooperative Oceanic Fisheries Investigation (CalCOFI) survey record. A multiple linear regression analysis of the CalCOFI PNMtime series identified two conditions that led to positive deviations in. Enhanced PNM, and potentially enhanced EZ nitrification, may be linked to (1) reduced phytoplankton competition for ammonium () andas interpreted from particulate organic carbon:chlorophyll ratios, and/or (2) to increased supply of(and thenoxidation to) from the degradation of organic nitrogen as interpreted from particulate organic nitrogen concentrations.more » « less
