An official website of the United States government
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
Clique minors in graphs with a forbidden subgraph
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
- PAR ID:
- 10287337
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 60
- Issue:
- 3
- ISSN:
- 1042-9832
- Page Range / eLocation ID:
- p. 327-338
- 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
-
Abstract As the abyssal oceans warm, stratification is also expected to change in response. This change may impact mixing and vertical transport by altering the buoyancy flux, internal wave generation, and turbulent dissipation. In this study, repeated surveys of three hydrographic sections in the Southwest Pacific Basin between the 1990s and 2010s are used to estimate the change in buoyancy frequency. We find that below the°C isotherm,is on average reduced by a scaling factor of, a 12% reduction, per decade that intensifies with depth. At°C, we observe the biggest change:, or a 29% reduction per decade. Within the same period, the magnitude of vertical diffusive heat flux is also reduced by about, although this estimate is sensitive to the choice of estimated diffusivity. Finally, implications of these results for the heat budget and global ocean circulation are qualitatively discussed.more » « less
-
Abstract The apparent end of the internally generated Martian magnetic field at 3.6–4.1 Ga is a key event in Martian history and has been linked to insufficient core cooling. We investigate the thermal and magnetic evolution of the Martian core and mantle using parameterized models and considered three improvements on previous studies. First, our models account for thermal stratification in the core. Second, the models are constrained by estimates for the present‐day areotherm. Third, we consider core thermal conductivity,, values in the range 5–40 Was suggested by recent experiments on iron alloys at Mars core conditions. The majority of our models indicate that the core of Mars is fully conductive at present with core temperatures greater than 1940 K. All of our models are consistent with the range ofW. Models with an activation volume of 6 (0)require a mantle reference viscosity of Pa s.more » « less
-
Abstract The Whitham equation was proposed as a model for surface water waves that combines the quadratic flux nonlinearityof the Korteweg–de Vries equation and the full linear dispersion relationof unidirectional gravity water waves in suitably scaled variables. This paper proposes and analyzes a generalization of Whitham's model to unidirectional nonlinear wave equations consisting of a general nonlinear flux functionand a general linear dispersion relation. Assuming the existence of periodic traveling wave solutions to this generalized Whitham equation, their slow modulations are studied in the context of Whitham modulation theory. A multiple scales calculation yields the modulation equations, a system of three conservation laws that describe the slow evolution of the periodic traveling wave's wavenumber, amplitude, and mean. In the weakly nonlinear limit, explicit, simple criteria in terms of generalandestablishing the strict hyperbolicity and genuine nonlinearity of the modulation equations are determined. This result is interpreted as a generalized Lighthill–Whitham criterion for modulational instability.more » « less
