On cubic non‐Cayley vertex‐transitive graphs

In 1983, the second author [D. Maru?i?, Ars Combinatoria 16B (1983), 297–302] asked for which positive integers n there exists a non‐Cayley vertex‐transitive graph on n vertices. (The term non‐Cayley numbers has later been given to such integers.) Motivated by this problem, Feng [Discrete Math 248 (2002), 265–269] asked to determine the smallest valency ?(n) among valencies of non‐Cayley vertex‐transitive graphs of order n. As cycles are clearly Cayley graphs, ?(n)?3 for any non‐Cayley number n. In this paper a goal is set to determine those non‐Cayley numbers n for which ?(n) = 3, and among the latter to determine those for which the generalized Petersen graphs are the only non‐Cayley vertex‐transitive graphs of order n. It is known that for a prime p every vertex‐transitive graph of order p, p² or p³ is a Cayley graph, and that, with the exception of the Coxeter graph, every cubic non‐Cayley vertex‐transitive graph of order 2p, 4p or 2p² is a generalized Petersen graph. In this paper the next natural step is taken by proving that every cubic non‐Cayley vertex‐transitive graph of order 4p², p>7 a prime, is a generalized Petersen graph. In addition, cubic non‐Cayley vertex‐transitive graphs of order 2p^k, where p>7 is a prime and k?p, are characterized. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 77–95, 2012     

Non‐elementary speed‐ups in logic calculi

In this paper we show some non‐elementary speed‐ups in logic calculi: Both a predicative second‐order logic and a logic for fixed points of positive formulas are shown to have non‐elementary speed‐ups over first‐order logic. Also it is shown that eliminating second‐order cut formulas in second‐order logic has to increase sizes of proofs super‐exponentially, and the same in eliminating second‐order epsilon axioms. These are proved by relying on results due to P. Pudlák. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Tetravalent half‐edge‐transitive graphs and non‐normal Cayley graphs

Let X be a vertex‐transitive graph, that is, the automorphism group Aut(X) of X is transitive on the vertex set of X. The graph X is said to be symmetric if Aut(X) is transitive on the arc set of X. suppose that Aut(X) has two orbits of the same length on the arc set of X. Then X is said to be half‐arc‐transitive or half‐edge‐transitive if Aut(X) has one or two orbits on the edge set of X, respectively. Stabilizers of symmetric and half‐arc‐transitive graphs have been investigated by many authors. For example, see Tutte [Canad J Math 11 (1959), 621–624] and Conder and Maru?i? [J Combin Theory Ser B 88 (2003), 67–76]. It is trivial to construct connected tetravalent symmetric graphs with arbitrarily large stabilizers, and by Maru?i? [Discrete Math 299 (2005), 180–193], connected tetravalent half‐arc‐transitive graphs can have arbitrarily large stabilizers. In this article, we show that connected tetravalent half‐edge‐transitive graphs can also have arbitrarily large stabilizers. A Cayley graph Cay(G, S) on a group G is said to be normal if the right regular representation R(G) of G is normal in Aut(Cay(G, S)). There are only a few known examples of connected tetravalent non‐normal Cayley graphs on non‐abelian simple groups. In this article, we give a sufficient condition for non‐normal Cayley graphs and by using the condition, infinitely many connected tetravalent non‐normal Cayley graphs are constructed. As an application, all connected tetravalent non‐normal Cayley graphs on the alternating group A₆ are determined. © 2011 Wiley Periodicals, Inc. J Graph Theory     

A deterministic‐control‐based approach to fully nonlinear parabolic and elliptic equations

We show that a broad class of fully nonlinear, second‐order parabolic or elliptic PDEs can be realized as the Hamilton‐Jacobi‐Bellman equations of deterministic two‐person games. More precisely: given the PDE, we identify a deterministic, discrete‐time, two‐person game whose value function converges in the continuous‐time limit to the viscosity solution of the desired equation. Our game is, roughly speaking, a deterministic analogue of the stochastic representation recently introduced by Cheridito, Soner, Touzi, and Victoir. In the parabolic setting with no u‐dependence, it amounts to a semidiscrete numerical scheme whose timestep is a min‐max. Our result is interesting, because the usual control‐based interpretations of second‐order PDEs involve stochastic rather than deterministic control. © 2009 Wiley Periodicals, Inc.     

Characterization of edge‐transitive 4‐valent bicirculants

A bicirculant is a graph admitting an automorphism with exactly two vertex‐orbits of equal size. All non‐isomorphic 4‐valent edge‐transitive bicirculants are characterized in this article. As a corollary, a characterization of 4‐valent arc‐transitive dihedrants is obtained. © 2011 Wiley Periodicals, Inc. J Graph Theory.     

3‐Factor‐Criticality of Vertex‐Transitive Graphs

