共查询到20条相似文献，搜索用时 15 毫秒
1.
We prove that for every fixed k, the number of occurrences of the transitive tournament Trk of order k in a tournament on n vertices is asymptotically minimized when is random. In the opposite direction, we show that any sequence of tournaments achieving this minimum for any fixed is necessarily quasirandom. We present several other characterizations of quasirandom tournaments nicely complementing previously known results and relatively easily following from our proof techniques. 相似文献
2.
Simon Griffiths 《Journal of Graph Theory》2013,74(2):198-209
We show that a number of conditions on oriented graphs, all of which are satisfied with high probability by randomly oriented graphs, are equivalent. These equivalences are similar to those given by Chung, Graham, and Wilson [5] in the case of unoriented graphs, and by Chung and Graham [3] in the case of tournaments. Indeed, our main theorem extends to the case of a general underlying graph G, the main result of [3] which corresponds to the case that G is complete. One interesting aspect of these results is that exactly two of the four orientations of a four cycle can be used for a quasi‐randomness condition, i.e., if the number of appearances they make in D is close to the expected number in a random orientation of the same underlying graph, then the same is true for every small oriented graph H. 相似文献
3.
If T is an n‐vertex tournament with a given number of 3‐cycles, what can be said about the number of its 4‐cycles? The most interesting range of this problem is where T is assumed to have cyclic triples for some and we seek to minimize the number of 4‐cycles. We conjecture that the (asymptotic) minimizing T is a random blow‐up of a constant‐sized transitive tournament. Using the method of flag algebras, we derive a lower bound that almost matches the conjectured value. We are able to answer the easier problem of maximizing the number of 4‐cycles. These questions can be equivalently stated in terms of transitive subtournaments. Namely, given the number of transitive triples in T, how many transitive quadruples can it have? As far as we know, this is the first study of inducibility in tournaments. 相似文献
4.
We find a formula for the number of directed 5‐cycles in a tournament in terms of its edge scores and use the formula to find upper and lower bounds on the number of 5‐cycles in any n‐tournament. In particular, we show that the maximum number of 5‐cycles is asymptotically equal to , the expected number 5‐cycles in a random tournament (), with equality (up to order of magnitude) for almost all tournaments. 相似文献
5.
本文给出了树型代数的拟遗传序数的精确上界以及单生成元的树型代数的拟遗传序数的精确下界及其算法 ,并由此得到一个新的组合公式 . 相似文献
6.
This paper studies, with techniques of Abstract Algebraic Logic, the effects of putting a bound on the cardinality of the set of side formulas in the Deduction Theorem, viewed as a Gentzen‐style rule, and of adding additional assumptions inside the formulas present in Modus Ponens, viewed as a Hilbert‐style rule. As a result, a denumerable collection of new Gentzen systems and two new sentential logics have been isolated. These logics are weaker than the positive implicative logic. We have determined their algebraic models and the relationships between them, and have classified them according to several standard criteria of Abstract Algebraic Logic. One of the logics is protoalgebraic but neither equivalential nor weakly algebraizable, a rare situation where very few natural examples were hitherto known. In passing we have found new, alternative presentations of positive implicative logic, both in Hilbert style and in Gentzen style, and have characterized it in terms of the restricted Deduction Theorem: it is the weakest logic satisfying Modus Ponens and the Deduction Theorem restricted to at most 2 side formulas. The algebraic part of the work has lead to the class of quasi‐Hilbert algebras, a quasi‐variety of implicative algebras introduced by Pla and Verdú in 1980, which is larger than the variety of Hilbert algebras. Its algebraic properties reflect those of the corresponding logics and Gentzen systems. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
7.
Huffman and Tonchev discovered four non‐isomorphic quasi‐symmetric 2‐(49,9,6) designs. They arise from extremal self‐dual [50,25,10] codes with a certain weight enumerator. In this note, a new quasi‐symmetric 2‐(49,9,6) design is constructed. This is established by finding a new extremal self‐dual [50,25,10] code as a neighbor of one of the four extremal codes discovered by Huffman and Tonchev. A number of new extremal self‐dual [50,25,10] codes with other weight enumerators are also found. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 173–179, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10007 相似文献
8.
We study quasi‐random properties of k‐uniform hypergraphs. Our central notion is uniform edge distribution with respect to large vertex sets. We will find several equivalent characterisations of this property and our work can be viewed as an extension of the well known Chung‐Graham‐Wilson theorem for quasi‐random graphs. Moreover, let Kk be the complete graph on k vertices and M(k) the line graph of the graph of the k‐dimensional hypercube. We will show that the pair of graphs (Kk,M(k)) has the property that if the number of copies of both Kk and M(k) in another graph G are as expected in the random graph of density d, then G is quasi‐random (in the sense of the Chung‐Graham‐Wilson theorem) with density close to d. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011 相似文献
9.
We prove that every bipartite C2l‐free graph G contains a C4‐free subgraph H with e(H) ≥ e(G)/(l – 1). The factor 1/(l – 1) is best possible. This implies that ex(n, C2l) ≤ 2(l – 1)ex(n, {C4, C2l}), which settles a special case of a conjecture of Erd?s and Simonovits. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 147–156, 2005 相似文献
10.
We study the maximum number of copies of a graph in graphs with a given number of vertices and edges. We show that for any fixed graph is asymptotically realized by the quasi‐clique provided that the edge density is sufficiently large. We also investigate a variant of this problem, when the host graph is bipartite. 相似文献
11.
12.
In this article, we consider the following problem. Given four distinct vertices v1,v2,v3,v4. How many edges guarantee the existence of seven connected disjoint subgraphs Xi for i = 1,…, 7 such that Xj contains vj for j = 1, 2, 3, 4 and for j = 1, 2, 3, 4, Xj has a neighbor to each Xk with k = 5, 6, 7. This is the so called “rooted K3, 4‐minor problem.” There are only few known results on rooted minor problems, for example, [15,6]. In this article, we prove that a 4‐connected graph with n vertices and at least 5n ? 14 edges has a rooted K3,4‐minor. In the proof we use a lemma on graphs with 9 vertices, proved by computer search. We also consider the similar problems concerning rooted K3,3‐minor problem, and rooted K3,2‐minor problem. More precisely, the first theorem says that if G is 3‐connected and e(G) ≥ 4|G| ? 9 then G has a rooted K3,3‐minor, and the second theorem says that if G is 2‐connected and e(G) ≥ 13/5|G| ? 17/5 then G has a rooted K3,2‐minor. In the second case, the extremal function for the number of edges is best possible. These results are then used in the proof of our forthcoming articles 7 , 8 . © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 191–207, 2007 相似文献
13.
Tarek Sayed Ahmed 《Mathematical Logic Quarterly》2006,52(1):106-112
SC, CA, QA and QEA denote the classes of Pinter's substitution algebras, Tarski's cylindric algebras, Halmos' quasi‐polyadic algebras and quasi‐polyadic equality algebras, respectively. Let ω ≤ α < β and let K ∈ {SC,CA,QA,QEA}. We show that the class of α ‐dimensional neat reducts of algebras in Kβ is not elementary. This solves a problem in [3]. Also our result generalizes results proved in [2] and [3]. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
14.
15.
M. Bărăscu 《代数通讯》2013,41(11):4290-4298
We investigate group gradings of upper block triangular matrix algebras over a field such that all the matrix units lying there are homogeneous elements. We describe these gradings as endomorphism algebras of graded flags and classify them as orbits of a certain biaction of a Young subgroup and the group G on the set G n , where G is the grading group and n is the size of the matrix algebra. In particular, the results apply to algebras of upper triangular matrices. 相似文献
16.
Dirk Meierling 《Journal of Graph Theory》2010,63(1):82-92
A directed cycle C of a digraph D is extendable if there exists a directed cycle C′ in D that contains all vertices of C and an additional one. In 1989, Hendry defined a digraph D to be cycle extendable if it contains a directed cycle and every non‐Hamiltonian directed cycle of D is extendable. Furthermore, D is fully cycle extendable if it is cycle extendable and every vertex of D belongs to a directed cycle of length three. In 2001, Tewes and Volkmann extended these definitions in considering only directed cycles whose length exceed a certain bound 3≤k<n: a digraph D is k ‐extendable if every directed cycle of length t, where k≤t<n, is extendable. Moreover, D is called fully k ‐extendable if D is k ‐extendable and every vertex of D belongs to a directed cycle of length k. An in‐tournament is an oriented graph such that the in‐neighborhood of every vertex induces a tournament. This class of digraphs which generalizes the class of tournaments was introduced by Bang‐Jensen, Huang and Prisner in 1993. Tewes and Volkmann showed that every connected in‐tournament D of order n with minimum degree δ≥1 is ( ) ‐extendable. Furthermore, if D is a strongly connected in‐tournament of order n with minimum degree δ=2 or , then D is fully ( ) ‐extendable. In this article we shall see that if , every vertex of D belongs to a directed cycle of length , which means that D is fully ( ) ‐extendable. This confirms a conjecture of Tewes and Volkmann. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 82–92, 2010 相似文献
17.
Joseph A. Wolf 《Proceedings of the American Mathematical Society》2001,129(8):2483-2487
Let be a complex flag manifold. The compact real form of is transitive on . If is a noncompact real form, such transitivity is rare but occasionally happens. Here we work out a complete list of Lie subgroups of transitive on and pick out the cases that are noncompact real forms of .
18.
Andrs Gyrfs 《Journal of Graph Theory》2001,38(2):111-112
A simple proof is given for a result of Sali and Simonyi on self‐complementary graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 111–112, 2001 相似文献
19.
An in‐tournament is an oriented graph such that the negative neighborhood of every vertex induces a tournament. The topic of this paper is to investigate vertex k‐pancyclicity of in‐tournaments of order n, where for some 3 ≤ k ≤ n, every vertex belongs to a cycle of length p for every k ≤ p ≤ n. We give sharp lower bounds for the minimum degree such that a strong in‐tournament is vertex k‐pancyclic for k ≤ 5 and k ≥ n − 3. In the latter case, we even show that the in‐tournaments in consideration are fully (n − 3)‐extendable which means that every vertex belongs to a cycle of length n − 3 and that the vertex set of every cycle of length at least n − 3 is contained in a cycle of length one greater. In accordance with these results, we state the conjecture that every strong in‐tournament of order n with minimum degree greater than is vertex k‐pancyclic for 5 < k < n − 3, and we present a family of examples showing that this bound would be best possible. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 84–104, 2001 相似文献
20.
Lutz Volkmann 《Discrete Mathematics》2006,306(12):1198-1206
The vertex set of a digraph D is denoted by V(D). A c-partite tournament is an orientation of a complete c-partite graph. In 1991, Jian-zhong Wang conjectured that every arc of a regular 3-partite tournament D is contained in directed cycles of all lengths 3,6,9,…,|V(D)|. This conjecture is not valid, because for each integer t with 3?t?|V(D)|, there exists an infinite family of regular 3-partite tournaments D such that at least one arc of D is not contained in a directed cycle of length t.In this paper, we prove that every arc of a regular 3-partite tournament with at least nine vertices is contained in a directed cycle of length m, m+1, or m+2 for 3?m?5, and we conjecture that every arc of a regular 3-partite tournament is contained in a directed cycle of length m, (m+1), or (m+2) for each m∈{3,4,…,|V(D)|-2}.It is known that every regular 3-partite tournament D with at least six vertices contains directed cycles of lengths 3, |V(D)|-3, and |V(D)|. We show that every regular 3-partite tournament D with at least six vertices also has a directed cycle of length 6, and we conjecture that each such 3-partite tournament contains cycles of all lengths 3,6,9,…,|V(D)|. 相似文献