Browsing by Browse by FOR 2008 "010104 Combinatorics and Discrete Mathematics (excl. Physical Combinatorics)"

The Minority Game was introduced to show basic properties of competitive systems with limited common information resources. M. Paczuski and K. E. Bassler introduced a Minority Game with personal limited information resources, where each agent knows the past actions of randomly chosen neighbours [M. Paczuski, K.E. Bassler, Self-organized Networks of Competing Boolean Agents (1999)]. They asked whether such a system can show cooperation. In this paper we show that agents who are placed in a circle are able to cooperate due to self-organization. Furthermore, we introduce a new evolution method to optimize the cooperation among the agents.

We consider the problem to decompose a binary matrix into a small number of binary matrices whose 1-entries form a rectangle. We show that the linear relaxation of this problem has an optimal integral solution corresponding to a well known geometric result on the decomposition of rectilinear polygons.

We consider the problem of characterizing the convex hull of the graph of a bilinear function f on the n-dimensional unit cube [0, 1]n. Extended formulations for this convex hull are obtained by taking subsets of the facets of the Boolean Quadric Polytope (BQP). Extending existing results, we propose a systematic study of properties of f that guarantee that certain classes of BQP facets are sufficient for an extended formulation. We use a modification of Zuckerberg’s geometric method for proving convex hull characterizations (Zuckerberg, 2016) to prove some initial results in this direction. In particular, we provide small-sized extended formulations for bilinear functions whose corresponding graph is either a cycle with arbitrary edge weights or a clique or an almost clique with unit edge weights.

We study a certain polytope arising from embedding the Hamiltonian cycle problem in a discounted Markov decision process. The Hamiltonian cycle problem can be reduced to finding particular extreme points of a certain polytope associated with the input graph. This polytope is a subset of the space of discounted occupational measures. We characterize the feasible bases of the polytope for a general input graph G, and determine the expected numbers of different types of feasible bases when the underlying graph is random. We utilize these results to demonstrate that augmenting certain additional constraints to reduce the polyhedral domain can eliminate a large number of feasible bases that do not correspond to Hamiltonian cycles. Finally, we develop a random walk algorithm on the feasible bases of the reduced polytope and present some numerical results. We conclude with a conjecture on the feasible bases of the reduced polytope.

Given an edge-weighted graph G = (V,E) and a set E₀⊂E , the incremental network design problem with minimum spanning trees asks for a sequence of edges e′ ₁ , … , e ′ _T ∈ E ∖ E ₀ minimizing ∑ ^T _{t = 1} w ( X _t ) where w(X_t) is the weight of a minimum spanning tree X_t for the subgraph (V,E₀∪ { e ′ ₁ , … , e ′ _T } ) and T=|E∖ E 0 |. We prove that this problem can be solved by a greedy algorithm.

In this note, we study a dynamic vertex coloring for a graph G. In particular, one starts with a certain set of vertices black, and all other vertices white. Then, at each time step, a black vertex with exactly one white neighbor forces its white neighbor to become black. The initial set of black vertices is called a zero forcing set if by iterating this process, all of the vertices in G become black. The zero forcing number of G is the minimum cardinality of a zero forcing set in G, and is denoted by Z(G). Davila and Kenter have conjectured in 2015 that Z(G)≥(g−3)(δ−2)+δ where g and δ denote the girth and the minimum degree of G, respectively. This conjecture has been proven for graphs with girth g≤10. In this note, we present a proof for g≥5, δ≥2, thereby settling the conjecture.

Interconnection networks provide an effective mechanism for exchanging data between processors in a parallel computing system. One of the most efficient interconnection networks is the hypercube due to its structural regularity, potential for parallel computation of various algorithms, and the high degree of fault tolerance. Thus it becomes the first choice of topological structure of parallel processing and computing systems. In this paper, lower bounds for the dilation, wirelength, and edge congestion of an embedding of a graph into a hypercube are proved. Two of these bounds are expressed in terms of the bisection width. Applying these results, the dilation and wirelength of embedding of certain complete multipartite graphs, folded hypercubes, wheels, and specific Cartesian products are computed.

