共查询到20条相似文献,搜索用时 46 毫秒
1.
《Discrete Mathematics》2022,345(6):112830
Given a matroid together with a coloring of its ground set, a subset of its elements is called rainbow colored if no two of its elements have the same color. We show that if an n-element rank r binary matroid M is colored with exactly r colors, then M either contains a rainbow colored circuit or a monochromatic cocircuit. As the class of binary matroids is closed under taking duals, this immediately implies that if M is colored with exactly colors, then M either contains a rainbow colored cocircuit or a monochromatic circuit. As a byproduct, we give a characterization of binary matroids in terms of reductions to partition matroids.Motivated by a conjecture of Bérczi, Schwarcz and Yamaguchi, we also analyze the relation between the covering number of a binary matroid and the maximum number of colors or the maximum size of a color class in any of its rainbow circuit-free colorings. For simple graphic matroids, we show that there exists a rainbow circuit-free coloring that uses each color at most twice only if the graph is -sparse, that is, it is independent in the 2-dimensional rigidity matroid. Furthermore, we give a complete characterization of minimally rigid graphs admitting such a coloring. 相似文献
2.
3.
《Discrete Mathematics》2023,346(4):113304
In 1965 Erd?s asked, what is the largest size of a family of k-element subsets of an n-element set that does not contain a matching of size ? In this note, we improve upon a recent result of Frankl and resolve this problem for and . 相似文献
4.
Will Agnew-Svoboda Alana Huszar Erin McNicholas Jeff Schreiner-McGraw Colin Starr Corrine Yap 《Discrete Mathematics》2019,342(8):2254-2269
Analogous to the concept of uniquely pancyclic graphs, we define a uniquely pancyclic (UPC) matroid of rank to be a (simple) rank- matroid containing exactly one circuit of each length for . Our discussion addresses the existence of graphic, binary, and transversal representations of UPC matroids. Using Shi’s results, which catalogued exactly seven non-isomorphic UPC graphs, we produce a nongraphic binary UPC matroid of rank 24. We consider properties of binary UPC matroids in general, and prove that all binary UPC matroids have a connectivity of . 相似文献
5.
《Discrete Mathematics》2022,345(5):112802
We study logical limit laws for uniform attachment random graphs. In this random graph model, vertices and edges are introduced recursively: at time , the vertex is introduced together with m edges joining the new vertex with m different vertices chosen uniformly at random from . We prove that this random graph obeys convergence law for first-order sentences with at most variables. 相似文献
6.
7.
《Discrete Mathematics》2022,345(1):112669
In this paper, we consider two kinds of spectral extremal questions. The first asks which graph attains the maximum Q-index over all graphs of order n and size ? The second asks which graph attains the maximum Q-index over all -bipartite graphs with edges? We solve the first question for , and the second question for . The maximum Q-index on connected -bipartite graphs is also determined for . 相似文献
8.
《Discrete Mathematics》2022,345(8):112904
Let be the minimum integer such that every plane graph with girth g at least , minimum degree and no -paths consisting of vertices of degree 2, where , has a 3-vertex with at least t neighbors of degree 2, where .In 2015, Jendrol' and Maceková proved . Later on, Hudák et al. established , Jendrol', Maceková, Montassier, and Soták proved , and , and we recently proved that and .Thus is already known for and all t. In this paper, we prove that , , and whenever . 相似文献
9.
Minimal blocking sets in have size at most . This result is due to Bruen and Thas and the bound is sharp, sets attaining this bound are called unitals. In this paper, we show that the second largest minimal blocking sets have size at most , if , , or , , . Our proof also works for sets having at least one tangent at each of its points (that is, for tangency sets). 相似文献
10.
《Discrete Mathematics》2020,343(12):112117
Let be an edge-colored graph of order . The minimum color degree of , denoted by , is the largest integer such that for every vertex , there are at least distinct colors on edges incident to . We say that an edge-colored graph is rainbow if all its edges have different colors. In this paper, we consider vertex-disjoint rainbow triangles in edge-colored graphs. Li (2013) showed that if , then contains a rainbow triangle and the lower bound is tight. Motivated by this result, we prove that if and , then contains two vertex-disjoint rainbow triangles. In particular, we conjecture that if , then contains vertex-disjoint rainbow triangles. For any integer , we show that if and , then contains vertex-disjoint rainbow triangles. Moreover, we provide sufficient conditions for the existence of edge-disjoint rainbow triangles. 相似文献
11.
12.
Let χ be an order c multiplicative character of a finite field and a binomial with . We study the twisted classical and T-adic Newton polygons of f. When , we give a lower bound of Newton polygons and show that they coincide if p does not divide a certain integral constant depending on .We conjecture that this condition holds if p is large enough with respect to by combining all known results and the conjecture given by Zhang-Niu. As an example, we show that it holds for . 相似文献
13.
《Annals of Pure and Applied Logic》2022,173(8):103135
We further develop a forcing notion known as Coding with Perfect Trees and show that this poset preserves, in a strong sense, definable P-points, definable tight MAD families and definable selective independent families. As a result, we obtain a model in which , each of , , has a witness and there is a well-order of the reals. Note that both the complexity of the witnesses of the above combinatorial cardinal characteristics, as well as the complexity of the well-order are optimal. In addition, we show that the existence of a well-order of the reals is consistent with and each of the following: , , , where the smaller cardinal characteristics have co-analytic witnesses.Our methods allow the preservation of only sufficiently definable witnesses, which significantly differs from other preservation results of this type. 相似文献
14.
We look for positive solutions for the singular equation where , , is a parameter, and has some summability properties. By using a perturbation method and critical point theory, we obtain two solutions when and the parameter is small. 相似文献
15.
16.
《Discrete Mathematics》2022,345(11):113029
Let G be a k-connected graph on n vertices. Hippchen's Conjecture (2008) states that two longest paths in G share at least k vertices. Gutiérrez (2020) recently proved the conjecture when or . We improve upon both results; namely, we show that two longest paths in G share at least k vertices when or . This completely resolves two conjectures by Gutiérrez in the affirmative. 相似文献
17.
The k-subset sum problem over finite fields is a classical NP-complete problem. Motivated by coding theory applications, a more complex problem is the higher m-th moment k-subset sum problem over finite fields. We show that there is a deterministic polynomial time algorithm for the m-th moment k-subset sum problem over finite fields for each fixed m when the evaluation set is the image set of a monomial or Dickson polynomial of any degree n. In the classical case , this recovers previous results of Nguyen-Wang (the case ) [22] and the results of Choe-Choe (the case ) [3]. 相似文献
18.
Assume that the vertices of a graph are always operational, but the edges of fail independently with probability . The all-terminal reliability of is the probability that the resulting subgraph is connected. The all-terminal reliability can be formulated into a polynomial in , and it was conjectured that all the roots of (nonzero) reliability polynomials fall inside the closed unit disk. It has since been shown that there exist some connected graphs which have their reliability roots outside the closed unit disk, but these examples seem to be few and far between, and the roots are only barely outside the disk. In this paper we generalize the notion of reliability to simplicial complexes and matroids and investigate when the roots fall inside the closed unit disk. We show that such is the case for matroids of rank 3 and paving matroids of rank 4. We also prove that the reliability roots of shellable complexes are dense in the complex plane, and that the real reliability roots of any matroid lie in . Finally, we also show that the reliability roots of thickenings of the Fano matroid can lie outside the unit disk. 相似文献
19.