A graph of order n is p ‐factor‐critical, where p is an integer of the same parity as n, if the removal of any set of p vertices results in a graph with a perfect matching. 1‐factor‐critical graphs and 2‐factor‐critical graphs are factor‐critical graphs and bicritical graphs, respectively. It is well known that every connected vertex‐transitive graph of odd order is factor‐critical and every connected nonbipartite vertex‐transitive graph of even order is bicritical. In this article, we show that a simple connected vertex‐transitive graph of odd order at least five is 3‐factor‐critical if and only if it is not a cycle.     

A deterministic‐control‐based approach motion by curvature

The level‐set formulation of motion by mean curvature is a degenerate parabolic equation. We show that its solution can be interpreted as the value function of a deterministic two‐person game. More precisely, we give a family of discrete‐time, two‐person games whose value functions converge in the continuous‐time limit to the solution of the motion‐by‐curvature PDE. For a convex domain, the boundary's “first arrival time” solves a degenerate elliptic equation; this corresponds, in our game‐theoretic setting, to a minimum‐exit‐time problem. For a nonconvex domain the two‐person game still makes sense; we draw a connection between its minimum exit time and the evolution of curves with velocity equal to the “positive part of the curvature.” These results are unexpected, because the value function of a deterministic control problem is normally the solution of a first‐order Hamilton‐Jacobi equation. Our situation is different because the usual first‐order calculation is singular. © 2005 Wiley Periodicals, Inc.     

Blow‐up profiles of solutions for the exponential reaction‐diffusion equation

We consider the blow‐up of solutions for a semilinear reaction‐diffusion equation with exponential reaction term. It is known that certain solutions that can be continued beyond the blow‐up time possess a non‐constant self‐similar blow‐up profile. Our aim is to find the final time blow‐up profile for such solutions. The proof is based on general ideas using semigroup estimates. The same approach works also for the power nonlinearity. Copyright © 2011 John Wiley & Sons, Ltd.     

Classification of non‐well‐founded sets and an application

A complete list of Finsler, Scott and Boffa sets whose transitive closures contain 1, 2 and 3 elements is given. An algorithm for deciding the identity of hereditarily finite Scott sets is presented. Anti‐well‐founded (awf) sets, i. e., non‐well‐founded sets whose all maximal ∈‐paths are circular, are studied. For example they form transitive inner models of ZFC minus foundation and empty set, and they include uncountably many hereditarily finite awf sets. A complete list of Finsler and Boffa awf sets with 2 and 3 elements in their transitive closure is given. Next the existence of infinite descending ∈‐sequences in Aczel universes is shown. Finally a theorem of Ballard and Hrbá?ek concerning nonstandard Boffa universes of sets is considerably extended.     

Large families of mutually embeddable vertex‐transitive graphs

For each infinite cardinal κ, we give examples of 2^κ many non‐isomorphic vertex‐transitive graphs of order κ that are pairwise isomorphic to induced subgraphs of each other. We consider examples of graphs with these properties that are also universal, in the sense that they embed all graphs with smaller orders as induced subgraphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 99–106, 2003     

Vertex‐Transitive Graphs of Prime‐Squared Order Are Hamilton‐Decomposable

We prove that all connected vertex‐transitive graphs of order p², p a prime, can be decomposed into Hamilton cycles.     

Stability of non‐constant steady‐state solutions for non‐isentropic Euler–Maxwell system with a temperature damping term

This work is concerned with the periodic problem for compressible non‐isentropic Euler–Maxwell systems with a temperature damping term arising in plasmas. For this problem, we prove the global in time existence of a smooth solution around a given non‐constant steady state with the help of an induction argument on the order of the mixed time‐space derivatives of solutions in energy estimates. Moreover, we also show the convergence of the solution to this steady state as the time goes to the infinity. This phenomenon on the charge transport shows the essential relation of the systems with the non‐isentropic Euler–Maxwell and the isentropic Euler–Maxwell systems. Copyright © 2015 John Wiley & Sons, Ltd.     

Semi‐transitive graphs

In this paper, we first consider graphs allowing symmetry groups which act transitively on edges but not on darts (directed edges). We see that there are two ways in which this can happen and we introduce the terms bi‐transitive and semi‐transitive to describe them. We examine the elementary implications of each condition and consider families of examples; primary among these are the semi‐transitive spider‐graphs PS(k,N;r) and MPS(k,N;r). We show how a product operation can be used to produce larger graphs of each type from smaller ones. We introduce the alternet of a directed graph. This links the two conditions, for each alternet of a semi‐transitive graph (if it has more than one) is a bi‐transitive graph. We show how the alternets can be used to understand the structure of a semi‐transitive graph, and that the action of the group on the set of alternets can be an interesting structure in its own right. We use alternets to define the attachment number of the graph, and the important special cases of tightly attached and loosely attached graphs. In the case of tightly attached graphs, we show an addressing scheme to describe the graph with coordinates. Finally, we use the addressing scheme to complete the classification of tightly attached semi‐transitive graphs of degree 4 begun by Marus?ic? and Praeger. This classification shows that nearly all such graphs are spider‐graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 1–27, 2004     