Let 𝑛 ≥ 4 be a natural number, and let 𝐾 be a set 𝐾 ⊆ [𝑛] := {1, 2, . . . , 𝑛}. We study the problem to find the smallest possible size of a maximal family 𝒜 of subsets of [𝑛] such that 𝒜 contains only sets whose size is in 𝐾, and 𝐴 ⊈ 𝐵 for all {𝐴, 𝐵} ⊆ 𝒜, i.e. 𝒜 is an antichain. We present a general construction of such antichains for sets 𝐾 containing 2, but not 1. If 3 ∈ 𝐾 our construction asymptotically yields the smallest possible size of such a family, up to an 𝑜(𝑛²) error. We conjecture our construction to be asymptotically optimal also for 3 ∉ 𝐾, and we prove a weaker bound for the case 𝐾 = {2, 4}. Our asymptotic results are straightforward applications of the graph removal lemma to an equivalent reformulation of the problem in extremal graph theory which is interesting in its own right.

We study maximal families 𝒜 of subsets of [𝑛]={1,2, . . . , 𝑛} such that 𝒜 contains only pairs and triples and 𝐴⊈𝐵 for all {𝐴,𝐵}⊆𝒜, i.e. 𝒜 is an antichain. For any 𝑛, all such families 𝒜 of minimum size are determined. This is equivalent to finding all graphs 𝐺=(𝑉,𝐸) with |𝑉|=𝑛 and with the property that every edge is contained in some triangle and such that|𝐸|−|𝑇| is maximum, where 𝑇 denotes the set of triangles in 𝐺. The largest possible value of |𝐸|−|𝑇| turns out to be equal to ⌊(𝑛+1)²/8⌋. Furthermore, if all pairs and triples have weights 𝑤₂ and 𝑤₃, respectively, the problem of minimizing the total weight 𝑤(𝒜) of 𝒜 is considered. We show that min 𝑤(𝒜)=(2𝑤₂+𝑤₃)𝑛²/8+𝑜(𝑛²) for 3/𝑛≤𝑤₃/𝑤₂=:λ=λ(𝑛)<2. For λ≥2 our problem is equivalent to the (6,3)-problem of Ruzsa and Szemerédi, and by a result of theirs it follows that min 𝑤(𝒜)= 𝑤₂𝑛²/2+𝑜(𝑛²).

Let 𝐺 = (𝑉,𝐸) be a connected graph and let 𝑑(𝑢,𝑣) denote the distance between vertices 𝑢,𝑣∈𝑉. A metric basis for 𝐺 is a set 𝐵⊆𝑉 of minimum cardinality such that no two vertices of 𝐺 have the same distances to all points of 𝐵. The cardinality of a metric basis of 𝐺 is called the metric dimension of 𝐺, denoted by dim(𝐺). In this paper we determine the metric dimension of the circulant graphs 𝐶(𝑛,±{1,2,3,4}) for all values of 𝑛.

Let n ≥ 3 be a natural number. We study the problem to find the smallest 𝑟 such that there is a family 𝒜 of 2-subsets and 3-subsets of [𝑛] = {1, 2, . . . ,𝑛} with the following properties: (1) 𝒜 is an antichain, i.e., no member of 𝒜 is a subset of any other member of 𝒜; (2) 𝒜 is maximal, i.e., for every 𝑋 ∈ 2⁽ⁿ⁾ \ 𝒜 there is an 𝐴 ∈ 𝒜 with 𝑋 ⊆ 𝐴 or 𝐴 ⊆ 𝑋; and (3) 𝒜 is 𝑟-regular, i.e., every point 𝑥 ∈ [𝑛] is contained in exactly 𝑟 members of 𝒜. We prove lower bounds on 𝑟, and we describe constructions for regular maximal antichains with small regularity.

Zero forcing is a graph propagation process introduced in quantum physics and theoretical computer science, and closely related to the minimum rank problem. The minimum rank of a graph is the smallest possible rank over all matrices described by a given network. We use this relationship to determine the minimum rank and the zero forcing number of butterfly networks, concluding they present optimal properties in regards to both problems.

