共查询到20条相似文献,搜索用时 46 毫秒
1.
《Mathematical Logic Quarterly》2017,63(6):509-535
We study theorems from Functional Analysis with regard to their relationship with various weak choice principles and prove several results about them: “Every infinite‐dimensional Banach space has a well‐orderable Hamel basis” is equivalent to ; “ can be well‐ordered” implies “no infinite‐dimensional Banach space has a Hamel basis of cardinality ”, thus the latter statement is true in every Fraenkel‐Mostowski model of ; “No infinite‐dimensional Banach space has a Hamel basis of cardinality ” is not provable in ; “No infinite‐dimensional Banach space has a well‐orderable Hamel basis of cardinality ” is provable in ; (the Axiom of Choice for denumerable families of non‐empty finite sets) is equivalent to “no infinite‐dimensional Banach space has a Hamel basis which can be written as a denumerable union of finite sets”; Mazur's Lemma (“If X is an infinite‐dimensional Banach space, Y is a finite‐dimensional vector subspace of X , and , then there is a unit vector such that for all and all scalars α”) is provable in ; “A real normed vector space X is finite‐dimensional if and only if its closed unit ball is compact” is provable in ; (Principle of Dependent Choices) + “ can be well‐ordered” does not imply the Hahn‐Banach Theorem ( ) in ; and “no infinite‐dimensional Banach space has a Hamel basis of cardinality ” are independent from each other in ; “No infinite‐dimensional Banach space can be written as a denumerable union of finite‐dimensional subspaces” lies in strength between (the Axiom of Countable Choice) and ; implies “No infinite‐dimensional Banach space can be written as a denumerable union of closed proper subspaces” which in turn implies ; “Every infinite‐dimensional Banach space has a denumerable linearly independent subset” is a theorem of , but not a theorem of ; and “Every infinite‐dimensional Banach space has a linearly independent subset of cardinality ” implies “every Dedekind‐finite set is finite”. 相似文献
2.
3.
For an oriented graph , let denote the size of a minimum feedback arc set, a smallest edge subset whose deletion leaves an acyclic subgraph. Berger and Shor proved that any -edge oriented graph satisfies . We observe that if an oriented graph has a fixed forbidden subgraph , the bound is sharp as a function of if is not bipartite, but the exponent in the lower order term can be improved if is bipartite. Using a result of Bukh and Conlon on Turán numbers, we prove that any rational number in is optimal as an exponent for some finite family of forbidden subgraphs. Our upper bounds come equipped with randomized linear-time algorithms that construct feedback arc sets achieving those bounds. We also characterize directed quasirandomness via minimum feedback arc sets. 相似文献
4.
《Mathematische Nachrichten》2018,291(1):55-85
We study minimal energy problems for strongly singular Riesz kernels , where and , considered for compact ‐dimensional ‐manifolds Γ immersed into . Based on the spatial energy of harmonic double layer potentials, we are motivated to formulate the natural regularization of such minimization problems by switching to Hadamard's partie finie integral operator which defines a strongly elliptic pseudodifferential operator of order on Γ. The measures with finite energy are shown to be elements from the Sobolev space , , and the corresponding minimal energy problem admits a unique solution. We relate our continuous approach also to the discrete one, which has been worked out earlier by D. P. Hardin and E. B. Saff. 相似文献
5.
6.
Dingding Dong 《Journal of Graph Theory》2021,96(1):160-166
In connection with his solution of the Sensitivity Conjecture, Hao Huang (arXiv: 1907.00847, 2019) asked the following question: Given a graph with high symmetry, what can we say about the smallest maximum degree of induced subgraphs of with vertices, where denotes the size of the largest independent set in ? We study this question for , the ‐dimensional Hamming graph over an alphabet of size . Generalizing a construction by Chung et al. (JCT‐A, 1988), we prove that has an induced subgraph with more than vertices and maximum degree at most . Chung et al. proved this statement for (the ‐dimensional cube). 相似文献
7.
We prove that in all regular robust expanders , every edge is asymptotically equally likely contained in a uniformly chosen perfect matching . We also show that given any fixed matching or spanning regular graph in , the random variable is approximately Poisson distributed. This in particular confirms a conjecture and a question due to Spiro and Surya, and complements results due to Kahn and Kim who proved that in a regular graph every vertex is asymptotically equally likely contained in a uniformly chosen matching. Our proofs rely on the switching method and the fact that simple random walks mix rapidly in robust expanders. 相似文献
8.
9.
Michael Savery 《Journal of Graph Theory》2022,99(1):152-161
A graph is Ramsey for a graph if every colouring of the edges of in two colours contains a monochromatic copy of . Two graphs and are Ramsey equivalent if any graph is Ramsey for if and only if it is Ramsey for . A graph parameter is Ramsey distinguishing if implies that and are not Ramsey equivalent. In this paper we show that the chromatic number is a Ramsey distinguishing parameter. We also extend this to the multicolour case and use a similar idea to find another graph parameter which is Ramsey distinguishing. 相似文献
10.
In 1990, Albertson, Berman, Hutchinson, and Thomassen proved a theorem which gives a minimum degree condition for the existence of a spanning tree with no vertices of degree 2. Such a spanning tree is called a homeomorphically irreducible spanning tree (HIST). In this paper, we prove that every graph of order () contains a HIST if for any nonadjacent vertices and . The degree sum condition is best possible. 相似文献
11.
Stijn Cambie Wouter Cames van Batenburg Ewan Davies Ross J. Kang 《Random Structures and Algorithms》2024,64(1):62-93
List coloring is an influential and classic topic in graph theory. We initiate the study of a natural strengthening of this problem, where instead of one list-coloring, we seek many in parallel. Our explorations have uncovered a potentially rich seam of interesting problems spanning chromatic graph theory. Given a -list-assignment of a graph , which is the assignment of a list of colors to each vertex , we study the existence of pairwise-disjoint proper colorings of using colors from these lists. We may refer to this as a list-packing. Using a mix of combinatorial and probabilistic methods, we set out some basic upper bounds on the smallest for which such a list-packing is always guaranteed, in terms of the number of vertices, the degeneracy, the maximum degree, or the (list) chromatic number of . (The reader might already find it interesting that such a minimal is well defined.) We also pursue a more focused study of the case when is a bipartite graph. Our results do not yet rule out the tantalising prospect that the minimal above is not too much larger than the list chromatic number. Our study has taken inspiration from study of the strong chromatic number, and we also explore generalizations of the problem above in the same spirit. 相似文献
12.
Nick Brettell Jake Horsfield Andrea Munaro Giacomo Paesani Daniël Paulusma 《Journal of Graph Theory》2022,99(1):117-151
A large number of -hard graph problems are solvable in time when parameterized by some width parameter. Hence, when solving problems on special graph classes, it is helpful to know if the graph class under consideration has bounded width. In this paper we consider maximum-induced matching width (mim-width), a particularly general width parameter that has a number of algorithmic applications whenever a decomposition is “quickly computable” for the graph class under consideration. We start by extending the toolkit for proving (un)boundedness of mim-width of graph classes. By combining our new techniques with known ones we then initiate a systematic study into bounding mim-width from the perspective of hereditary graph classes, and make a comparison with clique-width, a more restrictive width parameter that has been well studied. We prove that for a given graph , the class of -free graphs has bounded mim-width if and only if it has bounded clique-width. We show that the same is not true for -free graphs. We identify several general classes of -free graphs having unbounded clique-width, but bounded mim-width; moreover, we show that a branch decomposition of constant mim-width can be found in polynomial time for these classes. Hence, these results have algorithmic implications: when the input is restricted to such a class of -free graphs, many problems become polynomial-time solvable, including classical problems, such as - Colouring and Independent Set , domination-type problems known as Locally Checkable Vertex Subset and Vertex Partitioning (LC-VSVP) problems, and distance versions of LC-VSVP problems, to name just a few. We also prove a number of new results showing that, for certain and , the class of -free graphs has unbounded mim-width. Boundedness of clique-width implies boundedness of mim-width. By combining our results with the known bounded cases for clique-width, we present summary theorems of the current state of the art for the boundedness of mim-width for -free graphs. In particular, we classify the mim-width of -free graphs for all pairs with . When and are connected graphs, we classify all pairs except for one remaining infinite family and a few isolated cases. 相似文献
13.
Let be a graph whose largest independent set has size . A permutation of is an independent set permutation of if where is the number of independent sets of size in . In 1987 Alavi, Malde, Schwenk, and Erd?s proved that every permutation of is an independent set permutation of some graph with , that is, with the largest independent set having size . They raised the question of determining, for each , the smallest number such that every permutation of is an independent set permutation of some graph with and with at most vertices, and they gave an upper bound on of roughly . Here we settle the question, determining , and make progress on a related question, that of determining the smallest order such that every permutation of is the unique independent set permutation of some graph of at most that order. More generally we consider an extension of independent set permutations to weak orders, and extend Alavi et al.'s main result to show that every weak order on can be realized by the independent set sequence of some graph with and with at most vertices. Alavi et al. also considered matching permutations, defined analogously to independent set permutations. They observed that not every permutation of is a matching permutation of some graph with the largest matching having size , putting an upper bound of on the number of matching permutations of . Confirming their speculation that this upper bound is not tight, we improve it to . 相似文献
14.
《组合设计杂志》2018,26(3):101-118
Group divisible covering designs (GDCDs) were introduced by Heinrich and Yin as a natural generalization of both covering designs and group divisible designs. They have applications in software testing and universal data compression. The minimum number of blocks in a k‐GDCD of type is a covering number denoted by . When , the values of have been determined completely for all possible pairs . When , Francetić et al. constructed many families of optimal GDCDs, but the determination remained far from complete. In this paper, two specific 4‐IGDDs are constructed, thereby completing the existence problem for 4‐IGDDs of type . Then, additional families of optimal 4‐GDCDs are constructed. Consequently the cases for whose status remains undetermined arise when and , when and , and in several small families for which one of g and u is fixed. 相似文献
15.
《Journal of Graph Theory》2018,87(1):5-17
A 2‐cell embedding of a graph Γ into a closed (orientable or nonorientable) surface is called regular if its automorphism group acts regularly on the flags. In this article, we classify the regular embeddings of the complete multipartite graph . We show that if the number of partite sets is greater than 3, there exists no such embedding; and if the number of partite sets is 3, for any n, there exist one orientable regular embedding and one nonorientable regular embedding of up to isomorphism. 相似文献
16.
17.
Given an ‐vertex pseudorandom graph and an ‐vertex graph with maximum degree at most two, we wish to find a copy of in , that is, an embedding so that for all . Particular instances of this problem include finding a triangle‐factor and finding a Hamilton cycle in . Here, we provide a deterministic polynomial time algorithm that finds a given in any suitably pseudorandom graph . The pseudorandom graphs we consider are ‐bijumbled graphs of minimum degree which is a constant proportion of the average degree, that is, . A ‐bijumbled graph is characterised through the discrepancy property: for any two sets of vertices and . Our condition on bijumbledness is within a log factor from being tight and provides a positive answer to a recent question of Nenadov. We combine novel variants of the absorption‐reservoir method, a powerful tool from extremal graph theory and random graphs. Our approach builds on our previous work, incorporating the work of Nenadov, together with additional ideas and simplifications. 相似文献
18.
Daniel Soltész 《Journal of Graph Theory》2020,93(3):350-362
We say that two graphs on the same vertex set are -creating if the union of the two graphs contains as a subgraph. Let be the maximum number of pairwise -creating Hamiltonian paths of the complete graph . The behavior of is much better understood than the behavior of , the former is an exponential function of whereas the latter is larger than exponential, for every fixed . We study for fixed and tending to infinity. The only nontrivial upper bound on was proved by Cohen, Fachini, and Körner in the case of : In this paper, we generalize their method to prove that for every , and a similar, slightly better upper bound holds when is odd. Our proof uses constructions of bipartite, regular, -free graphs with many edges given in papers by Reiman, Benson, Lazebnik, Ustimenko, and Woldar. 相似文献
19.
Liqiong Xu 《Journal of Graph Theory》2024,105(3):403-412
Let be a positive integer. A graph is said to be uniformly -connected if between any pair of vertices the maximum number of independent paths is exactly . Dawes showed that all minimally 3-connected graphs can be constructed from such that every graph in each intermediate step is also minimally 3-connected. In this paper, we generalize Dawes' result to uniformly 3-connected graphs. We give a constructive characterization of the class of uniformly 3-connected graphs which differs from the characterization provided by Göring et al., where their characterization requires the set of all 3-connected and 3-regular graphs as a starting set, the new characterization requires only the graph . Eventually, we obtain a tight bound on the number of edges in uniformly 3-connected graphs. 相似文献
20.
A conjecture of Chung and Graham states that every -free graph on vertices contains a vertex set of size that spans at most edges. We make the first step toward this conjecture by showing that it holds for all regular graphs. 相似文献