An intuitionistic formula hierarchy based on high‐school identities

We revisit the notion of intuitionistic equivalence and formal proof representations by adopting the view of formulas as exponential polynomials. After observing that most of the invertible proof rules of intuitionistic (minimal) propositional sequent calculi are formula (i.e., sequent) isomorphisms corresponding to the high‐school identities, we show that one can obtain a more compact variant of a proof system, consisting of non‐invertible proof rules only, and where the invertible proof rules have been replaced by a formula normalization procedure. Moreover, for certain proof systems such as the G4ip sequent calculus of Vorob'ev, Hudelmaier, and Dyckhoff, it is even possible to see all of the non‐invertible proof rules as strict inequalities between exponential polynomials; a careful combinatorial treatment is given in order to establish this fact. Finally, we extend the exponential polynomial analogy to the first‐order quantifiers, showing that it gives rise to an intuitionistic hierarchy of formulas, resembling the classical arithmetical hierarchy, and the first one that classifies formulas while preserving isomorphism.     

Tetravalent vertex‐transitive graphs of order 4p

A graph is vertex‐transitive if its automorphism group acts transitively on vertices of the graph. A vertex‐transitive graph is a Cayley graph if its automorphism group contains a subgroup acting regularly on its vertices. In this article, the tetravalent vertex‐transitive non‐Cayley graphs of order 4p are classified for each prime p. As a result, there are one sporadic and five infinite families of such graphs, of which the sporadic one has order 20, and one infinite family exists for every prime p>3, two families exist if and only if p≡1 (mod 8) and the other two families exist if and only if p≡1 (mod 4). For each family there is a unique graph for a given order. © 2011 Wiley Periodicals, Inc.     

Comparison of exponential‐logarithmic and logarithmic‐exponential series

We explain how the field of logarithmic‐exponential series constructed in 20 and 21 embeds as an exponential field in any field of exponential‐logarithmic series constructed in 9 , 6 , and 13 . On the other hand, we explain why no field of exponential‐logarithmic series embeds in the field of logarithmic‐exponential series. This clarifies why the two constructions are intrinsically different, in the sense that they produce non‐isomorphic models of Th$(\mathbb {R}_{\mbox{an, exp}})$; the elementary theory of the ordered field of real numbers, with the exponential function and restricted analytic functions.     

Stochastic homogenization of Hamilton‐Jacobi‐Bellman equations

We study the homogenization of some Hamilton‐Jacobi‐Bellman equations with a vanishing second‐order term in a stationary ergodic random medium under the hyperbolic scaling of time and space. Imposing certain convexity, growth, and regularity assumptions on the Hamiltonian, we show the locally uniform convergence of solutions of such equations to the solution of a deterministic “effective” first‐order Hamilton‐Jacobi equation. The effective Hamiltonian is obtained from the original stochastic Hamiltonian by a minimax formula. Our homogenization results have a large‐deviations interpretation for a diffusion in a random environment. © 2005 Wiley Periodicals, Inc.     

Interaction of faults under slip‐dependent friction. Non‐linear eigenvalue analysis

We analyse the evolution of a system of finite faults by considering the non‐linear eigenvalue problems associated to static and dynamic solutions on unbounded domains. We restrict our investigation to the first eigenvalue (Rayleigh quotient). We point out its physical significance through a stability analysis and we give an efficient numerical algorithm able to compute it together with the corresponding eigenfunction. We consider the anti‐plane shearing on a system of finite faults under a slip‐dependent friction in a linear elastic domain, not necessarily bounded. The static problem is formulated in terms of local minima of the energy functional. We introduce the non‐linear (static) eigenvalue problem and we prove the existence of a first eigenvalue/eigenfunction characterizing the isolated local minima. For the dynamic problem, we discuss the existence of solutions with an exponential growth, to deduce a (dynamic) non‐linear eigenvalue problem. We prove the existence of a first dynamic eigenvalue and we analyse its behaviour with respect to the friction parameter. We deduce a mixed finite element discretization of the non‐linear spectral problem and we give a numerical algorithm to approach the first eigenvalue/eigenfunction. Finally we give some numerical results which include convergence tests, on a single fault and a two‐faults system, and a comparison between the non‐linear spectral results and the time evolution results. Copyright © 2004 John Wiley & Sons, Ltd.     

On Finite 2‐Path‐Transitive Graphs

The class of graphs that are 2‐path‐transitive but not 2‐arc‐transitive is investigated. The amalgams for such graphs are determined, and structural information regarding the full automorphism groups is given. It is then proved that a graph is 2‐path‐transitive but not 2‐arc‐transitive if and only if its line graph is half‐arc‐transitive, thus providing a method for constructing new families of half‐arc‐transitive graphs. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 225–237, 2013