Building on classical theorems of Sperner and Kruskal-Katona, we investigate antichains F in the Boolean lattice Bn of all subsets of [n]:={1,2,…,n}, where F is flat, meaning that it contains sets of at most two consecutive sizes, say F=A∪B, where A contains only k-subsets, while B contains only (k − 1)-subsets. Moreover, we assume A consists of the first m k-subsets in squashed (colexicographic) order, while B consists of all (k − 1)-subsets not contained in the subsets in A. Given reals α,β > 0, we say the weight of F is α⋅|A|+β⋅|B|. We characterize the minimum weight antichains F for any given n,k,α,β, and we do the same when in addition F is a maximal antichain. We can then derive asymptotic results on both the minimum size and the minimum Lubell function.

Let G=(V,A) be a directed graph, and let S⊆V be a set of vertices. Let the sequence S=S₀⊆S₁⊆S₂⊆⋯ be defined as follows: S₁ is obtained from S₀ by adding all out-neighbors of vertices in S₀. For k⩾2, Sₖ is obtained from Sₖ₋₁ by adding all vertices w such that for some vertex v∈Sₖ₋₁, w is the unique out-neighbor of v in V∖Sₖ₋₁. We set M(S)=S₀∪S₁∪⋯, and call S a power dominating set for G if M(S)=V(G). The minimum cardinality of such a set is called the power domination number of G. In this paper, we determine the power domination numbers of de Bruijn and Kautz digraphs.

We consider an algorithm on a graph 𝐺 = (𝑉, 𝐸) with a 2-colouring of 𝑉, that is motivated from the computer-aided text-recognition. Every vertex changes simultaneously its colour if more than a certain proportion 𝑐 of its neighbours have the other colour. It is shown, that by iterating this algorithm the colouring becomes either constant or 2-periodic. For 𝑐 = ½ the presented theorem is a special case of a known result [1], but here developed independently with another motivation and a new proof.

Sequential allocation is a simple and attractive mechanism for the allocation of indivisible goods used in a number of real world settings. In sequential allocation, agents pick items according to a policy, the order in which agents take turns. Sequential allocation will return an allocation which is Pareto efficient – no agent can do better without others doing worse. However, sequential allocation may not return the outcome that optimizes the social welfare. We consider therefore the relationship between the welfare and the efficiency of the allocations returned by sequential allocation mechanisms. We then study some simple computational questions about what welfare is possible or necessary depending on the choice of policy. Over half the problems we study turn out to be tractable, and we give polynomial time algorithms to compute them. We also consider a novel control problem in which the Chair chooses a policy to improve social welfare. Again, many of the control problems we study turn out to be tractable, and our results give polynomial time algorithms. In this case, tractability is a good thing so that the Chair can improve the social welfare of the allocation.

Zero forcing is a propagation process on a graph, or digraph, defined in linear algebra to provide a bound for the minimum rank problem. Independently, zero forcing was introduced in physics, computer science and network science, areas where line digraphs are frequently used as models. Zero forcing is also related to power domination, a propagation process that models the monitoring of electrical power networks. In this paper we study zero forcing in iterated line digraphs and provide a relationship between zero forcing and power domination in line digraphs. In particular, for regular iterated line digraphs we determine the minimum rank/maximum nullity, zero forcing number and power domination number, and provide constructions to attain them. We conclude that regular iterated line digraphs present optimal minimum rank/maximum nullity, zero forcing number and power domination number, and apply our results to determine those parameters on some families of digraphs often used in applications.

A subset S of initially infected vertices of a graph G is called zero forcing if we can infect the entire graph by iteratively applying the following process. At each step, any infected vertex which has a unique uninfected neighbor, infects this neighbor. The zero forcing number of G is the minimum cardinality of a zero forcing set in G. We study the zero forcing number of various classes of graphs, including graphs of large girth, H-free graphs for a fixed bipartite graph H, and random and pseudorandom graphs.